Free monads
Heinrich Apfelmus
apfelmus
Fri Oct 4 08:46:36 UTC 2013
Andres L?h wrote:
> Hi everyone.
>
> I'll follow Simon's lead, and ask a similar question with a similar
> motivation. I'm going to talk about free monads at the upcoming
> Haskell eXchange next Wednesday. I'll not limit myself to a particular
> library, and I'm open to related approaches (e.g. "operational") as
> well.
>
> I'm also looking for as many compelling examples as possible. Like
> Simon, I don't want to know anything secret or anything that you
> wouldn't like me to include in my talk. Most useful are pointers to
> existing libraries using free monads that I might have missed (for
> example, because they're new or very specialized).
I have included a couple of examples with the operational package:
<https://github.com/HeinrichApfelmus/operational/tree/master/doc/examples#readme>
My personal highlights are:
BreadthFirstParsing.hs
An implementation of parser combinators that does not have the space
leak associated to the depth-first approach s -> [(a,s)] . Instead,
parsers are evaluated in a breadth-first fashion, so that the input can
be consumed in an on-line fashion. This is equivalent to Koen Classen's
"parallel parsing processes", which I believe are used to implement the
'Text.ReadP' module.
WebSessionState.lhs
A program is written as a sequence of instructions, in this case a web
session ("shopping cart checkout"). However, unlike the code may
suggest, the program actually exits before completing and continues at
the last instruction when started. No persistent state is kept in RAM. I
learned this idea from Peter Thiemann's WASH/CGI library.
TicTacToe.hs
Similar to the previous example, but dialed up a notch. A game is
implemented using a monad that returns player input. Internally,
however, the player input can come from many sources: user, computer, or
even replays, depending on how the free monad is interpreted.
A less useful but still interesting example is `State.hs`, which
implements the state monad using only s -> a instead of s -> (a,s) .
Another example that I forgot to add when writing the package, but which
also one of my highlights, is the probability monad. Using operational,
it is possible to use the same code for both calculating complete
probability distributions and sampling from said probability distributions.
Yet another example for free monads/operational is the sunroof package
<http://hackage.haskell.org/package/sunroof-compiler>, which is an EDSL
that compiles to JavaScript. JavaScript statements are sequenced in a
monad, but the monad is then interpreted as a syntax tree ("deep
embedding").
Best regards,
Heinrich Apfelmus
--
http://apfelmus.nfshost.com
More information about the Libraries
mailing list