What are free monads?

Question

I've seen the term Free Monad pop up every now and then for some time, but everyone just seems to use/discuss them without giving an explanation of what they are. So: what are free monads? (I'd say I'm familiar with monads and the Haskell basics, but have only a very rough knowledge of category theory.)

Answer 1

Edward Kmett's answer is obviously great. But, it is a bit technical. Here is a perhaps more accessible explanation.

Free monads are just a general way of turning functors into monads. That is, given any functor f Free f is a monad. This would not be very useful, except you get a pair of functions

liftFree :: Functor f => f a -> Free f a
foldFree :: Functor f => (f r -> r) -> Free f r -> r

the first of these lets you "get into" your monad, and the second one gives you a way to "get out" of it.

More generally, if X is a Y with some extra stuff P, then a "free X" is a a way of getting from a Y to an X without gaining anything extra.

Examples: a monoid (X) is a set (Y) with extra structure (P) that basically says it has an operation (you can think of addition) and some identity (like zero).

So

class Monoid m where
   mempty  :: m
   mappend :: m -> m -> m

Now, we all know lists

data [a] = [] | a : [a]

Well, given any type t we know that [t] is a monoid

instance Monoid [t] where
  mempty   = []
  mappend = (++)

and so lists are the "free monoid" over sets (or in Haskell types).

Okay, so free monads are the same idea. We take a functor, and give back a monad. In fact, since monads can be seen as monoids in the category of endofunctors, the definition of a list

data [a] = [] | a : [a]

looks a lot like the definition of free monads

data Free f a = Pure a | Roll (f (Free f a))

and the Monad instance has a similarity to the Monoid instance for lists

--it needs to be a functor
instance Functor f => Functor (Free f) where
  fmap f (Pure a) = Pure (f a)
  fmap f (Roll x) = Roll (fmap (fmap f) x)

--this is the same thing as (++) basically
concatFree :: Functor f => Free f (Free f a) -> Free f a
concatFree (Pure x) = x
concatFree (Roll y) = Roll (fmap concatFree y)

instance Functor f => Monad (Free f) where
  return = Pure -- just like []
  x >>= f = concatFree (fmap f x)  --this is the standard concatMap definition of bind

now, we get our two operations

-- this is essentially the same as \x -> [x]
liftFree :: Functor f => f a -> Free f a
liftFree x = Roll (fmap Pure x)

-- this is essentially the same as folding a list
foldFree :: Functor f => (f r -> r) -> Free f r -> r
foldFree _ (Pure a) = a
foldFree f (Roll x) = f (fmap (foldFree f) x)