在Monad Transformer中回溯基础monad

Question

作为一个副业项目，我正在实现自己的正则表达式解析器/编译器。

我认为实际匹配部分是学习一些回溯单子的好时机；比如列表单子。

最终，我将我的“匹配”算法结构化如下：

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库

State单子部分跟踪已捕获的组(以便在回溯引用时使用)和剩余要消费的字符串。Expr是一种表示正则表达式的数据结构，类似于AST。

总之，这很有效；我会不断递归尝试匹配，如果匹配成功，我将匹配部分作为结果返回，并相应地更改状态中的剩余部分和组，这最终在非确定性中起作用，因为它将继续尝试使用所有可能的先前匹配项在尝试处理regex的下一部分时。问题是它仅在先前结果上回溯，但不会回溯到先前的状态！因此，我的匹配代码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)) )

我们看到它在运行基础单子并在相同的上下文中继续。

我想要类似于这样的东西：

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)) )

...但对于所有的单子效应，我甚至不确定这是否可能。

我研究了逻辑单子作为一种可能的解决方案，但即使在阅读论文之后，我也无法确定它是否能够实现我想要的，也许可以使用ifte？

是否有一种回溯单子，不仅可以回溯单子的结果，而且还可以回溯单子计算？我想这对于像IO这样的东西是不可能的，但从理论上讲，对于纯单子来说是可能的。我想这意味着它在一般情况下是不可能的，但是否有一种类型类可以实现这个功能以满足我的需求？

谢谢！我知道我在这里胡言乱语，感谢你帮我思考这个问题！

- Chris Penner

---

你尝试过反转单子栈吗？在 StateT RState [] String 中工作。这样每个分支应该有自己的状态。在 ListT (State RState) String 栈中，状态在分支之间是共享的，正如你所发现的那样。 - danidiaz

这是不可能的。如果底层的单子是 IO，用户执行了 launchNuclearMissiles china，你会取消对中国的导弹发射吗？ - user253751

Answer 1

解决方案是倒置堆栈，正如@danidiaz所建议的那样。

我发现记住外部单子变换器受内部单子变换器支配很有帮助。所以SomeMonadT (State s)将在其状态性中是“单线程”的，无论SomeMonadT做什么。

一个启示性的例子是在某些其他单子上展开StateT单子变换器。假设我们有：

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)

除了该模式在另一个单子上下文中发生，这是激励“状态”单子的熟悉模式。那个上下文是王者，变压器无能为力。

这意味着“ListT（State s）”是跟踪一个状态“s”的计算，并且顶部有一些“糖”，由“ListT”定义。您可以将其视为在具有仅能跟踪单个状态的有状态机中实现非确定性的方法。

而“StateT s []”是本质上不确定的计算，然后有一些“糖”来模拟状态。底层机器是不确定的回溯机器，然后变压器使用编码模式在该机器上模拟状态。

这是Dan Piponi的diagram，可以帮助提供一些直觉：

这是一些模糊和直觉感受的领域，希望这有所帮助。

进一步阅读：如何设计单子栈？

- luqui

---

这篇文章中的涂鸦 http://blog.sigfpe.com/2006/10/monads-field-guide.html 实际上为 ListT (State s) 的“单线程状态性”提供了很好的直觉。StateT s [] 的涂鸦缺失了，但它应该是一个与 [] 分支“分叉”的状态。 - danidiaz

@danidiaz，谢谢！我记得这个，但不够找到它。 - luqui