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:

https://gist.github.com/anonymous/06037497c1d291d3da38474363ece609

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:

https://gist.github.com/anonymous/b04e23770e69fb1f3e286596552611e3

But there is a convenient method for lifting S[A] into Free[S[_], A] in the companion object Free.

https://gist.github.com/anonymous/bfae79cf40b34272de3ccfc4d7cd41ac

Usage of this method looks like that:

https://gist.github.com/anonymous/dd04f9950adfce2ae421f49f7750be0a

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.

https://gist.github.com/anonymous/2aa14fd93f68e49494a830501c699ff0

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.

https://gist.github.com/anonymous/dfc78d8211e021c50c12289e1ed543e5

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].

https://gist.github.com/anonymous/0706d8143c2f33349abd43ed244e58b5

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:

https://gist.github.com/anonymous/118bc52627d63aca9fa877a8397b895b

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.

https://gist.github.com/anonymous/399358fce3cbe2193c8e193b06c49343

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.

https://gist.github.com/anonymous/d3a5bd03187d7cd786ed0a5270ef5c8e

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.

https://gist.github.com/anonymous/dcb3e9d0cad990cd93938a9e6a876da8

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.

https://gist.github.com/anonymous/f90ca2bffd5461b25063fc88d43bb1cd

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

https://gist.github.com/anonymous/1c26dcd1cd74acd4c6d810a28f660422

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

https://gist.github.com/anonymous/451c17650c677b2e2dfd04553bd84a4e

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.

https://gist.github.com/anonymous/32ff84bfab9eafb0dbb81bfcdf3d9fe7

Let’s define our common type.

https://gist.github.com/anonymous/2ad6158c73ee2b0001a2ee0bfe2498cc

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.

https://gist.github.com/anonymous/4e81c4dd044caa3d36a735262fd497c2

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

https://gist.github.com/anonymous/0f788993b925f91805552ccc0acf435e

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:

https://gist.github.com/anonymous/910f6a021798a9d0629552a1aacf6d05

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.

https://gist.github.com/anonymous/b074c4ee5d0b9068b619e8b0f185acd6

This is our second interpreter and the code merging it with the existing one looks like this

https://gist.github.com/anonymous/a652e57ca7f140e48551bc5931618779

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

• Cats Free Monad tutorial
• Eugene Yokota tutorial on Cats
• Rúnar Bjarnason talk about free monad

Do you like this post? Want to stay updated? Follow us on Twitter or subscribe to our Feed.

See also

• 9 Of The Best Unknown Tools For Learning A New Language
• When old-school developer goes freestyle
• Typelevel ecosystem: a high-level overview