State with Megaparsec ParsecT is not backtracking

Question

I have a parser defined as a slightly more complicated version of the following:

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

The idea is that I can build up a stack of actions I want to do to my state (the [Int]) and then execute them in any order or whenever I want, depending on the circumstances:

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

For example, the action executed may reorder the stack of actions or modify the [Int].

Design decisions aside (I'm sure there are better ways to do this), it seems that backtracking with try is not working with the state. Specifically, the state of the ParsecT will backtrack, but the inner state (the [Int] and [X]) won't. Why is this? Am I misusing ParsecT or is the strange recursive X business screwing everything over? Do I need to use Control.Monad.State.Strict instead?

Edit: To answer a commenter's question about an example X, here's one:

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 doubles our [Int] if it has less than ten elements, and returns False. If it does have ten or more elements, it removes itself and returns True. The power in having X be recursive is that it can choose whether or not to remove itself after it's done.

It has to do with the ordering of the monad stack. A monad transformer can't "undo" an effect performed by monads below it. You could try putting a `StateT` transformer above the `Parser` monad. You won't have to perform any lifts because there is a `MonadParsec e s m => MonadParsec e s (StateT st m)` instance. — danidiaz, Feb 10 '19 at 22:18
Tangential question: why have you defined an infinitely recursive state type? If you expand the newtypes, you get that `X` is `State ([Int], [State ([Int], [State ([Int], ...)])])`. What purpose does this type serve? — bradrn, Feb 10 '19 at 22:19
@bradrn I don't know the ultimate reason, but it seems to be the rule. For example, `StateT` over `ExceptT` loses its state on failure, while `ExceptT` over `StateT` doesn't. `ListT` over `StateT` has its state shared across all search branches, while `StateT` over `ListT` has a different state for each branch. — danidiaz, Feb 10 '19 at 22:22
@danidiaz I think that's because monad transformers work 'inside out', so e.g. an `ExceptT a (ExceptT b Identity) x` is equivalent to an `Either b (Either a x)`. I've always wondered why that is, although my question https://stackoverflow.com/q/49587122/7345298 may help. — bradrn, Feb 10 '19 at 22:47
Related question: https://stackoverflow.com/q/27835214/637669 — arrowd, Feb 11 '19 at 06:33
@bradrn Think of `X` like an action that can be performed on my state. I can make a list of actions, then run the top one with `executeOne`. The thing is, I want an `X` to have control over the `[X]` inside the parser state - for example, a specific `X` might not remove itself from the list until the `[Int]` is a specific length, or it might throw away some actions below it in the list if the head of `[Int]` is negative (just random examples). It provides the most freedom as they have 100% full control over the state. — otah007, Feb 11 '19 at 20:31
@otah007 It's starting to make sense to me, but I still don't entirely understand. Could you give me a small example of a value of type `X`? — bradrn, Feb 11 '19 at 20:46
@danidiaz, this is indeed a very interesting question in general. I strongly suspect the a answer will relate to the general nature of functions used to "run" computations in transformed monads. But I don't know how to formalize the question, let alone answer it! — dfeuer, Feb 11 '19 at 22:44
@danidiaz I think I've been misunderstanding the instances of `MonadParsec` - I knew `StateT` was an instance but I had it backward. Just to make sure, `MonadParsec e s m` guarantees backtracking via `try` for `StateT st m`, and in this case we want `m = ParsecT...`. But because `ParsecT` is not an instance of `MonadParsec`, the monad `ParsecT e s (StateT...` won't backtrack the inner `m`, that is, the inner `StateT...`. Is that correct? — otah007, Feb 11 '19 at 22:57
@otah007 That example makes sense. Personally I would have defined `newtype X = X { getX :: ([Int], [X]) -> ([Int], [X], Bool) }`, so getting rid of the confusing recursive `State` definition, but it doesn't really make much difference. Also as for your previous comment I'm pretty sure that `ParsecT` is an instance of `MonadParsec`. — bradrn, Feb 11 '19 at 23:12
@otah007 `ParsecT` is an instance of `MonadParsec`. `MonadParsec` is a convenience, it helps you avoid having to sprinkle your code with `lift`s when there's a transformer above `ParsecT`. It doesn't care about transformers below `ParsecT`. `StateT` above `ParsecT` happens to have the backtracking behaviour you need, and also happens to have a `MonadParsec` instance. — danidiaz, Feb 12 '19 at 06:38
@danidiaz If you add that as an answer then I can accept it. — otah007, Feb 13 '19 at 20:25

score 1 · Accepted Answer · answered Feb 13 '19 at 23:19

The problem was the order of the transformers in the monad stack.

Informally speaking, a transformer can't "cancel" or "nullify" the effects of the base monad it transforms. For example, StateT over ExceptT loses its state on failure, while ExceptT over StateT doesn't. (This is also the reason why there can't be an IOT transformer: how to nullify a effect that has already escaped into the world?)

Here, it means that the inner State will survive any backtracking of the parser. The solution is to put StateT above the parser monad, not below.

This would seem to require lift calls for all the parser functions, because the parser is not the outermost monad now. Fortunately, the lifts aren't needed because StateT s Parser is an instance of MonadParsec, which auto-lifts all parser operations.

State with Megaparsec ParsecT is not backtracking

1 Answers1