[Haskell-cafe] Could someone teach me why we use Data.Monoid?

[Edward Kmett]

2009/11/15 Eugene Kirpichov <ekirpichov at gmail.com>

> Hey, I've found terrific slides about monoids!
>
> http://comonad.com/reader/wp-content/uploads/2009/08/IntroductionToMonoids.pdf
> Edward Kmett, you rock!
>

Glad you enjoyed the slides. =)


> There's more http://comonad.com/reader/2009/iteratees-parsec-and-monoid/
> - but the second part was too hard for me to read it fully without
> special motivation.
>

The iteratees, parsec and monoids talk was mostly to solve a technical
problem of my own. The result is a way to build parallel parsers that works
quite well for most practical programming language grammars, but requires
you to think about parsing a bit sideways and requires a lot of machinery
from other areas to make work.

In essence I rely on the fact that in programming languages we typically
have a point at which we can resume parsing, or at least lexing, in a
context-free manner by locating global invariants of the grammar.

These invariants are typically already present and are used to provide error
productions in real world compiler grammars, so that the compiler can try to
resume parsing. It is a hack, but it is a reasonably efficient hack. =)

To make it work, I have to borrow a lot of machinery from other areas.
Iteratees give me a resumable parser, giving that access to its input
history lets it backtrack, which lets me bolt them onto parsec, so you can
write parsers the way you are used to, at least for the tokens in your
language, and then you add a layer on top to deal with the token-stream,
which is now available to be reduced monoidally rather than just
sequentially.

What I was looking for was a good understanding of what invariants would it
make sense to design a language to have so that it could be efficiently
parsed in parallel and incrementally reparsed as the user types without
having to rescan the whole source file.

-Edward Kmett
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20091116/0b51a469/attachment.html