These are my personal notes on David Laing’s talk Free monads are good for you - BFPG - 2014-04-22. His code and slides are available here: https://github.com/dalaing/bfpg-2014-04. My code diverges from his in that I don’t use
liftF and instead write my own definition of
Free, and my own monad instance, which follows the style in Gabriel Gonzalez’s blog post Why free monads matter. For me this made it easier to see the monad structure, mainly because I wanted to avoid the details of
liftF in Control.Monad.Free.Class.
Literate haskell source is here: https://github.com/carlohamalainen/playground/tree/master/haskell/notes-on-free-monads-are-good-for-you
Motivating example: model a data store. This could be an in-memory dictionary, an sqlite file on disk, a postgresql table, etc.
Parameterize the type by the type of the index,
i, and the type of the values,
How to read the types: for
Retrieve, an action is performed. So it’s natural that these three constructors will store a function type.
Create: we supply a value
v, and get back an index
List: we supply nothing (I guess in a more general setting we could supply a filter?) and get back a list of values.
Retrieve: We supply an index and get back a value.
On the other hand,
Delete are “in-place.” In theory we could return a list of affected indexes, so
Update could have been
Update (v -> [i]). But we’ll leave it as just
Update v. Lastly,
Delete just deletes the index/value pair, so we don’t have anything to return, so it’s not a function type.
Later we want to make our data store an instance of
Free so we need data store to be an instance of
Functor. Check the kind of
Free in ghci:
ghci> :k Free Free :: (* -> *) -> * -> *
DataStore has a concrete type. So add another parameter
k and tweak the types:
This is a bit like a continuation. Reading the types:
Create: the value
vis part of the constructor, and the last bit is a function that uses the new index
iand produces some
List: now the annoying
()has gone, and the constructor just holds the function which takes the list
[v]and does something with it, returning something of type
Retrieve: the index is stored along with the function that uses the retrieved value, returning something of type
Update: As before, but since nothing is done “to” the updated value, we can just store the value of type
Delete: similar to Update.
For the Functor instance we can use the compiler extension
DerivingInstances or we can grind through the details ourselves. It’s easy using hole-driven development because there are so few choices for each definition.
We can sequence commands manually. For example, create 3, then delete that same value, and finally return
Create 3, then create 4, then create 5, and return the triple consisting of the index values for 3, 4, and 5, respectively:
manual2 are sequences of commands, their type changes (and gets longer as more commands are added). But we can use
Free), which can be thought of as the fixed point of a functor.
Now a data store with index
v, and return type
manual2 have a succint type:
This looks suspiciously like the monad bind syntax, desugared. In fact, for any functor
f, we can write the instance for
Monad (Free f):
The function return puts a value into the monad, which uses
MkPure. The bind definition is a bit more complicated, but it can be worked out using hole driven development:
The two parameters:
MkFree constructor, poke the hole:
which results in
Couldn't match expected type `f (Free f b)' with actual type `Hole'
h which produces a
Free f b from an
x has type
f (...). So maybe
fmap will help:
Now it says:
Couldn't match expected type `Free f a -> Free f b'
Make it a function:
Which now complains:
Couldn't match expected type `Free f b' with actual type `Hole'
hole and use ghc-mod to check the type of
q. We now have these terms:
But look at the type of
>>=, it is exactly what we need now:
So plug it in and it type checks. (We have to manually verify the monad laws ourselves.)
This can also be written as
Now we can use
do notation to create a sequence of commands:
Some helper functions:
So we have a nifty little DSL!
We can write an “interpreter” that converts a series of data store commands into a string:
Notice how the
next is a function, so to print it we first apply it to the index value that we have.
List we run into a problem. We aren’t actually computing the data store, we have no way of producing an actual list to print here. So we just use the empty list as a dummy list for the parameter to ‘next’.
The rest of these are straightforward:
ghci> putStrLn $ printDataStore manual1''' Create: 3 Delete: 3 Pure value: () ghci> putStrLn $ printDataStore manual2''' Create: 3 Create: 4 Create: 5 Pure value: (3,4,5)
Make a few more helpers so we can do a longer example:
So while the value of the index for
3 passes through as
i, the list stored in
values is just the empty list as can be seen in the final value:
ghci> putStrLn $ printDataStore longExample Create: 3 Create: 4 List (dummy list): [pretend list] Retrieve: 3 Pure value: (3,)
It’s a bit like having a void back end that ignores all commands to store data and always returns an empty list.
Since this DSL is built on top of the monadic do-notation, we can use normal Haskell language features, for example if/then/else statements:
But we don’t see the if/then/else when we use
printDataStore, as it’s embedded in the monadic functions:
ghci> putStrLn $ printDataStore egLogic Create: 3 Create: 4 List (dummy list): [pretend list] Pure value: Right 
We ended up going down the
then path of the
if/then/else because our
printDataStore function uses the empty list when expanding the
Finally, here is a way to interpret the free monad and actually compute the data store, using an in-memory
ghci> runInMap M.empty egLogic (Right [3,4],fromList [(3,3),(4,4)]) ghci> runInMap (M.fromList [(10,10)]) egLogic (Left 3,fromList [(3,3),(4,4),(10,10)])
Another example, this time using
mapM in the midst of the DSL:
ghci> runInMap M.empty egLogic' ([10,11,12,13,14,15,16,17,18,19,20], fromList [(10,10),(11,11),(12,12),(13,13),(14,14),(15,15),(16,16),(17,17),(18,18),(19,19),(20,20)])