Free Monads Explained (pt 1)
Building composable DSLs
🤔 Free monad?
The core idea of Free is to switch from effectful functions (that might be impure) to plain data structures that represents our domain logic. Those data structures are composed in a structure that is free to interpretation and the exact implementation of our program can be decided later.
💩 Imperative example
As a use case example we will take a program that asks for user’s name a greets him:
As usual, we will go through series of small transformations trying to generalize things and eventually come up with Free monad implementation.
📖 Creating an algebra
First off, lets define an algebra that represents our program. There are two clear and distinct operations:
Tellrepresents an action to tell something to a user. We don’t say how, it might be a standard out print, message on a screen, etc.Askquestions user for something and returns the answer.
The imperative program from above can be described as a List of Asks and Tells:
Instead of calling functions we construct a description of a program. In order to execute such program we need to know how to “execute” each individual UserInteraction and then simply map it over the list:
The interpreter (execute + run) is an implementation of our program description, this is the place where all mutation and side effects can happen.
By the way, our new program is slightly different from the first imperative program — instead of greeting user by his name it just says generic “nice to meet you”. Our UserInteraction data structure is not very useful right now, we don’t have a way of getting the values of previous Ask's and referring them in Tell. The steps are sequential and depend on the value of a previous computation. Sounds like a Monad, right? If our UserInteraction would be a Monad (and lets even say we already implemented pure and flatMap) that would allow us to rewrite our program like this:
Now we can compose our user actions and access computation results. The problem is that program not a List of instructions anymore:
By introducing monadic bind we lost the ability to introspect the data structure, there is no way of knowing what our resulting UserAction[A] was made of and interpret each step.
😴 Monadception
First, let’s change our Ask to ‘return’ a value of a proper type in order to capture it in the monadic bind:
We know that UserInteraction needs to be monadic, be able to compose sequential computations but at the same time preserve information about the computation steps. The flatMap operation takes an F[A], a function A => F[B] and returns an F[B], this is where information is lost, same as with regular functions composition we lose information about what were the original composed functions. What if we could go meta again and replace calls to flatMap with a data structure? Eventually I want to get something like this:
By introducing FlatMap and Return we captured what it’s like for something to be a Monad and this is what FreeMonad is:
Imagine the F[_] being our UserInteraction but it can be any type constructor and there are no constraints on the F being a Monad or something. Return and FlatMap are the analogy of pure and flatMap on the monad — putting a value in a context and gluing computation together.
Free is a recursive structure where each subsequent computation can access the result of a previous computation. This is all we need to build composable programs using plain data structures that are free to interpretation. Let’s return to this example:
We want to end up having this kind of structure but it would be awkward to write programs by directly creating data structures. Besides, scala has a nice syntax to make it easier — “for comprehension”. This is how I’d like to see our program:
To make that work we need two things:
Freehas to be a Monad (compiler will look forflatMapandmapdefined onFreetrait)- A way to construct values of
Free[UserInteraction, A]. We wantflatMapto be called onFree, not onUserInteraction(which is not a Monad and that’s the point)
💡 Free as a Monad
“For comprehension” is desugared into a sequence of flatMap calls ending up with map. They have to be defined on the Free trait:
flatMap has to deal with two cases: Return is simply about applying the f to the inner a, FlatMap is about creating the same FlatMap whose continuation created by composing self cont with the result of flatMaping f. Sounds complicated, sometimes its just better to follow the types and try to implement it yourself until it “clicks”.
Now we can do something like this:
🏗 Creating Free stuff
How do we actually construct a Free[UserInteraction, A]? There has to be a function:
toFree takes a Tell or Ask and returns a free monad constructed by FlatMaping the value with a function that will just yield the result. That allows us to do the following:
There is a trick to make the syntax nicer and not having to write toFree every time — make toFree available for implicit conversions:
Now thanks to Free being a Monad and having a way to implicitly create Free from Tell and Ask our program looks exactly how we wanted to write it in the first place.
🏋️♀️ Do you even lift, Free?
Looking at toFree signature we can spot an improvement — abstracting over higher order type constructor it can be written in a more generic way, not specific toUserInteraction:
The problem here is that now it matches concrete type constructors:
We would run into compilation errors trying to compile for comprehension. The workaround is quite simple:
- Define a type alias fixing
UserInteractionto be a generator forFreewhich will represent the program’s DSL - Create functions to construct DSL by lifting our algebra types
🏃 Running the program
So now we have a nice syntax and data structure representing our program, how do we actually run it? Similar to when we had just a List of instructions we can fold the Free executing each instruction. So currently our goal is: given program Free[F, A] traverse the Free structure evaluating each step and threading results to subsequent computations.
But first, lets start off simple with implementing runInteractionDSL for our concrete program InteractionDsl[A] and generalize to a Free[F, A] later. The first obvious thing to do is to pattern match on the argument:
How to run sub which is UserInteraction[A]? This can be either Tell[A] or Ask[A], both of them has different meaning and there is no direct way to run them. We can use our previously implemented execute function to run sub operations, getting result back, feeding it back to cont and recursively call runInteractionDSL:
📚 Generalizing over the algebra
Lets make a step towards more generic implementation. The runFree should be able to execute any Free[F, A], not just InteractionDsl[A](e.g. Free[UserInteraction, A]).
The execute function is specific to UserInteraction and it’s not applicable to Free[F, A]. It has to be a generic function that by given F[A] will give us A back and possibly do some effects. Also, it has to be provided by the user and passed into runFree:
That’s pretty much it, we can run any Free[F, A] by providing a program to run and a custom “executor” that interprets our algebra. Looks great, but we can do even better.
🐛 Natural transformation 🦋
There is one more thing that can be generalized and that our “executor” function. Looking at the signature F[A] => A is actually a special case of functor transformation F[A] => Id[A] where Id is just a type alias for A (type Id[A] = A). This kind of transformation between functors is called “natural transformation”:
FunctionK or ~>Natural transformation is just a function that maps values in one context to another (F[A] ~> G[A]). In our case it will map UserInteraction data types to an Id:
Previously Executor returned A which we could directly pass into continuation but now it returns G[A]. We can resolve it by requiring G to be a Monad and use flatMap to thread inner A into cont and return G[A]. The return value of runFree has to be G[A] instead of A as well:
Yay, finally we’re done. The real implementation that you might find in Cats is a bit different but most of that is about syntax and style — everything regarding Free is defined within the trait, NaturalTransformation is calledFunctionK, transform is apply, run is foldMap with curried arguments. The idea stays the same and hopefully our step by step approach served as a relatively simple introduction to the Free concept.
🤙🏼 More to come!
In part 2 we will talk about how to deal with multiple algebras, how interpreters can be composed and why would anyone use Free monads in the first place.
Highly recommend checking out this talks on Free monads:
