Free monads

[Heinrich Apfelmus]

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