Introduction to Free Monads
If you’ve been around Haskell circles for a bit, you’ve probably seen the term “free monads”. This article aims to introduce free monads and explain why they are useful.
To whet your appetite a little, free monads are basically a way to easily get a generic pure Monad
instance for any Functor
.
This can be rather useful in many cases when you’re dealing with treelike structures, but to name a few:
 To build an AST for an eDSL using donotation.
 To have different semantics for the same monad in different contexts, e.g., define an interpreter and a prettyprinter for an eDSL, or have a mock interpreter in addition to a real one.
 To build a decisiontree type structure harnessing the donotation for nondeterminism (like with lists, but for trees).
Of course, all of this is perfectly achievable with regular old monads and some newtype wrappers, but free monads let us get rid of a bit of boilerplate.
Basic familiarity with Haskell is assumed for the rest of this article.
Specifically, donotation and type classes Monoid
, Functor
, and Monad
.
Free algebraic structures
To understand the concept, you should think of “free” as in “free speech,” not as in “free beer”.
– Free Software Foundation, What is Free Software?
So, to start with, let us try to explore what “free” in free monads stands for. This part is a bit theoryheavy, so if it is not your cup of tea, feel free to skim over it.
In abstract algebra, we call something a “free X” when it is in some sense a minimal structure that satisfies conditions for being X. The exact definition of “minimal” in abstract algebra is a little vague, but the main idea is that “free X” satisfies all laws for X and does not have any other laws describing it. That is, in this context, “free” means “unrestricted” – it is not that we can get a structure “for free”, but that no other laws are restricting the structure apart from those absolutely necessary. That said, depending on your definition of “for free”, in most cases, we actually might also get a structure “for free”.
More formally, a free structure over a set $S$ is a set $M,$ together with operations on elements of $M,$ such that:
 There is an embedding $i: S\to M$.
 $M$ is a minimal closure, i.e., it only contains all the results of applying $i$ to elements of $S$, and any results of applying the operations, defined as part of the structure, to the elements of $M$.
 The only laws that hold for the generated structure are those required to hold.
An embedding is an injective morphism. That is, an embedding $S\to M$ is a mapping from elements of $S$ to elements of $M$, such that each element of $S$ is mapped onto a unique element of $M$ (injectivity), and, in some sense, this mapping is structurepreserving (i.e. it’s a morphism). The point is that every element of the original set is uniquely representable in the free structure.
Let us start with a simple example, specifically, Monoid
s.
In Haskell, any type α
in the Monoid
type class must have two functions defined.
First, to construct a neutral element, we have mempty :: α
.
Second, to in some sense combine two elements, we have (<>) :: α > α > α
.
A note about (<>)
The (<>)
operator is actually defined in the Semigroup
type class, but we’ll gloss over semigroups here for the sake of simplicity.
Additionally, these functions must satisfy three equations, called the monoid laws:
(x <> y) <> z = x <> (y <> z)  associativity
mempty <> x = x  left identity
x <> mempty = x  right identity
A free monoid thus has to have these two operations (together with an embedding of some underlying set) and satisfy these laws and only them.
For example, it is implied that commutativity, i.e. the equation x <> y = y <> x
, should only hold if it follows from the monoid laws.
To give a more concrete example, a list (or, more generally, a sequence) of elements of the set S
constitutes a free monoid over S
.
Indeed, if the set $M$ is a set of lists of elements of $S$:
type M = [S]
Then our embedding can be defined as:
i :: S > M
i x = [x]
Then mempty = []
and (<>) = (++)
.
$M$ contains []
, as required by mempty
, all singleelement lists, and all possible concatenations.
Finally, all the monoid laws hold, and no other laws are implied.
On the other hand, addition over integers doesn’t constitute a free monoid. That would imply the law of commutativity, which isn’t a monoid law and, in the case of integers, doesn’t follow from monoid laws.
On nonfree monoids
The previous version of this article incorrectly claimed that addition over nonnegative integers doesn’t constitute a free monoid (thanks to Michał Kukieła for the correction!). The reason for why that is incorrect is that for naturals, commutativity immediately follows from associativity:
$n+k$ $= \underset{n \text{ times}}{\underbrace{(1 + \ldots + 1)}} + \underset{k \text{ times}}{\underbrace{(1 + \ldots + 1)}}$ $= \underset{k \text{ times}}{\underbrace{(1 + \ldots + 1)}} + \underset{n \text{ times}}{\underbrace{(1 + \ldots + 1)}}$ $= k + n$
This doesn’t hold if integers can be of different signs. To see why, assume, e.g., $n < 0 < k:$ in this case, it’s impossible to get $k+n$ from $n+k$ just by reshuffling parentheses.
Another way to look at it is this: a free monoid doesn’t do anything interesting. Hence, we can “recover” any other monoid from a free one.
More formally, if $M$ is a free monoid over $S$, then for any monoid $N$, given a map $f : S \to N$, we can extend this mapping to a monoid morphism $f' : M \to N$ in a unique way.
This also implies that all free monoids over the same set are isomorphic.
Thus, if addition with naturals is a free monoid over some set $S$, then we can convert this to a list monoid over the same set (which we know is a free monoid). The trick is in the choice of the set: if we choose $S = \lbrace 1 \rbrace,$ we can map addition to concatenation and natural numbers to lists of corresponding lengths. Hence, addition with naturals is a free monoid over a singleton set.
If you’re wondering why []
is an element of M
, despite it not being required by either i
or (<>)
, that’s because mempty
is also an operation on M
, one that happens to have zero arguments.
Similar to monoids, any set and grouptheoretic construction can, in principle, have a free counterpart. For example, you might have free groups or free rings.
One objection to this somewhat informal introduction might be that the concept of “minimal structure” is not very welldefined. Category theory offers a way to define a free structure as a left adjunct of some forgetful functor. However, we will avoid delving too deep into the category theory here. If you’re interested, Bartosz Milewski’s article on adjunctions delves deeper into the subject.
Monads
1990  A committee formed by Simon PeytonJones, Paul Hudak, Philip Wadler, Ashton Kutcher, and People for the Ethical Treatment of Animals creates Haskell, a pure, nonstrict, functional language. Haskell gets some resistance due to the complexity of using monads to control side effects. Wadler tries to appease critics by explaining that “a monad is a monoid in the category of endofunctors, what’s the problem?”
– James Iry, A Brief, Incomplete, and Mostly Wrong History of Programming Languages
Before we see how this idea applies to monads, it might be helpful to compare monads to monoids first.
Let us first review the definition of the Monad
type class.
In Haskell, it is defined as:
class Functor m => Monad m where
return :: a > m a
(>>=) :: m a > (a > m b) > m b
A note on Monad's superclass
If you’re more familiar with modern Haskell, you might object that actually, the superclass of Monad
is Applicative
, but we will gloss over that for the sake of simplicity.
This definition needs to additionally satisfy the monad laws:
(m >>= g) >>= h = m >>= (\x > g x >>= h)  associativity
return a >>= h = h a  left identity
m >>= return = m  right identity
If you look at the monad laws and squint a bit (or perhaps a lot), you might notice that these laws seem somewhat similar to the monoid laws. The names of the laws are the same, at least. Our choice of the definition makes it a little harder to see the connection, though. If we instead rewrite these laws using the Kleisli composition:
(>=>) :: Monad m => (a > m b) > (b > m c) > (a > m c)
f >=> g = \x > f x >>= g
It becomes much more apparent:
(f >=> g) >=> h = f >=> (g >=> h)  associativity
return >=> f = f  left identity
f >=> return = f  right identity
(The proof of equivalence between monad laws expressed via >>=
and >=>
is left as an exercise for the reader.)
On equivalence
Here, by equivalence we mean that the monad laws expressed via Kleisli arrows imply the monad laws expressed via >>=
and vice versa.
The proof itself is a straightforward application of equational reasoning.
It’s easier to start from the Kleisli arrow form.
That is why a monad is indeed a monoid: it satisfies the same laws, and the “values” are of the type Functor f => a > f b
.
Note, though, that this is not the category of endofunctors.
However, there exists an isomorphism with the category of endofunctors.
On endofunctors
One could alternatively define monads via join :: m (m a) > m a
instead of >>=
, which would make it a little more evident that monads are monoids over endofunctors, but to explain this properly, we would need to use a bit more of category theory jargon.
There is an excellent r/math post on the subject.
We can guess a few things based on the intuition we gained by looking at free monoids.
First, we might note that return
and >=>
correspond to mempty
and (<>)
, respectively.
Second, we can expect that for any Functor
f :: Type > Type
, there is a corresponding free Monad
Free f :: Type > Type
, the same as for free monoids.
Free monads
Let us first try to construct Free f
by analogy.
We’ve seen that lists are free monoids.
The typical definition of a list type in Haskell looks something like this:
data List a = Nil  Cons a (List a)
Now, List a
is a type, but Free f
is a unary type constructor, so we’d need one more type argument.
Doing that directly yields:
data Free f a = Nil a  Cons f (Free f) a
We can’t define such a data type – f
is not a plain type, so it can’t be an argument of a data constructor.
But we’re actually very close.
Let us now look at the definition of Free f
:
data Free f a = Pure a  Free (f (Free f a))
As you can see, it is indeed very similar to a list.
Note, however, that it is a bit more general: the functor is arbitrary, potentially making it a tree with branches of type f
and leaves of type a
.
Leaves are encoded via the Pure
constructor, and branches – via the Free
constructor.
We can also note that leaves correspond to pure values, and branches correspond to monadic “actions”, respectively.
This point is important, so we’ll repeat: free monad is similar to a list, but, unlike a list, “continuation” (i.e. Free
) can be a branching structure, depending on the choice of the base functor f
.
It may be helpful to write out the types of these constructors explicitly:
Pure :: a > Free f a
Free :: f (Free f a) > Free f a
If you squint a bit, you will notice that Pure
has the same signature as return
(assuming Monad (Free f)
).
If you squint some more, you will notice that the signature of Free
is very similar to the signature of join
:
join :: Monad m => m (m a) > m a
Instead of defining monads in terms of return
and >>=
, we can alternatively define them in terms of fmap
, return
, and join
.
Hopefully, this provides some insight into why such a structure works as an encoding for a free monad.
Indeed, if we require that f
in Free f
must be a functor, we get fmap
from the start, and Pure
and Free
fill the roles of return
and join
, respectively.
If f
is a Functor
, then Free f
is also a Functor
.
Indeed, the instance is very straightforward:
instance Functor f => Functor (Free f) where
fmap f (Pure x) = Pure (f x)
fmap f (Free g) = Free (fmap f <$> g)
Notice that we need f
to be a Functor
to recursively descend the Free
branch.
If f
is a Functor
, then Free f
is also a Monad
.
The instance is also pretty straightforward:
instance Functor f => Monad (Free f) where
return = Pure
Pure x >>= f = f x
Free g >>= f = Free ((>>= f) <$> g)
Note that the implementation of >>=
is very similar to that of fmap
.
If we instead defined the Monad
instance in terms of join
, it would look something like this:
join (Pure x) = x
join (Free x) = Free $ join <$> x
We must note that this implementation, while straightforward, is not particularly efficient. A more efficient implementation, known as Churchencoded free monads, is available. Naturally, when using free monads, you should prefer the more efficient implementation. However, the core idea remains the same, so we’re not delving into this topic in this introduction.
Free monads, along with free applicative and alternative functors, and cofree comonads, are provided by the free
package on Hackage (and Stackage).
Using free monads, we can define a computation as a data structure. Here, “computation” is a very broad term. The data structure in question doesn’t define how the computation is performed, and we can write a separate interpreter (or indeed many interpreters) that performs the actual computation in question.
Using free monads
With the theory out of the way, let us see some examples to build our intuitions.
State as a free monad
Let us start off with the State
monad.
We’ll pretend we “forgot” that it’s a monad and will try to implement it from scratch in terms of a free monad.
First, we define a typical State
newtype and let GHC autoderive the functor instance:
newtype StateF s a = StateF { runStateF :: s > (a, s) }
deriving stock Functor
(Note that we’re calling it StateF
for “state functor”.)
We can also define the typical functions for working with state:
getF :: StateF s s
getF = StateF $ \s > (s, s)
putF :: s > StateF s ()
putF s = StateF $ const ((), s)
Now we can define a “free state” monad:
type State s = Free (StateF s)
We’ll also need to lift our state operations into the monad.
We could do it manually, of course.
We have StateF s a
, and we need to get StateF s (Free (StateF s) a)
and wrap it in Free
.
To lift any a
into Free f a
, we just need to apply Pure
:
get :: State s s
get = Free $ Pure <$> getF
But since it is a common pattern, the free
library provides a function to do this for us:
liftF :: (Functor f, MonadFree f m) => f a > m a
MonadFree
is just an MTLstyle type class for different encodings of the free monad.
Also, while on the topic of different encodings, for more flexibility, instead of directly using Free
and Pure
, one would generally use wrap
(defined in MonadFree
) and pure
respectively.
In our case, we can pretend that:
liftF :: Functor f => f a > Free f a
 The implementation of this simplified version
 is rather straightforward, as discussed above,
 so it is left as an exercise for the reader.
Hence, we can define:
get :: State s s
get = liftF getF
put :: s > State s ()
put = liftF . putF
And, like magic, we have a State
monad:
someComputation :: State Int ()
someComputation = do
i < get
put $ i + 1
pure ()
There is a catch, however.
This code will happily compile, but it doesn’t do anything interesting.
Indeed, we didn’t define the meaning of the computation, only its form, and we can’t directly use runStateF
to “run” our free state monad.
This means we need to write an interpreter, so let’s do that.
Remember that Free
has two constructors, Pure
and Free
, so we need to patternmatch on those:
runState :: State s a > s > (a, s)
runState (Pure x) s = (x, s)
runState (Free f) s =
let (m, s') = runStateF f s
in runState m s'
If you’re familiar with the usual state monad, you may have noticed that we’ve essentially moved the implementation of >>=
to runState
.
The free monad doesn’t specify the meaning of monadic actions, so we have to decide what those actions mean when we’re running it.
To illustrate this point, we’re going to write another interpreter, which is essentially a prettyprinter for the flow of a State
computation:
printState :: (Show s, Show a) => State s a > s > String
printState (Pure x) s = "pure (" <> show x <> "," <> show s <> ")"
printState (Free m) s =
let (x, s') = runStateF m s
in "state change " <> show s <> " > " <> show s' <> "\n"
<> printState x s'
If we run someComputation
defined above through this interpreter by invoking printState someComputation 1
, we’ll get the following output:
state change 1 > 1
state change 1 > 2
pure ((),2)
The first line of output corresponds to get
.
While it doesn’t modify the state, it’s still an action, so the state change
line is still printed.
The second line corresponds to put $ i + 1
, which naturally changes the state to 2
.
The third line corresponds to pure ()
, but it also outputs the end state.
Let’s summarize what we’ve learned so far.
We can take any usual base functor for some monad and get a Monad
instance “for free”.
There’s no free lunch here, though, so we need to define the semantics of this monad separately by writing an interpreter (or several if we need to).
List as a free monad
Not all free monads behave exactly the same as their regular counterparts. For instance, you might know that the list monad encodes nondeterminism.
In case the last statement is surprising...
If the statement about list monad encoding nondeterminism is surprising, consider that one could use a list to represent all possible outcomes of some event and then handle those one by one. For further reading on this topic, refer to the School of Haskell article on the list monad or the Haskell wikibook section on understanding monads
However, if we derive a free monad for lists, the behavior is slightly different. To give a specific example:
listComputation :: Free [] Int
listComputation = do
x < liftF [1, 2, 3]
y < liftF [10, 20]
z < liftF [100, 200]
pure $ x+y+z
printFreeList :: Show a => Free [] a > String
printFreeList (Pure x) = show x
printFreeList (Free f) = "["
<> intercalate "," (printFreeList <$> f)
<> "]"
If we run printFreeList listComputation
, we will get:
[[[111,211],[121,221]],[[112,212],[122,222]],[[113,213],[123,223]]]
Notice how it gets us what is essentially nested lists, unlike the regular list monad. Notice also that it’s essentially a rose tree. Of course, we can get the standard list monad behavior by concatenating the nested lists, but we might not necessarily want to do that.
In general, we can restore any proper monad behavior from a free monad since it doesn’t define any semantics beyond those necessary for any monad.
free
provides a function for that:
foldFree :: Monad m => (forall x. f x > m x) > Free f a > m a
Given a function (a natural transformation) converting f x
into some monad m x
for any x
, we can convert Free f a
into m a
.
On natural transformations
The discussion of naturality is not particularly relevant here, but we’ll introduce the concept briefly.
The natural transformation is a structurepreserving transformation between two functors.
Here, the naturality condition is enforced by the parametricity, that is, the function is polymorphic in x
.
Essentially, you can think of any function with type forall a. f a > g a
as a natural transformation between f
and g
, as long as you ignore undefined
and other bottoms.
Returning to our list example, we can get the original list behavior by applying foldFree id
:
> foldFree id listComputation
[111,211,121,221,112,212,122,222,113,213,123,223]
Free monads for eDSLs
By now, we hopefully got some intuition for how free monads work. Let us now define a toy calculator language that reads a few integers from the standard input, adds them together, and prints the result.
The key intuition here is that if the next action depends on the previous one, we need to encode this as a continuation, i.e., we need to have a function accepting some argument and returning the functor parameter.
For example, for addition, we would need to define a data constructor with three arguments: two operands and the continuation. The continuation would need to accept the result of addition and (eventually) return some end result.
If a continuation doesn’t accept a value, we might just as well encode it as its end result.
Since Haskell is lazy, () > a
is basically the same as a
.
Now, if we try to define a functor where every operation uses the same type everywhere, we’ll run into a bit of an issue. Consider this datatype for instance:
data ASTF a
= Add a a (a > a)
 Input (a > a)
 Output a a
If we try to derive a Functor
instance, GHC will complain:
Constructor ‘Add’ must not use the type variable in a function argument
It is, in fact, impossible to define a lawful Functor
instance if the functor’s type variable ends up in the function argument position (this has to do with Functor
being a covariant functor, but discussion of variance is out of scope here).
Hence, we will introduce two type variables: one for operation arguments, and another for the overall result.
data ASTF t a
= Add t t (t > a)
 Input (t > a)
 Output t a
deriving Functor
Notice that for Add
we’re saying that it takes two arguments t
, its result is also t
, but ultimately, the continuation returns the type a
.
In practice, we will define add :: t > t > Free (ASTF t) t
, but to have a lawful Functor
and also more flexibility, we’re not assuming these types are the same.
Similar reasoning applies to Input
.
With Output
, we could’ve defined it as Output t (() > a)
since our output action doesn’t have any meaningful result.
But we omit this extraneous argument and simply encode the continuation as a value.
In practice, we’ll set a
to be ()
.
We can now define our monad and a few helper functions:
type FreeAST t = Free (ASTF t)
input :: FreeAST t t
input = liftF $ Input id
add :: t > t > FreeAST t t
add x y = liftF $ Add x y id
output :: t > FreeAST t ()
output x = liftF $ Output x ()
And write a simple program:
program :: (Read a, Show a) => FreeAST a ()
program = do
x < input
y < input
res < add x y
output res
Now, the interpreter for this program will need to convert our FreeAST
to IO
because we’re doing input and output.
We can do this with foldFree
; we only need to provide a conversion from the base functor to IO
.
computeAST :: FreeAST Int () > IO ()
computeAST = foldFree go
where
go :: ASTF Int x > IO x
go arg = case arg of
Add x y next > pure $ next (x + y)
Input next > next . read <$> getLine
Output x next > do
print x
pure next
We can write other interpreters, of course.
For instance, we could write a prettyprinter here.
Using the fact that we can convert a free monad to any other monad using foldFree
, we’ll do just that.
For instance, let’s convert FreeAST String
into WriterT String (State Int)
.
We’ll be naming variables using a counter in the State
and producing the printed output using the Writer
.
Note that the argument type t
is set to String
here since our terms will be the variable names, not values.
printAST :: FreeAST String () > String
printAST fast = snd $ evalState (runWriterT $ foldFree go fast) 0
where
freshVar :: State Int String
freshVar = do
n < get
put $ n + 1
pure $ "x" <> show n
go :: ASTF String a > WriterT String (State Int) a
go f = case f of
Add x y g > do
var < lift freshVar
tell $
var <> " < add " <> x <> " " <> y <> "\n"
pure $ g var
Input x > do
var < lift freshVar
tell $ var <> " < input\n"
pure $ x var
Output s next > do
tell $ "output " <> s <> "\n"
pure next
Notice that, up to this point, all constructors of our ASTF
had exactly one parameter that had anything to do with the functor.
A question you might have now is: what happens if we have several?
If you’ve gained a bit of intuition for free monads by now, you might suspect we get a branching computation, and that’s exactly right!
Let’s add simple branching to our toy language to see how it works.
data ASTF t a
= Add t t (t > a)
 Input (t > a)
 Output t a
 If t a a
deriving Functor
We add a new constructor, If
, with one scalar parameter and two branches.
We can now define a helper:
if' :: t > FreeAST t a > FreeAST t a > FreeAST t a
if' cond t f = Free $ If cond t f
Notice how instead of liftF
we have to use Free
directly here – our branches are already of type FreeAST
.
As discussed earlier, in general you would use wrap
defined in MonadFree
instead of Free
directly, but we’re glossing over that for simplicity.
We can now modify our interpreter computeAST
by adding another case:
computeAST :: FreeAST Int () > IO ()
computeAST = foldFree go
where
go :: ASTF Int x > IO x
go arg = case arg of
Add x y next > pure $ next (x + y)
Input next > next . read <$> getLine
Output x next > do
print x
pure next
 below is the only thing that changed
If cond t f >
if cond /= 0 then pure t else pure f
Here we define the semantics of the branching – for the sake of not complicating the example, we interpret 0
as false and nonzero as true.
When we try modifying the pretty printer, we run into a problem.
Since our branching operation introduces a bit of nondeterminism into the computation, our approach with WriterT (State Int)
doesn’t work anymore.
One could fix it by explicitly adding some kind of nondeterminism transformer on top of this, like ListT
or LogicT
, but let us instead write the prettyprinter directly.
printAST :: FreeAST String a > String
printAST fast = snd $ evalState (runWriterT $ go fast) 0
where
freshVar :: State Int String
freshVar = do
n < get
put $ n + 1
pure $ "x" <> show n
go :: FreeAST String a > WriterT String (State Int) ()
go (Pure _) = pure ()
go (Free f) = case f of
Add x y g > do
var < lift freshVar
tell $
var <> " < add " <> x <> " " <> y <> "\n"
go $ g var
Input x > do
var < lift freshVar
tell $ var <> " < input\n"
go $ x var
Output s next > do
tell $ "output " <> s <> "\n"
go next
If cond onTrue onFalse > do
tell $ "if' " <> cond <> " (do\n"
_ < go onTrue
tell "\n) (do\n"
_ < go onFalse
tell "\n)\n"
Not much has changed.
Instead of pure
, we use explicit recursion, and we have to handle the Pure
case explicitly.
For the sake of simplicity, the return type of go
is fixed at ()
since we don’t care about the result here.
When we try to run this prettyprinter on some code that uses branching, we might be a little surprised by the output. For example, with the following “program”:
someAST :: (Read a, Show a) => FreeAST a ()
someAST = do
x < input
y < input
res < if' x (add x y) (pure y)
output res
Applying our prettyprinter, we get:
x0 < input
x1 < input
if' x0 (do
x2 < add x0 x1
output x2
) (do
output x1
)
The reason for this is simple: when the free monad is built up, the continuation is passed to each place where the base functor is recursive in its parameter. This means that all the code after our “if’” command gets copied to both branches. There isn’t a workaround for this because free monads build trees and not general graphs. However, a more efficient representation – e.g., the Church encoding mentioned previously – will reduce the overhead.
Decomposing ASTs
Naturally, we don’t have to define the whole AST at once – we’re free to decompose it however we see fit. Likewise, we can also decompose interpreters.
For instance, we could decompose our AST into a part for arithmetic and a part for I/O:
data ArithASTF t a
= Add t t (t > a)
 + Sub, Mul, etc
deriving Functor
data IOASTF t a
= Input (t > a)
 Output t a
deriving Functor
data ASTF t a
= Arith (ArithASTF t a)
 IO (IOASTF t a)
deriving Functor
We would have to modify the helper functions slightly:
input :: FreeAST t t
input = liftF $ IO $ Input id
add :: t > t > FreeAST t t
add x y = liftF $ Arith $ Add x y id
output :: t > FreeAST t ()
output x = liftF $ IO $ Output x ()
And we could also decompose the interpreter:
computeAST :: FreeAST Int () > IO ()
computeAST = foldFree computeASTF
computeASTF :: (Num t, Read t, Show t) => ASTF t x > IO x
computeASTF arg = case arg of
Arith c > pure $ computeArith c
IO c > computeIO c
computeArith :: Num t => ArithASTF t a > a
computeArith (Add x y next) = next (x + y)
computeIO :: (Read t, Show t) => IOASTF t a > IO a
computeIO arg = case arg of
Input next > next . read <$> getLine
Output x next > do
print x
pure next
Notice how we managed to neatly decompose the interpreter into two: one pure and one doing I/O.
This all might be pretty obvious, but it bears mentioning.
Trees as free monads
To close out this section, let’s look at another application of free monads. Namely, let’s build a binary search tree from a sorted list.
Our base functor for the binary tree would look like this:
data BinTreeF l a = NodeF l a a
deriving Functor
You might ask yourself: where are the leaf and/or nil branch constructors?
We can actually encode those as the “return value” of type Maybe l
, so we don’t need them here.
Now we define our free monad type and build the tree.
type FreeBinTree l = Free (BinTreeF l)
buildBalanced :: [Int] > FreeBinTree Int (Maybe Int)
buildBalanced [] = pure Nothing
buildBalanced [x] = pure $ Just x
buildBalanced xs = do
let len = length xs
(l,x:r) = splitAt (len `div` 2) xs
b < liftF $ NodeF x l r
buildBalanced b
The first two cases, where lists have sizes of zero and one, respectively, are selfevident. If there are more elements in the list, we divide it in half. The approximate “middle” element serves as the current node value. We then recursively construct left and right subtrees from the corresponding halves of the list.
Notice how we’re passing left and right halves of the list to NodeF
and then bind it to name b
.
As we discussed previously, multiple functor variables per constructor encode nondeterminism.
So here, we basically split the computation into two branches.
We then recursively build the tree for each branch.
The caveat here is there’s no simple way to print this all, and working with a tree wrapped in the Free
is probably not particularly convenient.
So we can convert this FreeBinTree
into a regular binary tree, for example:
data BinTree l = Nil  Leaf l  Branch l (BinTree l) (BinTree l)
deriving Show
convert :: FreeBinTree a (Maybe a) > BinTree a
convert (Pure Nothing) = Nil
convert (Pure (Just x)) = Leaf x
convert (Free f) =
let NodeF x l r = convert <$> f
in Branch x l r
Note how Pure
values correspond to leaves, and Free
values correspond to branches.
Running convert . buildBalanced
on a list produces the expected result, i.e., a binary search tree.
> convert $ buildBalanced [0..10]
5 (2 (1 0
Nil)
(4 3
Nil))
(8 (7 6
Nil)
(10 9
Nil))
Conclusions
The only way to learn a new programming language is by writing programs in it.
– Dennis Ritchie
Hopefully, after this brief introduction, you understand, at least in principle, what free monads are and how they may be useful. Of course, the only way to get proficient with them is to use them in projects, and no blog post can replace actual handson experience, but that applies to everything in programming.
Let us then briefly review what we’ve learned.
 Free monads are “free” because they do not impose any additional constraints beyond those required by the definition of a monad.
 They are a particular type of a free algebraic structure.
 As such, they are very similar to free monoids.
 They build treelike structures, which later can be interpreted.
 Any typical Haskell monad can be implemented as a free monad with a corresponding interpreter.
 Generally, a free monad can be converted to any other monad via a natural transformation.
 One particular application of free monads is in building ASTs for eDSLs.
 But you could use them almost anywhere where a tree could be used.
For further reading: it turns out, to get a monad, we don’t really even need a functor if we cheat a little. This construction is known as freer monads (as in, more free than free). See Free and Freer Monads: Putting Monads Back into Closet .
All examples from this article are available as code on GitHub.
Exercises

Implement the standard monads
Reader
andWriter
usingFree
. Here is a template to get you started:import Control.Monad.Free newtype ReaderF r a = ReaderF { runReaderF :: r > a } deriving Functor type Reader ... ask :: Reader r r ask = undefined runReader :: Reader r a > r > a runReader = undefined newtype WriterF w a = WriterF { runWriterF :: (w, a) } deriving Functor type Writer ... tell :: w > Writer w () tell = undefined listen :: Monoid w => Writer w a > Writer w (a, w) listen = undefined pass :: Monoid w => Writer w (a, w > w) > Writer w a pass = undefined runWriter :: Monoid w => Writer w a > (a, w) runWriter = undefined

Using a free monad, define a monad for a
String
keyed,String
valued keyvalue store. The store must support two commands, assuming the store monad is calledStore
:type Key = String type Value = String getValue :: Key > Store (Maybe Value) putValue :: Key > Value > Store ()
For an interpreter, implement a natural transformation from
StoreF
toIO
, usingIORef [(String, String)]
as a backing store. Feel free to useMap
orHashMap
if you want to. 
Notice that
BinTree
defined above is not aMonad
. However, if leaves and branches could have different types, it would be. Now consider the following type:data BinTree l a = Leaf a  Branch l (BinTree l a) (BinTree l a) deriving (Show, Functor)
It is a monad.
Implement a conventional
Monad
instance, and implementconvert :: FreeBinTree l a > BinTree l a
usingfoldFree
and a natural transformationBinTreeF l a > BinTree l a
.
If you get absolutely stuck, the intended solutions to exercises are avaliable in the GitHub repository with the examples in the solutions
branch.