Megaparsec ParsecT 的状态不是回溯

Question

我有一个解析器定义为以下稍微复杂的版本：

data X = X { getX :: State ([Int], [X]) Bool }
type Parser = ParsecT Void String (State ([Int], [X]))

我的想法是，我可以建立一堆我想对我的状态（[Int]）执行的操作，然后根据情况以任何顺序或任何我想要的时间执行它们：

-- Run the first state in the list.
executeOne :: Parser Bool
executeOne = do
  s@(_, fs) <- get
  let (r, s') = (flip runState s) . getX . head $ fs
  put s'
  return r

例如，执行的动作可能会重新排序动作堆栈或修改 [Int]。

抛开设计决策（我相信有更好的方法可以做到这一点），似乎 try 的回溯不适用于状态。具体来说，ParsecT 的状态将回溯，但内部状态（[Int] 和 [X]）不会。为什么是这样？我是在滥用 ParsecT 还是奇怪的递归 X 业务把一切都搞砸了？我需要改用 Control.Monad.State.Strict 吗？

编辑：要回答评论者关于示例的问题 X，这里是：

useless :: X
useless = X $ do
  (vs, xs) <- get
  if length vs >= 10
  then do { put (vs, tail xs) ; return True }
  else do { put (vs ++ vs, xs) ; return False }

如果元素少于十个，

useless 将 [Int] 加倍，returns False。如果它确实有十个或更多元素，它会删除自己和 returns True。 X 递归的强大之处在于它可以选择在完成后是否删除自己。

Answer 1

问题出在 monad 堆栈中转换器的顺序。

通俗地说，转换器不能 "cancel" 或 "nullify" 它转换的基础 monad 的效果。例如，StateT over ExceptT 在失败时失去状态，而 ExceptT over StateT 则不会。（这也是为什么不能有一个IOT变形器的原因：如何使一个已经逃逸到世界的效果无效化？）

在这里，这意味着内部 State 将在解析器的任何回溯中幸存下来。解决方案是将 StateT 放在解析器 monad 上方，而不是下方。

这似乎需要 lift 调用所有解析器函数，因为解析器现在不是最外层的 monad。幸运的是，不需要 lift，因为 StateT s Parser 是 MonadParsec 的一个实例，它会自动提升所有解析器操作。

Megaparsec ParsecT 的状态不是回溯

State with Megaparsec ParsecT is not backtracking

monads

state

haskell

monad-transformers

megaparsec