{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-}
module StatefulParsing where
import Control.Monad.State.Class
import Control.Applicative

In this post I propose an extension to the monadic parser framework introduced in a previous post, You could have invented Parsec, that extends the parser to also support embedded user state in your parsing.

This could be used, for example, for parsing a language with user-extensible operators: The precedences and fixidities of operators would be kept in a hashmap threaded along the bind chain.

Instead of posing these changes as diffs, we will rewrite the parser framework from scratch with the updated type.

Parser newtype

Our new parser is polymorphic in both the return type and the user state that, so we have to update the newtype declaration to match.

newtype Parser state result
   = Parser { runParser :: String
                        -> state
                        -> Either String (result, state, String) }

Our tuple now contains the result of the parsing operation and the new user state, along with the stream. We still need to supply a stream to parse, and now also supply the initial state. This will be reflected in our functions.

For convenience, we also make a Parser' a type alias for parsers with no user state.

type Parser' a = Parser () a

Seeing as type constructors are also curried, we can apply η-reduction to get the following, which is what we’ll go with.

type Parser' = Parser ()

Functor instance

instance Functor (Parser st) where

The functor instance remains mostly the same, except now we have to thread the user state around, too.

The instance head also changes to fit the kind signature of the Functor typeclass. Since user state can not change from fmapping, this is fine.

  fn `fmap` (Parser p) = Parser go where
     go st us = case p st us of
          Left e -> Left e
          Right (r, us', st') -> Right (fn r, us', st')

As you can see, the new user state (us') is just returned as is.

Applicative instance

instance Applicative (Parser st) where

The new implementations of pure and <*> need to correctly manipulate the user state. In the case of pure, it’s just passed as-is to the Right constructor.

  pure ret = Parser go where
    go st us = Right (ret, us, st)

Since (<*>) needs to evaluate both sides before applying the function, we need to pass the right-hand side’s generated user state to the right-hand side for evaluation.

  (Parser f) <*> (Parser v) = Parser go where
    go st us = case f st us of
      Left e -> Left e
      Right (fn, us', st') -> case v st' us' of
        Left e -> Left e
        Right (vl, us'', st'') -> Right (fn vl, us'', st'')

Monad instance

instance Monad (Parser st) where

Since we already have an implementation of pure from the Applicative instance, we don’t need to worry about an implementation of return.

  return = pure

The monad instance is much like the existing monad instance, except now we have to give the updated parser state to the new computation.

  (Parser p) >>= f = Parser go where
    go s u = case p s u of
        Left e -> Left e
        Right (x, u', s') -> runParser (f x) s' u'

MonadState instance

instance MonadState st (Parser st) where

Since we now have a state transformer in the parser, we can make it an instance of the MTL’s MonadState class.

The implementation of put must return () (the unit value), and needs to replace the existing state with the supplied one. This operation can not fail.

Since this is a parsing framework, we also need to define how the stream is going to be affected: In this case, it isn’t.

  put us' = Parser go where
    go st _ = Right ((), us', st)

The get function returns the current user state, and leaves it untouched. This operation also does not fail.

  get = Parser go where
    go st us = Right (us, us, st)

Since we’re an instance of MonadState, we needn’t an implementation of modify and friends - They’re given by the MTL.

Alternative instance

instance Alternative (Parser st) where

The Alternative instance uses the same state as it was given for trying the next parse.

The empty parser just fails unconditionally.

  empty = Parser go where
    go _ _ = Left "empty parser"

(<|>) will try both parsers in order, reusing both the state and the stream.

  (Parser p) <|> (Parser q) = Parser go where
    go st us = case p st us of
      Left e -> q st us
      Right v -> Right v

Conclusion

This was a relatively short post. This is because many of the convenience functions defined in the previous post also work with this parser framework, if you replace Parser with Parser'. You can now use get, put and modify to work on the parser’s user state. As a closing note, a convenience function for running parsers with no state is given.

parse :: Parser' a -> String -> Either String a
parse str = case runParser str () of
  Left e -> Left e
  Right (x, _, _) -> x