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 NaturalTransformationfrom 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 Positionwhich 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 posinto 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 Instructionis 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 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
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
Authors
I'm a software engineer believing that choosing the right tools is the first step to solving the problems at hand. Usually I pick Scala. Its concise syntax and functional approach allows creating easily scalable applications quickly. To meet the growing demand of the market I also employ Akka toolkit to build robust and resilient distributed architectures. These tools are needed to build "the thing right", but understanding the problem domain is crucial. I use Domain-Driven Design to build a shared understanding and common vocabulary with domain experts.
