# Notes on free monads

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.

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, `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, `Update`

and `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 `manual1`

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