Search code examples
haskellmonadscategory-theoryfree-monad

What are free monads?


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.)


Solution

  • 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)