[Haskell-cafe] Parsers are monadic?

[jerzy.karczmarczuk at info.unicaen.fr]

Big Chris writes to Gregory, who posts:
> 
>> ... 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. /.../

To make it shorter. The first usage of monads in parsing was *not* related
to IO, but to the non-determinism of top-down parsers, the usage of
lazy lists to store the possible partial parses (and to signal the possible
ambiguities). People who used (or taught) this strategy using before, say,
Prolog, found it remarkably clear. 

The standard, naïve approach to monadic parsing is very nice, but
inefficient. So *please read* some material based on Hutton&Meijer
approach, but don't stay there, read something more modern, for example
the PARSEC business 

http://legacy.cs.uu.nl/daan/download/papers/parsec-paper-letter.pdf
http://research.microsoft.com/~emeijer/Papers/Parsec.pdf 

and also find out a bit about the arrow formalism, as present within
the Swierstra & Duponcheel approach to parsing (they, themselves didn't
use arrows, but they inspired John Hughes. Unless I am confusing things
because of my age...).
Anyway, concerning what Big Chris calls a "more general concept":
don't be confused, the parsing strategy of S&D is *NOT* monadic.
Thera are arrows which are monadic, and others which are not. 

http://www.cs.uu.nl/people/doaitse/Papers/1996/DetErrCorrComPars.pdf 

== 

Jerzy Karczmarczuk