haskell - Why does ParsecT type have 'u' argument?

Question

Documentation for the parsec package states that u argument is used to carry some user state through monadic computation. But the same functionality can be achieved by basing ParsecT monad transformer on State monad. So if my parser is not stateful, i don't need u altogether, but have to set it to () with parsec. What's rationale for adding non-optional state support to ParsecT?

Answer 1

Because a parser of type ParsecT s () (State st) a behaves differently from a parser of type Parsec s st Identity a when it comes to backtracking:

• User state resets when parsec tries an alternative after a failing parse that consumes no input.
• But the underlying Monad m does not backtrack; all the effects that happened on the way to a final parse result are kept.

Consider the following example:

{-# LANGUAGE FlexibleContexts #-}
module Foo where

import Control.Applicative
import Control.Monad.State
import Text.Parsec.Prim hiding ((<|>), State(..))
import Text.Parsec.Error (ParseError)

tick :: MonadState Int m => ParsecT s Int m ()
tick = do
  lift $ modify (+1)
  modifyState (+1)

tickTock :: MonadState Int m => ParsecT s Int m ()
tickTock = (tick >> empty) <|> tick

-- | run a parser that has both user state and an underlying state monad.
--
-- Example:
-- >>> run tickTock
-- (Right 1,2)
run :: ParsecT String Int (State Int) () -> (Either ParseError Int, Int)
run m = runState (runParserT (m >> getState) initUserState "-" "") initStateState
  where initUserState = 0
        initStateState = 0

As you can see, the underlying state monad registered two ticks (from both alternatives that were tried), while the user state of the Parsec monad transformer only kept the successful one.