What is a free monad

Free Monads or: How I Learned to Love Independence

A close coupling of the description of program parts and their execution inevitably leads to problems, at the latest when testing the software. Therefore, this article uses practical code to explain how the concept of the free monad helps us to separate description and execution neatly and elegantly.

requirements

All code examples in this article are implemented with Scala. Since this article is practice-oriented, the examples are implemented with the help of the Cats library. Although the free monad is not explained theoretically, the concept of monads should be familiar. A great and simple introduction to this is provided by Functors, Applicatives, And Monads in Pictures. For the theoretically interested reader, further links are provided in some places.

To get you started, let's look at a typical problem related to side effects.

Not like that!

The following Scala code shows a simple implementation of an address book. To do this, we define a case class that represents an address and an object that offers the function for the persistence of the same:

The simple use of the repo directly from the business logic leads directly to several problems. What is wrong with that?

  • The program is difficult to test: Although tests are possible in integrative environments, it is difficult to carry out simple unit tests. There is no provision for the database backend to be excluded, so it must always be present when tests are carried out. Depending on the code structure, testing the actual business logic can therefore only take place with a great deal of effort.
  • Side effects are carried out immediately: A basic idea of ​​functional programming is the creation of referentially transparent programs, i.e. without side effects. These side effects should, if possible, only be carried out “at the end of the universe”. In the example, however, effects would be executed scattered in many places in the program. In particular, the function would produce different results if executed multiple times.
  • The interface is too special: The separation of description and execution is an important concept that leads to modular, excellently maintainable and testable code. In describing our address book operations, we shouldn't have to struggle with futures, eithers, and throwables. What is more, we are assuming a certain database (in this case an asynchronous one that uses exceptions), which is too closely interlinked in the business logic of our application and would therefore be difficult to replace.

A first step in decoupling such aspects is to formulate the operations as separate entities. This enables us to represent the necessary operations as data, which are then only carried out later.

Our little language

To formulate the operations as entities, we create a data representation for each operation. We summarize this representation as an algebraic sum type:

The type parameter of the trait determines the return type of our operations. Although these operations can be used to describe simple programs, for example through lists of commands, complex relationships cannot be formulated. It is not possible to reference read data without having a side effect, such as in the function. We would like to have a possibility here to be able to bind return values ​​(without executing the effect).

Free monad, to salvation!

We use the free monad from cats in this article. Cats is a Scala library that provides powerful abstractions from functional programming. In addition to the functionality of free monads, we will turn to further abstractions like the Natural transformations use from this library. The free monad will help us overcome the limitations of our little language. A systematic introduction to the internal functionality of free monads can be found in this article.

In order to be able to use our commands with the free monad of cats, we have to raise them into the monad. To do this, we create a so-called smart constructor for each command:

The smart constructors each receive the parameters of the, generate the operation and use it to raise the operation to the free monad. It returns a value of type (alias for), where is the expected return value of the operation. The definition of these smart constructors makes the description of the later programs easier. With the help of the definition, the function can simply be described as monadic. In particular, intermediate results can be linked:

By linking the intermediate values, complex programs can be formulated without having to talk about details of the execution: When formulating the program, neither throwables nor futures are considered. is another little help from the Cats library, for which we need the additional Cats imports. The running of the list of intermediate results can also be described by describing it.

Our new version of returns a value of type. This program description can be combined and thus reused:

Execution

So we now have a powerful representation to represent operations, reference intermediate results, and combine abstractions. What is missing is execution. To do this, we need an interpreter that receives and interprets (or compiles). To do this we define a natural transformation. To put it bluntly, we are transferring our programs from the free monad to a target monad. In the following example, the state monad is used as a simple address store:

In Cats, the natural transformation from to is described by the type (a functor transformation of the type). In our case we transfer to. The interpreter can be applied to a program of the type:

An interpreter for our original address book repo could then look like this:

As you can see, we are only confronted with the technical aspects such as futures and throwables when we are interpreting our program. There is a clear separation between description and execution. This goes so far that while we are formulating the logic we do not have to know who is executing our description and in what form. So far we have spoken of databases or repos. But nothing prevents us from implementing an actuator-based service as an address book. The resulting descriptions can easily be exchanged between actuators in the form of messages.

In this independence lies the charm of free monads.

Words about testability

A great advantage of the separation of description and execution is that the descriptions can be tested separately. In this way, descriptions can also be tested outside of integration tests without having to provide databases. That sounds charming at first, but with free monads it is more difficult than initially assumed. Descriptions represent abstract syntax, but they are in the form of a function and cannot be easily inspected at first. We can implement test interpreters like the state interpreter from the example above. However, there is a risk here that the test and the "real" interpreter will behave differently.

However, it would be conceivable to implement a very simple test interpreter which, for example, merely records the instructions that have been executed. In some cases, however, the behavior has to be implemented, especially if certain operations are only partially carried out by bound data. So if we want to test the content of the emerging programs, we have to enter into a trade-off between accuracy and the susceptibility to errors in the interpretation.

If there is a strict separation between description and execution, large parts of the code can still be covered in unit tests without having to offer an integrated environment. This decoupling often makes testing our business logic a lot easier. One possible synergy that illustrates this is in combination with the actuator-based observer pattern. Messages in the form of our descriptions based on the free monad help us with a clean separation between services and the exchange of flexible and complex instructions is still possible. All units can be tested separately and the business logic can be tested outside of the integration.

Résumé

In this blog article we implemented a small language with the help of the free monad using a simple example. This language has enabled us to express combinable descriptions without knowing what will be done later. Only through interpreters (or compilers) are the descriptions executed and details about the execution known.

The code used in this article is available on Github.

In the next post we will see how to implement the free monad from scratch in Scala.


About the author:

Simon Härer is a software architect at Active Group GmbH. He is particularly interested in functional programming, development methodologies and software architecture.