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

Here's an even simpler answer: A Monad is something that "computes" when monadic context is collapsed by join :: m (m a) -> m a (recalling that >>= can be defined as x >>= y = join (fmap y x)). This is how Monads carry context through a sequential chain of computations: because at each point in the series, the context from the previous call is collapsed with the next.

A free monad satisfies all the Monad laws, but does not do any collapsing (i.e., computation). It just builds up a nested series of contexts. The user who creates such a free monadic value is responsible for doing something with those nested contexts, so that the meaning of such a composition can be deferred until after the monadic value has been created.

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)

A free foo happens to be the simplest thing that satisfies all of the 'foo' laws. That is to say it satisfies exactly the laws necessary to be a foo and nothing extra.

A forgetful functor is one that "forgets" part of the structure as it goes from one category to another.

Given functors F : D -> C, and G : C -> D, we say F -| G, F is left adjoint to G, or G is right adjoint to F whenever forall a, b: F a -> b is isomorphic to a -> G b, where the arrows come from the appropriate categories.

Formally, a free functor is left adjoint to a forgetful functor.

The Free Monoid

Let us start with a simpler example, the free monoid.

Take a monoid, which is defined by some carrier set T, a binary function to mash a pair of elements together f :: T → T → T, and a unit :: T, such that you have an associative law, and an identity law: f(unit,x) = x = f(x,unit).

You can make a functor U from the category of monoids (where arrows are monoid homomorphisms, that is, they ensure they map unit to unit on the other monoid, and that you can compose before or after mapping to the other monoid without changing meaning) to the category of sets (where arrows are just function arrows) that 'forgets' about the operation and unit, and just gives you the carrier set.

Then, you can define a functor F from the category of sets back to the category of monoids that is left adjoint to this functor. That functor is the functor that maps a set a to the monoid [a], where unit = [], and mappend = (++).

So to review our example so far, in pseudo-Haskell:

U : Mon → Set -- is our forgetful functor
U (a,mappend,mempty) = a

F : Set → Mon -- is our free functor
F a = ([a],(++),[])

Then to show F is free, we need to demonstrate that it is left adjoint to U, a forgetful functor, that is, as we mentioned above, we need to show that

F a → b is isomorphic to a → U b

now, remember the target of F is in the category Mon of monoids, where arrows are monoid homomorphisms, so we need a to show that a monoid homomorphism from [a] → b can be described precisely by a function from a → b.

In Haskell, we call the side of this that lives in Set (er, Hask, the category of Haskell types that we pretend is Set), just foldMap, which when specialized from Data.Foldable to Lists has type Monoid m => (a → m) → [a] → m.

There are consequences that follow from this being an adjunction. Notably that if you forget then build up with free, then forget again, its just like you forgot once, and we can use this to build up the monadic join. since UFUF ~ U(FUF) ~ UF, and we can pass in the identity monoid homomorphism from [a] to [a] through the isomorphism that defines our adjunction,get that a list isomorphism from [a] → [a] is a function of type a -> [a], and this is just return for lists.

You can compose all of this more directly by describing a list in these terms with:

newtype List a = List (forall b. Monoid b => (a -> b) -> b)

The Free Monad

So what is a Free Monad?

Well, we do the same thing we did before, we start with a forgetful functor U from the category of monads where arrows are monad homomorphisms to a category of endofunctors where the arrows are natural transformations, and we look for a functor that is left adjoint to that.

So, how does this relate to the notion of a free monad as it is usually used?

Knowing that something is a free monad, Free f, tells you that giving a monad homomorphism from Free f -> m, is the same thing (isomorphic to) as giving a natural transformation (a functor homomorphism) from f -> m. Remember F a -> b must be isomorphic to a -> U b for F to be left adjoint to U. U here mapped monads to functors.

F is at least isomorphic to the Free type I use in my free package on hackage.

We could also construct it in tighter analogy to the code above for the free list, by defining

class Algebra f x where
  phi :: f x -> x

newtype Free f a = Free (forall x. Algebra f x => (a -> x) -> x)

Cofree Comonads

We can construct something similar, by looking at the right adjoint to a forgetful functor assuming it exists. A cofree functor is simply /right adjoint/ to a forgetful functor, and by symmetry, knowing something is a cofree comonad is the same as knowing that giving a comonad homomorphism from w -> Cofree f is the same thing as giving a natural transformation from w -> f.

The Free Monad (data structure) is to the Monad (class) like the List (data structure) to the Monoid (class): It is the trivial implementation, where you can decide afterwards how the content will be combined.

---

You probably know what a Monad is and that each Monad needs a specific (Monad-law abiding) implementation of either fmap + join + return or bind + return.

Let us assume you have a Functor (an implementation of fmap) but the rest depends on values and choices made at run-time, which means that you want to be able to use the Monad properties but want to choose the Monad-functions afterwards.

That can be done using the Free Monad (data structure), which wraps the Functor (type) in such a way so that the join is rather a stacking of those functors than a reduction.

The real return and join you want to use, can now be given as parameters to the reduction function foldFree:

foldFree :: Functor f => (a -> b) -> (f b -> b) -> Free f a -> b
foldFree return join :: Monad m => Free m a -> m a

To explain the types, we can replace Functor f with Monad m and b with (m a):

foldFree :: Monad m => (a -> (m a)) -> (m (m a) -> (m a)) -> Free m a -> (m a)

A Haskell free monad is a list of functors. Compare:

data List a   = Nil    | Cons  a (List a  )

data Free f r = Pure r | Free (f (Free f r))

Pure is analogous to Nil and Free is analogous to Cons. A free monad stores a list of functors instead of a list of values. Technically, you could implement free monads using a different data type, but any implementation should be isomorphic to the above one.

You use free monads whenever you need an abstract syntax tree. The base functor of the free monad is the shape of each step of the syntax tree.

My post, which somebody already linked, gives several examples of how to build abstract syntax trees with free monads

I think a simple concrete example will help. Suppose we have a functor

data F a = One a | Two a a | Two' a a | Three Int a a a

with the obvious fmap. Then Free F a is the type of trees whose leaves have type a and whose nodes are tagged with One, Two, Two' and Three. One-nodes have one child, Two- and Two'-nodes have two children and Three-nodes have three and are also tagged with an Int.

Free F is a monad. return maps x to the tree that is just a leaf with value x. t >>= f looks at each of the leaves and replaces them with trees. When the leaf has value y it replaces that leaf with the tree f y.

A diagram makes this clearer, but I don't have the facilities for easily drawing one!

Trying to provide a “bridge” answer between the auper-simple answers here and the full answer.

So “free monads” build a “monad” out of any “functor”, so let’s take these in order.

Functors in detail

Some things are type-level adjectives, meaning they take a type-noun like “integers” and give you back a different type-noun like “lists of integers” or “pairs of strings with integers” or even “functions making strings out of integers.” To denote an arbitrary adjective let me use the stand-in word “blue”.

But then we notice a pattern that some of these adjectives are input-ish or output-ish in the noun they modify. For example “functions making strings out of __” is input-ish, “functions turning strings into __” is output-ish. The rule here involves me having a function X → Y, some adjective “blue” is outputtish, or a functor, if I can use such a function to transform a blue X into a blue Y. Think of “a firehose spraying Xs” and then you screw on this X → Y function and now your firehose sprays Ys. Or it is inputtish or a contravariant if it is the opposite, a vacuum cleaner sucking up Ys and when I screw this on I get a vacuum sucking up Xs. Some things are neither outputtish nor inputtish. Things that are both it turns out are phantom: they have absolutely nothing to do with the nouns that they describe, in the sense that you can define a function “coerce” which takes a blue X and makes a blue Y, but *without knowing the details of the types X or Y,” not even requiring a function between them.

So “lists of __” is outputtish, you can map an X → Y over a list of Xs to get a list of Ys. Similarly “a pair of a string and a __” is outputtish. Meanwhile “a function from __ to itself” is neither outputtish nor inputtish,” while “a string and a list of exactly zero __s” could be the “phantom” case maybe.

But yeah, that's all there is to functors in programming, they are just things that are mappable. If something is a functor it is a functor uniquely, there is at most only one way to generically map a function over a data structure.

Monads

A monad is a functor that in addition is both

1. Universally applicable, given any X, I can construct a blue X,
2. Can be repeated without changing the meaning much. So a blue-blue X is in some sense the same as just a blue X.

So what this means is that there is a canonical function collapsing any blue-blue __ to just a blue __. (And we of course add laws to make everything sane: if one of the layers of blue came from the universal application, then we want to just erase that universal application; in addition if we flatten a blue-blue-blue X down to a blue X, it should not make a difference whether we collapse the first two blues first or the second two first.)

The first example is “a nullable __”. So if I give you a nullable nullable int, in some sense I have not given you much more than a nullable int. Or “a list of lists of ints,” if the point is just to have 0 or more of them, then “a list of ints” works just fine and the proper collapse is concatenating all of the lists together into one super list.

Monads became big in Haskell because Haskell needed an approach to do things in the real world without violating its mathematically pure world where nothing really happens. The solution was to add is sort of watered down form of metaprogramming where we introduce an adjective of “a program which produces a __.” So how do I fetch the current date? Well, Haskell can't do it directly without unsafePerformIO but it will let you describe and compose the program which produces the current date. In this vision, you are supposed to describe a program which produces nothing called “Main.main,” and the compiler is supposed to take your description and hand you this program as a binary executable for you to run whenever you want.

Anyway “a program which produces a program which produce an int” doesn't buy you much over “a program which produces an int” so this turns out to be a monad.

Free Monads

Unlike functors, monads aren't uniquely monads. There is not just one monad instance for a given functor. So for example “a pair of an int and a __”, what are you doing with that int? You could add it, you could multiply it. If you make it a nullable int, you could keep the minimum non-null one or the maximum non-null one, or the leftmost non-null one or the rightmost non-null one.

The free monad for a given functor is the "boringest” construction, it is just “A free blue X is a blueⁿ X for any n = 0, 1, 2, ...”.

It is universal because a blue⁰ X is just an X. And a free blue free blue X is a blue^m blueⁿ X which is just a blue^m+n X. It implements “collapse” therefore by not implementing collapse at all, internally the blues are nested arbitrarily.

This also means you can defer exactly which monad you are choosing until a later date, later you can define a function which reduces a blue-blue X to a blue X and collapse all of these to blue^0,1 X and then another function from X to blue X gives you blue¹ X throughout.