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:
data FreeM f a = Return a
| Bind (f (FreeM f a))
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:
instance (Functor f) => Functor (FreeM f) where
fmap f (Return a) = Return (f a)
fmap f (Bind fm) = Bind (fmap (fmap f) fm)
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 fmaping 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:
joinFreeM (Return a) = a
joinFreeM (Bind fm) = Bind (fmap joinFreeM fm)
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:
instance (Functor f) => Monad (FreeM f) where
return = Return
m >>= f = joinFreeM ((fmap f) m)
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:
data Zero a = Zero
deriving (Show)
instance Functor Zero where
fmap _ Zero = Zero
zeroTest my = do
x <- return 5
y <- my
return $ x + y
-- > zeroTest (return 1)
-- 6
-- > zeroTest (Bind Zero)
-- Zero
Remind you of anything? It should: it's just the Maybe monad!
What about this?
data One a = One a
deriving (Show)
instance Functor One where
fmap f (One a) = One (f a)
oneTest my = do
x <- return 5
y <- my
return $ x + y
-- > oneTest (Return 2)
-- 7
-- > oneTest (Bind $ One $ Return 2)
-- One 7
-- > oneTest (Bind $ One $ Bind $ One $ Return 2)
-- One One 7
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?
listTest = do
x <- Bind [Return 1, Return 2]
y <- Bind [Return 3, Return 4]
return $ x + y
-- > listTest
-- [[4,5],[5,6]]
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!
