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.
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]))
(defprotocol Monad
(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))
Monad
(flat-map [ev f]
(f v))
Comonad
(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))
Monad
(flat-map [_ f]
(Free. (fmap val #(flat-map % f))))
Comonad
(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.
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)))
Comonad
(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)))
Comonad
(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.
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.
Jim Duey 12 April 2014