[Haskell-cafe] Parsers are monadic?

Big Chris ccasingh at andrew.cmu.edu
Sat Jun 30 02:01:14 EDT 2007


Hi Gregory,

> First post.  I'm a newbie, been using Haskell for about a week and
> love it.  Anyway, this is something I don't understand.  Parsers are
> monadic.  I can see this if the parser is reading from an input stream
> but if there's just a block of text can't you just have the parser
> call itself recursively feeding the unparsed text down the recursion
> and tacking nodes onto the tree as the recursions return, finally
> returning the whole tree to the top level caller.  Seems this meets
> the criteria for pure functionality, same result every time with same
> args.

   Your intuition is right - it's definitely possible to write a parser
without using a monad.  However, some experience has shown that the
most convenient way to structure a recursive descent parser library is
with monads (or maybe with arrows, a more general concept).

   I imagine your suspicion is the result of equating monads with
effects.  Monads serve many purposes besides dealing with effects
elegantly.  Many new haskell hackers get their first taste of monads
with IO, and get the impression that this is the One True Purpose
of monadic programming.

   You might want to have a look at the paper Monadic Parser Combinators
by Graham Hutton and Erik Meijer.  This paper serves as a great
introduction to both parser combinators and monads, and shows how
they are related:

http://www.cs.nott.ac.uk/~gmh/bib.html#monparsing

The first 10 or 12 pages are particularly helpful in figuring out
why monads make sense in parsing.  Good luck!

--Chris


More information about the Haskell-Cafe mailing list