Well, it’s been too long since my last post. A combination of things personal and professional have consumed my time. I’d intended for my next post to be about my project to port Clojure to the LLVM compiler. That will happen soon, but I want to get some thoughts down about Free Monads in Clojure. As is usually the case, this is more about me crystallizing my understanding of a concept and putting it down so I can refer to it later.

The code for this post is in a new github repo I’m working that you can find here. This is very much a work in progress where I’m investigating how to combine monads, comonads, arrows and the like. Use at your own risk.

For some other perspectives on Free Monads, this is a great post and this Stackoverflow question has some great thoughts about Free monads in Clojure.

### What is a Free Monad

I’m not quite clear on what the meaning of ‘Free’ is in Category Theory, but what I’ve read states that a Free monad is a monad that has the absolute minimum structure. What this means practically can be understood by considering what the requirements are for for a monad. A monad is a data type that implements two protocol functions.

``````(defprotocol Applicative
(wrap [x v]))

(flat-map [mval func]))
``````

The `wrap` function wraps any value in the same monad context of ‘x’. It’s often referred to as `result` or `return` in the monad literature. And the `flat-map` function is how you apply a function to a monadic value `mval`. It’s often called `bind`. The structure of the monad is embedded in the way `wrap` and `flat-map` work. So the Free monad has the simplest implementations of these functions possible. So the first thing we need, is a data type that just wraps plain values but does nothing else to them and also implements `wrap` and `flat-map`.

``````(deftype Pure [v]
Applicative
(wrap [_ v]
(Pure. v))

(flat-map [ev f]
(f v))

(extract [_] v))
``````

The `extract` function just unwraps the value.

It doesn’t take much working with these Pure values to realise that they don’t allow you to do anything that plain values don’t. So there’s not really enough structure there to properly call it a monad. It turns out, we need something like this:

``````(deftype Free [val]
Applicative
(wrap [_ v]
(Pure. v))

(flat-map [_ f]
(Free. (fmap val #(flat-map % f))))

(extract [_] val))
``````

This is the data type that generates a monad out of a value of a data type that implements `fmap`. The idea is that you have to have ‘some’ structure and a data type with the `fmap` function is the bare minimum. And notice that the implementation of `flat-map` makes a recursive call to itself. This is the reason you also need the Pure data type because it serves to ‘bottom out’ the recursion. And that’s all you need for the Free monad.

### Functors

But what’s that call to `fmap`? Well, all monad data types are a subset of the endofunctor data types. (Often times, people will just say “functor” when they mean “endofunctor” which is really confusing.) This means that, given any monad, you can automatically write an implemenation for `fmap` in terms of `wrap` and `flat-map`.

``````(defn monad-fmap [mval func]
(flat-map mval #(wrap mval (f %))))
``````

And `fmap` is just a protocol function that knows how to apply a pure function to a value that has some structure while preserving that structure.

``````(defprotocol EndoFunctor
(fmap [v f]))
``````

So an endofunctor provides just enough structure to allow it to be converted into a monad using the Free data type which serves as sort of a wrapper for the endofunctor values. Endofunctors can be thought of as encapsulating plain values and so you wrap those values in the Pure data type and you’re good to go.

There are a couple of major benefits to monads in general. One is that you get an embedded DSL with no additional work using ‘do-notation’. In the Clojure world, this is a more generalized form of the `for` list comprehension notation. In my effects repo, I define a `for` macro that works with any monad that implements `wrap`/`flat-map`.

And since the free monad works for any endofunctor value, you can compose the functionality of different endofunctors by simply wrapping their values in Free. So, what does this look like? The real payoff comes when you realize that the free monad does nothing more than build a data structure which can be used in different ways by different interpreter functions.

(This example is taken from the Haskell For All post I mentioned up above.)

So lets say you want to implement a simple language with 3 operations; output a value, ring a bell or end the program. The output and bell ringer also need to be linked other operations that follow them while the program-ending command doesn’t.

The output operation needs to take two parameters, the value to output and the rest of the program:

``````(deftype Output [b next]
EndoFunctor
(fmap [_ f]
(Output. b (f next)))

(extract [_] [b next]))
``````

`Output`’s `fmap` function just applies `f` to the rest of the program.

``````(deftype Bell [next]
EndoFunctor
(fmap [_ f]
(Bell. (f next)))

(extract [_] next))

(deftype Done []
EndoFunctor
(fmap [_ _]
(Done.)))
``````

Pretty simple, huh? There’s almost nothing to this code. So what do you do with it? Well, you can write programs in this language. But first, we want some helper functions to keep from writing a lot of boiler plate.

``````(defn output [x] (liftF (Output. x nil)))
(def bell (liftF (Bell. nil)))
(def done (liftF (Done.)))
``````

where ‘liftF’ is defined like:

``````(defn liftF [f-val]
(Free. (fmap f-val (fn [x] (Pure. x)))))
``````

With all that in hand, here’s a simple subroutine in this language;

``````(def subr (for [_ (output :a)
_ (output :b)]
8))
``````

It just outputs an `:a`, then a `:b` and returns a value of `8`, which we’re going to end up ignoring.

This subroutine can then be used in program like this:

``````(def prog (for [v subr
_ bell
_ done]
nil))
``````

The value that actually get’s bound to `prog` is just a data structure. To actually do anything with it, we need to extend our basic operations with another protocol function.

``````(defprotocol ShowProg
(show [_]))

(extend-type Output
ShowProg
(show [ev]
(let [[v x] (extract ev)]
(str "output " v \newline (show x)))))

(extend-type Bell
ShowProg
(show [ev]
(let [x (extract ev)]
(str "bell" \newline (show x)))))

(extend-type Done
ShowProg
(show [ev]
(str "done" \newline)))

(extend-type Pure
ShowProg
(show [ev]
(str "return" (extract ev) \newline)))

(extend-type Free
ShowProg
(show [ev]
(show (extract ev))))
``````

The `show` function just converts the respective data value types to strings. You also have to extend `Pure` and `Free`. And now running

``````(print (show prog))
=>
output :a
output :b
bell
done
``````

Pretty printing is just one way to interpret a program in this toy language. You could compile it, execute it, produce a graphical representation, etc. It all just depends on what kind of interpreter you want to write.

### The rest of the story

That’s about as much of Free Monads as I currently understand. I’ve seen references to the fact that there are large performance improvements that can be gained with a different implementation. I also need to read up on Free Monad Transformers. And then, since every comonad is also an endofunctor, what does a Free monad wrapping a comonad look like? Further still is the whole domain of cofree comonads. There’s so very much to learn.

12 April 2014