[Haskell-cafe] Parsers are monadic?

[Philippa Cowderoy]

On Sat, 30 Jun 2007, Claus Reinke wrote:

> for all that i like monadic programming in general, i often feel
> that it is biased towards handling only the success path well,
> by offering built-in support for a single continuation only.

Certainly one path gets privileged over the others, I don't know I'd go so 
far as saying none get treated well though.

> for
> instance, one can use (Either String) as a parser monad with
> error messages, but it isn't straightforward to express error
> handling into that format, preserving both success and failure-
> related info (such as reporting the error corresponding to the
> longest partially successful parse). also, negation does not
> seem to be an easy fit (succeed if a specific parser would
> not be successful at the current point; this seems to require
> monad-specific information, so perhaps there's a
> MonadNegate class missing?).
> 

Have you used Parsec? The error model is not quite as general as it could 
be (hmm, perhaps this might be worth a day's hacking for Paolo as part of 
SoC if he's interested?) but it's certainly suitably compositional and I 
could start sketching out how to generalise it easily enough. Negation 
pretty much just works. The paper linked to elsethread explains the 
mechanisms reasonably well IMO.

> has anyone else had similar experiences with expressive limitations
> of monadic programming? things that one might be able to work
> around, but that don't feel as natural or simple as they should be?
> things that one hasn't been able to express at all (such as Swierstra
> & Duponcheel's static analysis of combinator parsers which
> inspired Hughes's proposal to use arrows)?
> 

The big gain with arrows is those situations where higher-order 
computations can't be allowed - that's exactly the restriction that makes 
S&D-style parsers work. You can even pull my favourite AST-and-interpreter 
implementation off again, with the static analysis taking a similar role 
to the interpreter (but also called /by/ the interpreter).

-- 
flippa at flippac.org

Performance anxiety leads to premature optimisation