在 Monad Transformer 中回溯底层 monad

Question

作为一个副项目，我正在努力实现我自己的 Regex parser/compiler。

我认为实际匹配部分是了解一些回溯 monad 工作原理的好时机；例如列表 monad。

我最终构建了我的 'match' 算法，如下所示：

data Expr
  = Group Int Expr
  | Terms [Expr]
  | OneOf [Expr]
  | Repetition Expr Int (Maybe Int)
  | Empty
  | BackRef Int
  | Wildcard
  | Atom Char
  | Start
  | End
  deriving (Show)

data RState = RState
  { groups :: Groups
  , leftover :: String
  } deriving Show

match :: Expr -> ListT (State RState) String

其中 ListT 来自 Gabriel 的 List.Transformer lib

State monad 部分跟踪已捕获的组（以便我在匹配反向引用时可以使用它们）和剩余的字符串供使用。 Expr 是一种数据结构，将正则表达式表示为某种 AST。

无论如何；这很好用；我递归尝试进行匹配，如果匹配成功我 return 结果是匹配的部分并相应地改变状态中的剩菜和组，这最终在非确定性中工作，因为它会继续尝试继续使用所有尝试处理正则表达式的下一部分时可能的先前匹配项。问题是它只回溯到以前的结果，而不是回到以前的状态！结果，我的 alternative 匹配正则表达式中可选链的匹配代码（例如 a|b*|c；其中每个部分都是 'term'）如下所示：

match (OneOf terms) = do
  st <- get
  -- Backtrack the state and try again on each alternative
  let try t = put st >> match t
  asum (try <$> terms)

基本上我尝试匹配每一项，但即使匹配失败它仍然会改变状态！所以我需要在失败之间手动倒回状态。这是由于 <|>:

的 ListT 实现

ListT m <|> l = ListT (do
    s <- m
    case s of
        Nil       -> next l
        Cons x l' -> return (Cons x (l' <|> l)) )

我们看到它运行底层 monad 并在相同的上下文中继续。

我想要类似这样的东西：

ListT m <|> l = ListT (do
    st <- get
    s <- m
    case s of
        Nil       -> put st >> next l
        Cons x l' -> return (Cons x (l' <|> l)) )

... 但是对于一般的所有 monad 效果；我什至不确定这是否可能。

我将 Logic Monad 作为一种可能的解决方案进行了研究，但即使在阅读了这篇论文之后，我也无法确定它是否可以满足我的要求，也许可以使用 ifte？

是否有一个回溯monad，它不仅可以回溯monad的结果，还可以回溯monadic的计算？我想这对于像 IO 这样的东西是不可能的，但理论上对于纯 monad 应该是可能的吗？我想这意味着它通常是不可能的，但是有没有一种类型-class我可以实施以获得我的案例的这个功能？

谢谢！我知道我在这里大声说话，感谢您帮助我思考这个问题！

Answer 1

解决方案是按照@danidiaz 的建议反转堆栈。

我发现记住外部 monad 变换器受内部变换器的支配是有帮助的。因此，无论 SomeMonadT 做什么，SomeMonadT (State s) 的状态都是 "single-threaded"。

一个有启发性的例子是将 StateT monad 转换器展开到其他一些 monad 上。假设我们有：

foo :: StateT S M A
bar :: StateT S M B

do a <- foo
   b <- bar
   return (a,b)

这只是一种奇特的写法：

foo :: S -> M (A, S)
bar :: S -> M (B, S)

\s1 -> do 
    (a,s2) <- foo s1
    (b,s3) <- bar s2
    return ((a,b),s3)

这是激发 State monad 的熟悉模式，只是该模式发生在另一个 monadic 上下文中。上下文为王，转换器对此无能为力。

这意味着ListT (State s)是一个跟踪一个状态s的计算，然后在上面定义了一些"sugar"通过 ListT。您可以将其视为有状态机器（仅具有跟踪单个状态的能力）中不确定性的实现。

而 StateT s [] 是一种本质上不确定的计算，然后有一些 "sugar" 可以模拟状态。底层机器是一个非确定性回溯机器，然后转换器使用编码模式在该机器上模拟状态。

这是丹·皮波尼 (Dan Piponi) 的 diagram，有助于提供一些直觉：

这是一个有点虚幻和直觉的领域，所以我希望这对您有所帮助。

进一步阅读：How to design a monadic stack?

在 Monad Transformer 中回溯底层 monad

Backtrack over underlying monad in Monad Transformer

haskell

backtracking

monad-transformers