haskell - 具有 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

例如，执行的 Action 可能会重新排列 Action 堆栈或修改 [Int] .

撇开设计决策不谈(我相信有更好的方法可以做到这一点)，似乎可以使用 try 进行回溯。不与 State 合作。具体来说，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]如果少于十个元素，则返回 False .如果它确实有十个或更多元素，它会移除自己并返回 True .拥有中的力量 X递归的是它可以选择是否在完成后删除自己。

Answer 1

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

非正式地说，转换器不能“取消”或“取消”它所转换的基础 monad 的效果。例如，StateT在 ExceptT失败时失去状态，而 ExceptT在 StateT没有。 (这也是为什么不能有IOT变压器的原因:如何抵消一个已经逃到世界的效果？)

这里的意思是内部State将在解析器的任何回溯中幸存下来。解决办法是把StateT在解析器monad之上，而不是在下面。

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