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

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

Solution 2

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.

Solution 3

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.

Solution 4

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)

Solution 5

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

View more solutions

Comments

[Roger Lindsjö]

A fairly good explanation is here haskellforall.com/2012/06/…

[David]

@Roger that's kind of the page that brought me here. To me, that example defines a monad instance for a type named "Free" and that's it.

[Paulo Scardine]

Perhaps I'm not smart enough to dig haskell, but stuff like this seems so hard to digest. I was enjoying the language until the I/O chapter and the pure/impure thing.

[David]

@PauloScardine, this is nothing you have to be concerned about. My question came from the interest to understand some advanced data structure and maybe getting a glimpse of what's cutting edge in Haskell development right now - it is on no way necessary or representative of what actually writing Haskell is about so far. (And a heads up, it gets better once you're past the IO learning stage again)

[Edward Kmett]

@PauloScardine You do not need the above answer in order to productively program in Haskell, even with free monads. In fact, I wouldn't recommend attacking the free monad in this way to someone who didn't have a background in category theory. There are plenty of ways to talk about it from an operational perspective and grok how to use one without diving into the category theory. However, it is impossible for me to answer the question about where they come from without diving into theory. Free constructions are a powerful tool in category theory, but you don't need this background to use them.

[Paulo Scardine]

Seems like it is really hard to grasp haskell without some background in Calculus. Perhaps that is why it is not very popular despite all the advantages - most people go throughout calculus in college with the same pleasure of chewing glass (even in CS).

[Sarah]

@PauloScardine: You need exactly no calculus to utilize Haskell effectively and even understand what you're doing. It's a bit weird to complain that "this language is mathy" when the mathyness is just extra goodness that you can use for fun and profit. You don't get these things in most imperative languages. Why would you complain about extras? You can just elect NOT to reason mathematically, and approach it like you would any other new language.

[John L]

This may be the best approachable explanation of "free" I've yet seen. Especially the paragraph starting with "More generally."

[Paulo Scardine]

@Sarah: I'm yet to see a piece of documentation or IRC conversation about haskell that is not heavy on computer theory and lambda calculus therms.

[mnish]

What kind of limits/colimits exist in the category of Haskell types?

[David]

@PauloScardine this is drifting a little OT, but in Haskell's defense: similar technical things apply to all other programming languages, only that Haskell has such a nice compilation that people can actually enjoy talking about them. Why/how X is a monad is interesting to many people, discussions about the IEEE floating point standard aren't; both cases don't matter for most people, because they can just use the results.

[David]

Your paragraphs make a really great addition to Philip's post.

[Tom Ellis]

I know you were just drawing an analogy rather than making a definition, but a free monad is certainly not analogous to a list of functors in any sense. It's much closer to a tree of functors.

[Gabriella Gonzalez]

I stand by my terminology. For example, using my index-core package you can define "free monad comprehensions", which behave just like the list monad, except that you bind functors instead of values. A free monad is a list of functors in the sense that if you translate all Haskell concepts up the category of functors, then lists become free monads. A true tree of functors then becomes something completely different.

[Tom Ellis]

You are right that monad is the categorification, in some sense, of the concept of monoid, thus free monads are analogous to free monoids, i.e. lists. To that extent you are certainly correct. However the structure of a value of a free monad is not a list. It is a tree, as I detail below.

[Gabriella Gonzalez]

@TomEllis Technically, it is only a tree if your base functor is a product functor. When you have a sum functor as the base functor it more closely resembles a stack machine.

[David]

This answer gave me the impression that I understand what they might even be useful for.

[danidiaz]

I really like this answer.

[Bartosz Milewski]

What you guys are saying is that the free monad takes the shape of the functor itself. So if the functor is tree-like (products), free monad is tree-like; if it's list-like (sums), free monad is list-like; if it's function-like, free monad is function-like; etc. This makes sense to me. So just like in a free monoid, you keep treating every application of mappend as creating a completely new element; in free monad, you treat every application of the functor as a completely new element.

[Tom Ellis]

Even if the functor is a "sum functor" the resulting free monad is still tree-like. You end up with more than one type of node in your tree: one for each component of your sum. If your "sum functor" is X -> 1 + X then indeed you get a list, which is just a degenerate sort of tree.

[jkff]

I think it's interesting to look at Free f a = Pure a | Roll (f (Free f a)) as Free f a = a + fa + ffa + ..., i.e. "f applied to a any number of times". Then concatFree (i.e. join) takes an "f applied any number of times to (f applied any number of times to a)" and collapses the two nested applications into one. And >>= takes "f applied any number of times to a" and "how to get from a to (b with f applied any number of times)", and basically applies the latter to a's inside the former and collapses the nesting. Now I myself get it!

[Edward Kmett]

@mnish - you might get better results by asking that as a regular question rather than a response. That said Hask serves as a constructive analogue of Set, and we have (weak) products, and (weak) coproducts, if you ignore issues with bottoms. That should give you finite limits, but note we don't have the vocabulary in Hask to prove anything about commutative squares, so any work there has to be done on a meta level. The limitations are more pronounced on the colimit-side as to build pushouts/colimits, we often need quotient types, which Haskell lacks.

[misterbee]

Can the free monad replace the Monad type class? That is, could I write a program using only the free monad's return and bind, and then join the results using whichever I prefer of Mwybe or List or whatever, or even generate multiple monadic views of one sequence of binded/concatted function calls. Ignoring bottom and nontermination, that is.

[rgrinberg]

is concatFree basically join?

[Edward Kmett]

@mnish Hask has all small limits and colimits, it is complete and cocomplete. If we treat our categories as kinds we can make newtype Const a (b::i) = Const a then we can make newtype Lim f = Lim { runLim :: forall a. f a } and data Colim f where Colim :: f a -> Colim f. Now we have Colim -| Const -| Lim :: (i -> *) -> * which you can show pretty easily.

[Tom Ellis]

@EdwardKmett: I'm a bit confused. If Hask has all small limits how do you get equalisers?

[Edward Kmett]

@TomEllis: I knew i'd get called out on that! The category of natural transformations that that has to use is a subset of the 'real' category of natural transformations that abuses parametricity as a proxy for naturality. Unfortunately the combination of parametricity's strength, which lets (forall a. f a -> g a) commute with both fmap and contramap and the fact that all Functors you can construct having that funny tagged f on the front of them forcing your functor to work fibered over an faithful mapping on types destroys a lot of standard constructions. =(

[Hjulle]

"So lists are the free monoid over sets" Apparantly not according to this blog article: comonad.com/reader/2015/free-monoids-in-haskell

[Philip JF]

@Hjulle Haskell types are not sets and Haskell "lists" are not lists. So, that really shouldn't be suprising. [a] has extra values the free monad doesn't since Haskell lists might be infinite.

[Martin Capodici]

This answer helped, but I think it would have confused me had I not met 'join' on the NICTA course and read haskellforall.com/2012/06/…. So for me, the trick to understanding is to read a lot of answers until it sinks in. (NICTA Reference: github.com/NICTA/course/blob/master/src/Course/Bind.hs)

[Boris Marinov]

So a monad is a functor, which is also a monoid?

[polkovnikov.ph]

@misterbee This question deserves its own topic. It seems that you can do that, given that you're using an extensible ADT that can handle adding Put, Get, Local etc. in addition to Pure and Roll. That's likely to be implemented via data types a la carte techinque. I bet I have seen that in literature on modular interpreters.

[Ruud]

“Here is a perhaps more accessible explanation. […] In fact, since monads can be seen as monoids in the category of endo functors, …” Nevertheless, I think this is a very good answer.

[tlo]

"monads can be seen as monoids in the category of endo functors" <3 (you should link to stackoverflow.com/a/3870310/1306877 because every haskeller should know about that reference!)

[Curycu]

this answer is best ever

[aoeu256]

Basically Haskell is like Lisp, so you can do meta programming but it requires types to check your meta programming....?

[Jeffrey Benjamin Brown]

Wonderful answer. A beginner might get confused about the differing meanings of f -- in some cases it is a type, in others a function. Maybe rename the function to g?

[jjwatt]

The most striking thing about this answer to me is that it's what I thought monads were in the first place! After encountering monads in the context of parsing and futures/promises from papers that I read. I even did a design for a validation system that "built up" all of the computations without executing them, thinking that monads just always did that. Great answer.

[joshuahhh]

@jkff: That formula is almost right! But if you carefully unroll the recursive definition of Free, you don't get Free f a = a + f a + f f a + ...; you get Free f a = a + f (a + f (a + ...) ). These are different, because f (a + b) isn't (necessarily) the same as f a + f b. For example, take []. Your formula would say that Free [] Int consists of Ints, lists of Ints, lists of lists of Ints, etc. But Free [] Int is more general – it has things like [1, [2, 3], 4], which isn't any of those. This emerges from the fact that [a + b] is bigger than [a] + [b].

[jkff]

@joshuahhh you're right, thanks for pointing this out!

[worldsayshi]

Does this mean that a free monad is an injective monad? And maybe even a reversible monad?

[Ivan Klass]

Thank you very much for this down-to-earth explanation! I was able to get that quite simple idea without having to know Haskell (I'm a scala FP enthusiast). So now it's much more clear to me, it sounds like the continuation of the Coyoneda trick (lazy functor) but we also defer the flatMap part. With Coyoneda we just encapsulate all the sequence of functions until we know how to apply them, here in Free Monads we make a kind of "lazy monad" by encapsulating pure values and suspendings in the data structure, so we can provide an actual monad later.

[Amos Joshua]

This is a fantastic answer!