[Haskell] Monadic parser combinators with logging

[Andrew Pimlott]

On Wed, Aug 02, 2006 at 10:52:14AM +0200, Harald ROTTER wrote:
> newtype Parser a = Parser { runParser :: (PState -> [(a, PState)])}
> 
> as the parsing monad with the Parser state  "PState" that contains the
> remaining input after matching and possibly some additional user defined
> state elements. I want to add logging such that the application of every
> element parser/parser combinator gets recorded in a string. In the end I
> want to print out the trace of all encountered parsers for successful and
> for failed matches.
> 
> I tried to use the WriterT transformer to add a writer monad on top of the
> Parser monad but for failed matches (i.e. runParser gives []) the log is
> also "lost" since WriterT gives a monad of "m (a,w)".

Excellent observation!  The order in which you apply monad transformers
matters.  "WriterT w Parser" keeps a separate output for each branch of
the parser.  If you stare at the definition of (>>=) for WriterT, you'll
see why this must be so.  Or, as you did, you can just look at the type.

> What I would look for is "(m a, w)".

Hmm, that looks like (if m is Parser) a parser plus some output.  I
think you'd rather have an answer plus some output, ie "([(a, PState)],
w)".  Hint:  Consider

    newtype Parser m a = Parser { runParser :: (PState -> m [(a, PState)])}

where m is a Monad.

> How can I make the Parser monad given above an instance of MonadState ? (I
> always get kind errors ...)

Did you switch up the order of parameters or something?  I don't get any
error using

    instance MonadState Int Parser where ...

Andrew