So you may have heard of the Free monad upon your journey of exploring functional programming. You may have even read a blog or two, or even three about it. You may have even implemented a DSL (Domain Specific Language) with it. Well hopefully I'm going to provide you with a fresh take on exploring Free. What I wanted to do for myself was explore Free from first principles and implement some core functionality from the ground up to see how things work under the hood. This post is about what happened when I did this.
The first part of my journey was to take a trip on over to Edward Kmett's package
free, more specifically, the data definition: https://www.stackage.org/haddock/lts-9.4/free-4.12.4/Control-Monad-Free.html#t:Free
So we have our data definition with the name
Free taking two type parameters,
a. With this definition we have two constructors
Free. There are many good explanations of this structure and I won't get into it here. There are better explanations that I will provide below, but for now we will say that this data type describes and abstract syntax tree (AST) for general computation. Or in other words, we can write programs with it.
Alrighty, we have our data type and that's cool. But now we want to be able to do things with it. More specifically, we will make this data type an instance of three of our favourite typeclasses: Functor, Applicative and Monad. We will start from
Functor and work our way up the chain.
So already we have something interesting here. We cannot straight up define a
Free without saying that the
f inside is a
Functor. The reason being, that we need the power of
fmap to access the structure.
So let's think about what the type signature of
fmap looks like for
Free. Our regular
fmap looks like
fmap :: (a -> b) -> f a -> f b. If we substitute our data definition for
Free in there we get
fmap :: (a -> b) -> Free f a -> Free f b. Cool, so let's try implement it!
I'm going to use a little type hole driven development here and reason about the types. So the types in scope are:
So we need to do something with
freer and we know
f is a functor, thus we will reach for
This will get us some mileage. My thinking is that we have some sort of
Free f a inside that first
f and we will probably want to change it into a
Free f b. And you know what? That's exactly what we will do, and we have the perfect function
(a -> b) -> Free f a -> Free f b, also known as
Now the only thing we are missing here is that we unwrapped a
Free so we need to wrap it up again, and our final solution for this is:
Pure?!", I hear you cry out. Well you are not wrong and let's bang it out.
We just need to unwrap, apply and wrap up. Ezpz. So this is cool, we have a
Functor instance for
Free so we can lift functions into our
Free structure; very nice!
Now that we've defined
Functor for the
Free data type, we are free to define
Applicative (I promise that's the first and last time I will make that pun).
Again, we start by saying that we need
f to be a
Functor so we have enough power in our hands to get things working. First off let's get a quick refresher on
Applicative. To define an
Applicative we need to define two functions
(<*>). Let's make things super clear and write out the types for these functions when we talk about them with
Let's get some of the easier things out of the way.
I think these last two are super cool, because they are actually just
fmap once we unwrap the function from
Pure! So we can write this more succinctly as:
We have two cases left, both of which have something like
Free freeFunc on the left hand side of our
<*> operator. Now I am not gonna lie, this one really tripped me up because I was fighting with myself and the compiler implementing them. Maybe you see the solution already, and if so nice one! But what I am going to do here is take you through my struggle. My initial template looked like the following:
There was a couple of things I knew. First I had to unwrap some structure and was going to end up applying
<*> recursively. Let's look at the types we have to work with now.
So we are posed with the challenge of accessing the things inside our
f. We should be immediately thinking
fmap here! So let's try add to our solution:
Our next step was to
freeFunc to get to our inner
Free f (a -> b) and then we want to
<*> to some
_innerFreer, not knowing what that is, yet. Finally, wrapping it back up in
Free. So that leaves us with
_innerFreer being the type of
Free f a and we still have to use
freer. So let's try add it in.
Here we will get some noise (I say noise, but it's actually really helpful) from the compiler about the following errors:
Well, if we remember that we unwrapped our
freer. When we unwrap we need to rewrap! So we finish it all of by doing:
So we have one last case to implement with
Free on the left hand side and
Pure on the right.
As usual we will start off by looking at what types we have to work with:
Somehow we are going to have to get into the
f of our
freeFunc, and I am sure you are seeing the pattern now, we have to use
So the last thing we need is to fill in the
_iWantToBreakFree hole. If we think about what type this is we will come to the conclusion it needs to be a
Free a. There's only one
Free a we can construct and that is
And that is it! We have completed the
Applicative instance for
Free. I know what you are thinking now, "But Fintan, you said you had trouble with this one?" and you would be right to ask. So two things, I failed to tease out the full implementation with the
Free constructor on both sides, until writing this. So I ended up cheating and looked at the source to get the answer. BUT! I did learn that you can abstract the last two cases. So I will show you the easier way of doing them and explain what is happening.
Damn that is nice! So what's up here? As usual we need to unwrap but this time we are only doing the left hand side. "Why are we only unwrapping the left hand side?", I hear you ask. Very good question, you are an astute reader (more astute than me, anyway). Well let's look at the types!
So, we know we want to apply
<*> recursively. When we
fmap into the inner part of
freeFunc and want to use
<*> all we are looking for is a
Free a. Look what we have here, it's a
Free a going by the name
freer. Making the whole thing easy for us.
We are onto the final of our three. We are going to put the
Free Monad! We will gloss over
return since it is the same as
pure. What we will look at more closely is
(>>=) . So as we usually do, let's take a look at the types.
That's cool. We have our
Free f a then a function
a -> Free f b and get out a
Free f b. Let's get started with the implementation!
This one is easy money, unwrap our
a and apply our function
k and, hey presto, we have a
Free f b. Moving onto the
Free constructor case.
Hmmmm, what should we do? Oh ya, the same as every other time!
fmap over, apply recursively and wrap it all up again.
Some Helpers From my Friends
This is awesome, we have our instances, which from the look of the
free there can be many more! But instead, we will define two functions that will help us in our endeavour of writing a DSL using
Free. These two functions will be
liftF allows us to lift any
Functor into a
Free structure and
foldFree allows us to fold our
Free structure into a
Monad. The first is useful for writing helper functions to describe actions in the DSL and the second is helpful for interpreting our DSL into some
Let's look at
My first instinct is to use the
Free constructor on our
Functor but that does not give us what we need. To explain, we want a
Free f a but the constructor
Free needs a
f (Free f a). So to turn the inside of our Functor into a
Free will utilise
Pure. Our final definition is:
Next up on our list is
To quickly explain, the first parameter to
foldFree is a function going from any
f x to a
m x. This is called a "natural transformation" if you want to explore this concept more. The
forall x. says that this function must work for any
x but we don't know what
x at this time. We then use this function to fold down our
Free f x structure to the
m. Let's get into the thick of it and implement it.
Let's do the easy case first:
We extract our
Pure and use the
pure to place in that context instead. Next up:
Let's see what we have here:
We don't have our trusty
fmap here because we never said
f was a functor, so there's really only one thing we can do, and that's apply
Let's just think about what this gives us in terms of types:
So when we apply it we actually have a
Free f a inside it. Well what can we do next to break down that inner
Free even further? Well since we are working with a
Monad we can utilise
Again we should ask, what is the type of
_iWantToFoldFree? Well using the type signature of
(>>=) we can figure this out. If
k freer is
m (Free f a) and our result should be
m x due to our
foldFree type signature, then we would expect:
Hmmm, that function in the middle of our signature looks pretty familiar... That's right! It's our
foldFree with the natural transformation already applied! And of course we can feel at ease with this solution because it's recursive.
Well damn, that turned out to be quite the lengthy article just to explain a few functions, but this actually gives us enough power to write as many DSLs as we want. On top of this we now understand how
Free actually works and not just how to use it! That's something extremely useful in itself.
Something else we can learn from this is that type driven development is amazingly useful. When we constrain ourselves to certain typeclasses and polymorphism we can only do so many things. This way our solutions tend to "fall out" and we can reason about what our program is doing. Then we can utilise the polymorphism, writing the implementation once and reusing many times. Very cool!
If you want to see some actual code with rambling comments that inspired this article you can check out free-me. On top of that there's a mini IO DSL example that everyone seems to write as their Hello, World of
Free. I will probably write about that next time. Maybe.
And as promised, here is some resources on
If you have any feed back, questions or further information you can reach out to me. I'm alway
Free for a chat (I lied there's the second pun).