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.
New Beginnings
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, f and a. With this definition we have two constructors Pure and 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.
Functor
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 Functor for 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 fmap.
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 fmap!
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:
"What about Pure?!", I hear you cry out. Well you are not wrong and let's bang it out.
instance Functor f => Functor (Free f) where
fmap f (Pure a) = Pure $ f a
fmap f (Free freer) = Free $ fmap (fmap f) freerWe 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!
Applicative
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 pure and (<*>). Let's make things super clear and write out the types for these functions when we talk about them with Free.
instance Functor f => Applicative (Free f) where
pure :: a -> Free f a
(<*>) :: Free f (a -> b) -> Free f a -> Free f bLet's get some of the easier things out of the way.
— | Here we have a function wrapped in `Pure` and a `Free`
— | recursive structure.
(Pure f) <*> (Free freer) = Free $ fmap (fmap f) freerI 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 fmap over 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.
(Free freeFunc) <*> (Free freer) =
Free $ fmap (\innerFunc -> fmap (\inner -> innerFunc <*> inner) freer) freeFuncHere 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:
(Free freeFunc) <*> (Free freer) =
Free $ fmap (\innerFunc -> Free $ fmap (\inner -> innerFunc <*> inner) freer) freeFuncSo 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 fmap.
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 Pure a!
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.
Monad
We are onto the final of our three. We are going to put the Monad in 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.
instance Functor f => Monad (Free f) where
(Pure a) >>= k = k a
(Free freer) >>= k = _iWantToBreakFreeHmmmm, what should we do? Oh ya, the same as every other time! fmap over, apply recursively and wrap it all up again.
instance Functor f => Monad (Free f) where
(Pure a) >>= k = k a
(Free freer) >>= k = Free $ fmap (>>= k) freerSome 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 and foldFree. 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 Monad.
Let's look at liftF first:
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 fmap and Pure. Our final definition is:
Next up on our list is foldFree:
To quickly explain, the first parameter to foldFree is a function going from any f x to a Monad, 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 Monad , m. Let's get into the thick of it and implement it.
Let's do the easy case first:
We extract our a from Pure and use the Monad\'s pure to place in that context instead. Next up:
foldFree :: Monad m => (forall x. f x -> m x) -> Free f x -> m x
foldFree k (Free freer) = _iWantToFoldFreeLet'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 k to freer!
foldFree :: Monad m => (forall x. f x -> m x) -> Free f x -> m x
foldFree k (Free freer) = _iWantToFoldFree (k freer)Let's just think about what this gives us in terms of types:
So when we apply it we actually have a Monad with 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 (>>=).
foldFree :: Monad m => (forall x. f x -> m x) -> Free f x -> m x
foldFree k (Free freer) = k freer >>= _iWantToFoldFreeAgain 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.
foldFree :: Monad m => (forall x. f x -> m x) -> Free f x -> m x
foldFree k (Free freer) = k freer >>= foldFree kFinal Words
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 Free:
- http://dlaing.org/cofun/posts/free_and_cofree.html
- http://www.haskellforall.com/2012/06/you-could-have-invented-free-monads.html
- https://youtu.be/eKkxmVFcd74?list=WL
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).
