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 Option
, 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.
The monad M[A]
has two important functions:
where 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 S[A]
into Free[S[_], A]
in the companion object Free
.
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 Instruction[A]
into Free[Instruction, A]
.
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.
The program
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.
Interpreter
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 NaturalTransformation
from F
to 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 Instruction
to Id
. Computations
object has all the functions that are necessary to compute a new position. Functions used in first 4 cases return value of type Position
which is equal to Id[Position]
. The Id
does not modify value, it is just a container that provides monadic functions.
If you put Position
value pos
into 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 f
.
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 program
was 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.
Another Interpreter
Let’s assume we want to move on a surface that has only non-negative coordinates. Whenever the value of x
or y
in Position
becomes negative we want to stop further computation. The simplest solution is to change the interpreter so that it’ll transform Instruction
into Option
.
Function foldMap
is using the flatMap
function of the Monad
that our Instruction
is transformed into. So if we going to return None
then the computation will be stopped. Let’s implement it.
We defined 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.
Composing
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 – PencilUp
and PencilDown
, but they will be in other instruction set. First thing is defining PencilInstruction
The problem with the program type is that PencilInstruction
and 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 Either
. 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 Instruction
or PencilInstruction
set 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
Moves
and 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 cats
.
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.
Summary
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.
Links
Do you like this post? Want to stay updated? Follow us on Twitter or subscribe to our Feed.
See also