模式匹配在“替代"中 [英] Pattern matching in `Alternative`

问题描述

我有一个函数，该函数在其参数上进行模式匹配以在StateT () Maybe ()中进行计算.这种计算在运行时可能会失败，在这种情况下，我希望当前的模式匹配分支失败.

I have a function that pattern matches on its arguments to produce a computation in StateT () Maybe (). This computation can fail when run, in which case I want the current pattern match branch to fail, so to speak.

我非常怀疑是否可能有类似的东西

I highly doubt it's possible to have something like

compute :: Int -> StateT () Maybe Int
compute = return

f :: Maybe Int -> Maybe Int -> StateT () Maybe ()
f (Just n1) (Just n2) = do
  m <- compute (n1 + n2) 
  guard (m == 42)
f (Just n) _ = do
  m <- compute n
  guard (m == 42)
f _ (Just n) = do
  m <- compute n
  guard (m == 42)

的运行方式:当第一次计算由于guard或compute中的某处而失败时，我希望f尝试下一个模式.

behave in the way I want it to: When the first computation fails due to the guard or somewhere in compute, I want f to try the next pattern.

显然，以上内容不起作用，因为StateT(就像其他任何monad一样)在扩展时会涉及一个附加参数，因此我可能无法将其表述为简单的模式防护.

Obviously the above can't work, because StateT (as any other monad might) involves an additional parameter when expanded, so I probably can't formulate this as simple pattern guards.

以下内容可以满足我的要求，但是很丑:

The following does what I want, but it's ugly:

f' :: Maybe Int -> Maybe Int -> StateT () Maybe ()
f' a b = asum (map (\f -> f a b) [f1, f2, f3])
  where
    f1 a b = do
      Just n1 <- pure a
      Just n2 <- pure b
      m <- compute (n1 + n2) 
      guard (m == 42)
    f2 a _ = do
      Just n <- pure a
      m <- compute n
      guard (m == 42)
    f3 _ b = do
      Just n <- pure b
      m <- compute n
      guard (m == 42)

像execStateT (f (Just 42) (Just 1)) ()这样的调用将对f失败，但对于f'则返回Just ()，因为它与f2匹配.

A call like execStateT (f (Just 42) (Just 1)) () would fail for f but return Just () for f', because it matches f2.

如何在具有优雅的模式匹配和尽可能少的辅助定义(如f中)的同时获得f'的行为?还有其他更优雅的方式来表述吗?

How do I get the behavior of f' while having elegant pattern matching with as little auxiliary definitions as possible like in f? Are there other, more elegant ways to formulate this?

完整的可运行示例:

#! /usr/bin/env stack
-- stack --resolver=lts-11.1 script

import Control.Monad.Trans.State
import Control.Applicative
import Control.Monad
import Data.Foldable

compute :: Int -> StateT () Maybe Int
compute = return

f :: Maybe Int -> Maybe Int -> StateT () Maybe ()
f (Just n1) (Just n2) = do
  m <- compute (n1 + n2) 
  guard (m == 42)
f (Just n) _ = do
  m <- compute n
  guard (m == 42)
f _ (Just n) = do
  m <- compute n
  guard (m == 42)

f' :: Maybe Int -> Maybe Int -> StateT () Maybe ()
f' a b = asum (map (\f -> f a b) [f1, f2, f3])
  where
    f1 a b = do
      Just n1 <- pure a
      Just n2 <- pure b
      m <- compute (n1 + n2) 
      guard (m == 42)
    f2 a _ = do
      Just n <- pure a
      m <- compute n
      guard (m == 42)
    f3 _ b = do
      Just n <- pure b
      m <- compute n
      guard (m == 42)

main = do
  print $ execStateT (f (Just 42) (Just 1)) ()  -- Nothing
  print $ execStateT (f' (Just 42) (Just 1)) () -- Just (), because `f2` succeeded

---

编辑:到目前为止，我已经就这个问题得出了一些聪明的答案，谢谢！不幸的是，他们大多数都无法适应我给出的特定代码示例.实际上，我需要类似这样的方法来统一两个表达式(准确地说是let-bindings)，在这里我想尝试统一两个同时允许的RHS的RHS，并陷入我在一侧处理let结合的情况.通过漂浮他们的时间.因此，实际上在Maybe参数上没有聪明的结构可以利用，而我实际上在Int上不是compute.

---

Edit: I elicited quite some clever answers with this question so far, thanks! Unfortunately, they mostly suffer from overfitting to the particular code example I've given. In reality, I need something like this for unifying two expressions (let-bindings, to be precise), where I want to try unifying the RHS of two simultaneous lets if possible and fall through to the cases where I handle let bindings one side at a time by floating them. So, actually there's no clever structure on Maybe arguments to exploit and I'm not computeing on Int actually.

到目前为止，答案虽然可能给其他人带来了好处，但是他们给我带来的启发却无法解决，所以谢谢！！

The answers so far might benefit others beyond the enlightenment they brought me though, so thanks!

编辑2 :以下是一些可能带有虚假语义的编译示例代码:

Edit 2: Here's some compiling example code with probably bogus semantics:

module Unify (unify) where

import Control.Applicative
import Control.Monad.Trans.State.Strict

data Expr
  = Var String -- meta, free an bound vars
  | Let String Expr Expr
  -- ... more cases
  -- no Eq instance, fwiw

-- | If the two terms unify, return the most general unifier, e.g.
-- a substitution (`Map`) of meta variables for terms as association
-- list.
unify :: [String] -> Expr -> Expr -> Maybe [(String, Expr)]
unify metaVars l r = execStateT (go [] [] l r) [] -- threads the current substitution as state
  where
    go locals floats (Var x) (Var y)
      | x == y = return ()
    go locals floats (Var x) (Var y)
      | lookup x locals == Just y = return ()
    go locals floats (Var x) e
      | x `elem` metaVars = tryAddSubstitution locals floats x e
    go locals floats e (Var y)
      | y `elem` metaVars = tryAddSubstitution locals floats y e
    -- case in point:
    go locals floats (Let x lrhs lbody) (Let y rrhs rbody) = do
      go locals floats lrhs rrhs -- try this one, fail current pattern branch if rhss don't unify
      -- if we get past the last statement, commit to this branch, no matter
      -- the next statement fails or not
      go ((x,y):locals) floats lbody rbody
    -- try to float the let binding. terms mentioning a floated var might still
    -- unify with a meta var
    go locals floats (Let x rhs body) e = do
      go locals (Left (x,rhs):floats) body e
    go locals floats e (Let y rhs body) = do
      go locals (Right (y,rhs):floats) body e

    go _ _ _ _ = empty

    tryAddSubstitution = undefined -- magic

推荐答案

当我需要这样的东西时，我只需使用asum并内联代码块即可.在这里，我还将Just n1 <- pure a; Just n2 <- pure b的多个模式浓缩为(Just n1, Just n2) <- pure (a, b).

When I need something like this, I just use asum with the blocks inlined. Here I also condensed the multiple patterns Just n1 <- pure a; Just n2 <- pure b into one, (Just n1, Just n2) <- pure (a, b).

f :: Maybe Int -> Maybe Int -> StateT () Maybe ()
f a b = asum

  [ do
    (Just n1, Just n2) <- pure (a, b)
    m <- compute (n1 + n2) 
    guard (m == 42)

  , do
    Just n <- pure a
    m <- compute n
    guard (m == 42)

  , do
    Just n <- pure b
    m <- compute n
    guard (m == 42)

  ]

如果愿意，还可以使用<|>链:

You can also use chains of <|>, if you prefer:

f :: Maybe Int -> Maybe Int -> StateT () Maybe ()
f a b

  = do
    (Just n1, Just n2) <- pure (a, b)
    m <- compute (n1 + n2) 
    guard (m == 42)

  <|> do
    Just n <- pure a
    m <- compute n
    guard (m == 42)

  <|> do
    Just n <- pure b
    m <- compute n
    guard (m == 42)

对于这种失败"，这几乎是您所能获得的.

This is about as minimal as you can get for this kind of "fallthrough".

这篇关于模式匹配在“替代"中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！