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 wrap and liftF in Control.Monad.Free.Class.

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, v.

How to read the types: for Create, List, and 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 i.
• 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, Updateand 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 :: (* -> *) -> * -> *


However our 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 v is part of the constructor, and the last bit is a function that uses the new index i and produces some k.
• 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 k.
• Retrieve: the index is stored along with the function that uses the retrieved value, returning something of type k.
• Update: As before, but since nothing is done “to” the updated value, we can just store the value of type k.
• 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:

Even though manual1 and manual2 are sequences of commands, their type changes (and gets longer as more commands are added). But we can use Fix (or Free), which can be thought of as the fixed point of a functor.

Now a data store with index i, key v, and return type r:

Now manual1and 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:

Use the MkFree constructor, poke the hole:

which results in

Couldn't match expected type f (Free f b)' with actual type Hole'


We have h which produces a Free f b from an a but 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'


Temporarily turn Hole into 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.

With 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:

Some examples:

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 List case.

Finally, here is a way to interpret the free monad and actually compute the data store, using an in-memory Map:

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)])
`