# Free Monads In Haskell

Did you know that you can actually generate a monad automatically given any endofunctor? This is the *free* monad of that functor. How do we perform this magic trick? Quite simple, everything follows from this data type:

In this, the *f* parameter is just the functor we are going to build a monad for, and *a* is the type of the contents of a *FreeM* value. We’ve said that the free monad can either contain such a value directly (boring) or it can contain a value of it’s own type, but wrapped in the functor *f* - hmm! As an aside, I’m not sure that *Bind* is strictly the best name for this constructor, but I like the symmetry.

If you want to build up some intuition about this definition, you can think of it as specifying values that consist of an actual *a* (in a *Return* constructor) but nested within a finite number of functor applications.

As another aside, you might like to know that actually Haskell would let you create an infinite stack of functors fairly straightforwardly, since all its *data* declarations are actually really co-data declarations. Don’t do this, though, or you might start having some non-termination issues :-)

Having got this far through the post, you won’t be surprised to learn that we can make this definition into a functor itself. Here comes the implementation:

That *Bind* case looks pretty scary, doesn’t it? The leftmost *fmap* call is that from the functor *f* that we are making a free monad over, and the rightmost one is actually a recursion back into the *fmap* we are currently trying to compute, but one functor “lower”.

Essentially all we are doing in this definition is *fmap_ing all the way down our tower of functors until we finally reach a nice sane _a* value in the *Return* case, which we handle in the obvious way.

So far so good. But we’ve come all this way and **still** don’t have a monad, even though I promised you one at the start. Well, let’s sort that out now! Instead of defining one using the usual Haskell *»=* operator, I’m going to use the more category-theoretical *join :: Monad m => m (m a) -> m a* construction:

If you think about the type of this operation, what we want to do is stick the pile of functors associated with the outermost *FreeM* onto the pile of functors associated with the innermost one, to produce one cohesive functor pile. How we go about this is fairly straightforward: in the *Return* case there are no functor applications on the outermost *FreeM* so we just give back the inner one. The *Bind* case simply recurses its way down the whole functor pile, mushing them together in some sense :-).

That was it. The code to actually declare a *Monad* instance is entirely boilerplate given that we have a *join* operation:

Pretty neat! But what, pray tell, are these things actually useful for? Well, after I’d implemented my own version of free monads I found that Wouter Swierstra’s excellent paper “Data types à la carte” had already publicly demonstrated the same thing (in passing) with his *Term* data structure, and he has some nice examples. For instance, consider this functor:

Remind you of anything? It should: it’s just the *Maybe* monad!

What about this?

Something like the identity monad: pretty boring! What if we try something a bit more exotic (and not mentioned in Wouter’s paper) like the list functor?

But for want to a call to *concat*, this looks strikingly similar to the list monad - and all without ever having to define it. Interesting stuff!

I’ve found that the fun of free monads is that you can play around with any functor you like and get something interesting generated from it. Since they’re free, this happens without you typing a single line of non-trivial code, so I encourage you to go and try a few out quickly and see what you can make happen!