Overview of free monad in cats
Cats library, which helps to write purely functional code, is a quite young project in Scala. It brings many structures and functional constructs for you to use. The library itself is designed in a modular way, so we can use only things that we really need. In this post I’ll try to look at the Free Monad concept and implement basic functionality of LOGO programming language.
What is a Free Monad?
Basically, you can look at Free Monad as a way to describe your program. When I say program I mean set of abstract instructions. More precisely, instructions are some kind of AST (Abstract Syntax Tree) that represents computations. The Free Monad allows to combine them into functions, that later can be combined into higher level functions, which should improve composability of our code.
Moreover, the usage of free monad removes the necessity of tinkering with implementation details. Furthermore, API of our code isn’t strictly defined as
Future or other monads.
Such a description then must be interpreted, which basically means that we’re going to run it using an interpreter with an implementation of our AST. In the interpreter we start to worry about implementation details. But these details are separated from our business logic, what makes it easier to test. Moreover, the same function can be executed in different contexts, even using various interpreters. That makes this pattern very useful.
M[A] has two important functions:
A has to be a type constructor(
A[_]), which means that type
A needs to be parameterized by some other type. Using the
flatMap it’s possible to write our program flow control, working only on a defined instruction set.
What does the Free Monad look like in Cats? It’s defined as follows:
But there is a convenient method for lifting
Free[S[_], A] in the companion object
Usage of this method looks like that:
We’ll see how it works in practice.
Putting the Free monad to work
We gonna implement basic instructions from LOGO language – the famous “Turtle”. We will implement movement in a 2 dimensional space.
Creating set of instructions (AST)
Ok, let’s say we have some set of instructions that we want to use in order to create program. Using the LOGO example I would like to implement basic functionality like moving forward and backward, rotating left or right and showing the current position. To do that I’ve created a few simple classes to represent those actions.
These are just simple case classes. Type
A will be the type that Free Monad will be working on. That means if we use a
flatMap we will have to provide a function of type
A => Instruction[B].
There are also two classes that will be used. It’s a part of simplified domain model.
At this point we have defined only our actions with some additional types, but it does not compute anything, it’s abstract.
Creating the DSL
DSL is a Domain Specific Language. It contains functions that refer to the domain. Such functions make the code more readable and expressive. To make it easier to use I’ve created some helper methods that will create free monads wrapping our actions, by lifting
These methods are used to write the application and make it stateless by taking a position as a parameter and not storing it inside the function.
Now we can easily use our DSL. Having the methods in place we can use them in a for comprehension to build a program description. Let’s say we want to get from point (0,0) to point (10,10). The code looks like this:
As we can see the program is just a function that takes a starting position and moves the turtle. The result of calling the function is also a Free monad and that’s great news because it’s very easy to compose another function using this one.
We can simply think of creating functions to draw basic geometric shapes and then using these functions to draw something more complicated; furthermore, it’s going to compose very well. It’s like that because of referential transparency property of the free monad.
Another advantage is that we don’t worry how it is computed. We are just expressing how program should work using the DSL.
At this moment we have our program description, but we want to execute it. In order to do that a
NaturalTransformation is needed. It’s a function that can transform one type constructor into another one. A
G is often written as
F[_] ~> G[_].
What is important, is that we have to provide implicit conversion from
G to a
Monad[G]. It’s possible to have multiple interpreters, e.g. one for testing and another one for production. This is very useful when we create an AST for interacting with a database or some other external service.
The simplest monad is the identity monad
Id, which is defined in cats as a simple type container.
It has all necessary functions implemented and implicit value that is a
Monad[Id]. In the
cats package object there is an implicit instance that helps with conversion to an
Id. Let’s use it to write our own interpreter.
InterpreterId is defined as a natural transformation from
Computations object has all the functions that are necessary to compute a new position. Functions used in first 4 cases return value of type
Positionwhich is equal to
Id does not modify value, it is just a container that provides monadic functions.
If you put
Id[Position].pure(pos) it will return value
pos of type
Position. If you want to
map over the
Id using function
f: Position => B, it will behave the same as if you apply the
pos into the
Running the program
To run the
program we need to simply
foldMap it using the interpreter and pass a parameter to the function to start evaluation.
The result of this operation will be just a
Position because last the instruction of
forward and we yielded the result of it. When we look at the definition of
Forward we can see that it extends
Instruction[Position] and that type parameter specifies that we will have a value of
Position type as result.
Let’s assume we want to move on a surface that has only non-negative coordinates. Whenever the value of
Position becomes negative we want to stop further computation. The simplest solution is to change the interpreter so that it’ll transform
foldMap is using the
flatMap function of the
Monad that our
Instructionis transformed into. So if we going to return
None then the computation will be stopped. Let’s implement it.
nonNegative as a part of the interpreter – the reason is that it’s an implementation detail not connected to the business logic. And now if we run the program with such definition
It’ll not print the position, so we achieved our goal. We can easily think about another interpreter that could be implemented for this AST. It could be a graphical representation of our program.
Free Monads are a really powerful tool. One of the reasons is composition. Our example is rather simple, but you can imagine that you’ve built a whole instruction set for your business logic. It is completely separated from other code in application. Then you can add set of instructions for logging, accessing the database, failure handling or just another business logic but for some reason separated from the previous one. Each of such DSLs can be easily tested.
Writing the program doesn’t change much. You have to do some adjustments. Let’s say we want to add to our LOGO application two new instructions –
PencilDown, but they will be in other instruction set. First thing is defining
The problem with the program type is that
Instruction don’t have a common supertype, and they shouldn’t have. We need to define some type that will be either former or latter of these two type constructors and still be able to pass them type parameter.
Luckily, there is a
Coproduct, which is made exactly for such tasks. It’s a wrapper for
Xor type, which is more or less the same thing as Scala’s
Coproduct requires two type constructors and type that will be inserted into them. In this way we can make superset of two sets of instructions and create a supertype for them.
Let’s define our common type.
In application we will be using
LogoApp as a whole set of instructions. To make the mixing of these two ASTs possible we need to be able to lift both of them to
Coproduct type. To do this we have to change our lifting methods – instead of using
Free.liftF method we will use an injecting function.
It basically means that we can lift our
PencilInstructionset into the
Coproduct which is the superset of both of them. Because we want to be flexible about the
Coproduct types we will define classes wrapping our DSL. These classes will take type parameter, which will be corresponding to the
Coproduct. This is what our Logo definition will look like
PencilActions will be implicitly needed in our program. They gonna be parameterized by our
LogoApp type, and will have all methods lifted to
Free that will be operating on the
LogoApp. That means we can mix them in one for comprehension expression. Now our program definition will look like this:
The last step is to add an interpreter for
PencilInstruction and join it with previous one which is very easy thanks to functions offered by
This is our second interpreter and the code merging it with the existing one looks like this
As we can see, combining two sets of instruction is fairly easy. Mixing another one will be very similar, you just need to add another
Coproduct which takes as type parameters the
LogoApp and the other instruction set. Still, each of these DSLs can work separately and can be easily tested. That is a big advantage.
Summing up, Free Monad is definitely concept that make it possible to write functional code in easy and composable way. What is also very useful it helps you define your domain language and then just use it without bothering about implementation details. The code is readable and easily testable. The most difficult part is to grasp the theory and definitions that stays behind Free Monad. But it’s worth learning.