# Monadic Parsing with User State

```
{-# 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.

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

`Functor`

instance

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

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.

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

Since we already have an implementation of `pure`

from the Applicative instance, we don’t need to worry about an implementation of `return`

.

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

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.

The `get`

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

Since we’re an instance of `MonadState`

, we needn’t an implementation of `modify`

and friends - They’re given by the MTL.

`Alternative`

instance

The `Alternative`

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

The `empty`

parser just fails unconditionally.

`(<|>)`

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.