An introduction to Free Monads
Free Monads solve the very same problem as Tagless Final but in a different way. Our goal is the same: we want to decouple or abstract the implementation details from the application code. If you recall our previous post, we did this by using expressions or functions that would be injected into our application code. We separated the description of our program from its interpretation which came from an interpreter. This time we’ll do the same but instead of relying on expressions we’ll use data.
Algebraic Data Types
What do I mean by using data rather than expressions. Let’s go back to our previous post, there we had the following:
We can represent the very same set of instructions (or algebra in the FP world) as data:
We’ve just translated some functions into what’s called an Algebraic Data Type (ADT). Note that the return type of our previous functions now has become into a parametric type. Also note we haven’t defined anywhere which effects will use.
Basically we could say that a program is a set of instructions that are executed one after the other. There’s an FP structure that lets us execute things sequentially this is: the Monad. Even if you are not that familiar with the concept of a Monad, if you have been using Scala for any amount of time you will have been taking advantage of the Monadic properties such as flatMap, and further Scala’s syntactical sugar around that in the form of the for comprehension. Here’s an example:
In scala Future is a Monad and has the flatmap function. For comps add syntactic sugar to make flatmap chains more readable. If you were timing this snippet you’d see it takes 3 seconds to execute rather than 2, even though Futures are concurrent. They were executed sequentially.
If the ADT was a monad, it would be possible for us to write the following code since we’d had flatmap:
Now that our ADT is monadic so we can implement recreateIndex in terms of a for comp:
This code is perfectly valid and will compile, unfortunately it won’t do anything as it is. We haven’t even defined if this code will be synchronous or asynchronous, we just know that in order to recreate and index we delete it first and then we create it again.
The implementation details will come from an interpreter as we did with Tagless Final. Here’s a synchronous interpreter:
Free monad is a way to turn a set of instructions (algebra) into a way to express sequential programs, it is an alternative implementation of the Interpreter pattern and an alternative to the Tagless Final pattern we looked at previously.
About the author