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

如果Qazxswpoi少于十个元素，useless将我们的[Int]加倍，并返回False。如果它确实有十个或更多元素，它将自行删除并返回True。让X递归的能力是它可以选择是否在完成后自行删除。

Answer 1

问题是monad堆栈中变换器的顺序。

非正式地说，变压器不能“取消”或“无效”它转换的基础monad的效果。例如，StateT在ExceptT失败后失去状态，而ExceptT在StateT失败。 （这也是为什么不能有IOT变换器的原因：如何使已经逃逸到世界的效果无效？）

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

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