#### Free Monads

Free monads build on many of the previous concepts in this section and add some nice features. There are many scholarly papers on this topic. I found Runar's presentation from ScalaDays 2014 in Berlin especially helpful. Like with Monads, a cottage industry has cropped around describing Free Monads. To learn more, we point you to the web to find deeper descriptions. We have included a brief description.

Free Monads are often covered in the context of "interpreted languages" so we will use that thought in the next few paragraphs.

If you develop a "language" in your program you need to create an interpreter that interprets that language.

There are many different types of "interpreters" you can embed into a JVM-based language. For example, there is a scripting API where you can embed javascript or the language of your choice into a jvm-based program. The scripting language typically provides a general purpose "context" that stores computation results. The syntax is based on the scripting engine of choice.

Another way to create an interpreted language without using a scripting engine is to create an Abstract Syntax Tree (AST) using the type system in your language. Then an interpreter interprets the AST. In the typical approach, you need some type of "context" that stores intermediate computations. Other approaches may be more clever.

A variation of the AST approach is to create an instruction stream. Instead of retaining an AST per se, you directly compose an instruction stream that is executed by the "interpreter." In most implementations, a "context" is still needed to store intermediate computation. If you have a list of instructions, you need to walk over the list to execute them--you need to fold over them. If each instruction is itself a Functor, then you need to fold and map at the same time. In the Free Monad literature this is called `foldMap`

. `foldMap`

is fairly general and can be applied to a list of instructions or an AST to run the instructions.

A Free Monad is a design pattern for creating interpreted languages but there are other uses as well.

For example, consider the following for-comprehension:

```
for{ a <- Some(1)
b <- aFunctionCallReturningOption(a, "blah")
} yield b
```

In a for-comprehension, a single Monad type needs to be used for each line (that is, each `flatMap/map`

desugared level). In the example above, the Monad is `Option[Int]`

. All of your functions need to be lifted or projected to return on `Option`

. This can be inconvenient and awkward to maneuver all of your return values to the same monad. Each function call on each line of the for-comprehension could return a different Monad. You could use a Monad transformer to transform one Monad into another but transformers become awkward quickly. Another approach is to use a Free Monad.

If you use a Free Monad, each line of a for-comprehension can have a different Monad and each of those Monad types are lifted into a Free monad, and hence, a common Monad is actually used in the for-comprehension. Each instruction, each line of the for-comprehension, can have a different monadic return type. It's much like the concept of "one more level of indirection" can solve many problems.

A Free monad is a monad whose flatMap does not impose any constraints on the Monad you can return. Instead of being constrained by a rigid flatMap definition, you are "free" to choose the monad to flatMap into.

This is why Runar mentions in his talk that Free Monad's subsumes dependency injection because you can setup your dependencies in the for-comprehension and use them directly in the `yield`

part to perform a computation. All of the dependencies are available using the variable assignment in the for-comprehension.

A Free Monad is a Monad derived from a Functor with the ability to specify the `flatMap`

without "constraints." Category theory has a precise definition of a Free Monad that we will not use here.

A Free Monad can be directly derived from a Functor without you the programmer having to specify the `flatMap`

rigidly e.g. you do not have to force the return value to be the same monad because you can cast the the entire monad into the same Monad. But like anything that sounds "free", an assumption has to be made, somewhere, that allows you to turn a Functor into a Free Monad. In other words, you do not fixate on the flatMap, you fixate on the Monad itself.

A regular Monad is already a Functor so you can turn a regular Monad into a Free Monad. The original Monad's `flatMap`

becomes "overridden." A Free Monad that was created from a Monad often renders the new Monad a "forgetful Monad" because the existing `flatMap`

is not fully used. A Free Monad is itself a Monad. Because it can take a regular Monad and transform it into another Monad, a Free Monad is also a Monad transformer.

The core assumption made that allows you to turn a Functor into a Free Monad with great flexibility into what the flatMap does is quite simple. We should motivate it with an example first using the "instruction stream" idea discussed earlier.

Assume that you wanted to create an instruction stream. Each instruction has a type, say `I`

. To create a set of instructions, you could easily use tuples to create a "list."

```
(I,(I,(I,(I,A))))
```

But this formulate is a very difficult to work with because each instruction stream would be a different type. If you add another instruction to the "list" you are creating another type. It is impractical to have a different type for each instruction stream. You will also have to create a new interpreter to interpret the instruction stream that matches the instruction stream type--an exhausting thought to contemplate.

First, lets assume that each instruction in the list is a Free Monad. Why make this assumption? A Free Monad, just like a Monad, is like a context with a value inside. That value could be a value like an Int or it could be another instruction. When each instruction a Free Monad, the instructions can express greater computation complexity while still being reasonably easy to manipulate in a program. Since each instruction is a Free Monad, we must also wrap the value `a`

represented by type `A`

. Since each instruction is chained to the instructions that come after it, we need a way to chain the next instruction. We know that `flatMap`

sequences operations. We need some way to group together the current instruction together with the next instruction. `flatMap`

is known as `bind`

so we can use Runar's notation:

```
trait Free[F[_], A]
trait Pure[F[_], A](a: A) extends Free[F, A]
trait Bind[F[_], I, A](instruction: F[I], next: I=>Free[F,A]) extends Free[F, A]
```

`Pure`

allows us to lift a value into the Free Monad. `Bind`

enables us to chain together the current instruction with the next instruction. Instead of directly specifying the next instruction, a function should be provided that returns the next instruction given the current instruction. This allows the instruction stream to branch or perform other sequencing logic. Given the definition above you can also see that you are limiting `next`

to either a `Return`

or more instructions via `Bind`

. `F[_]`

is your instruction set that you create.

The two subtraits have essentially the same type signature as the methods on a Monad:

```
trait Monad[F[_]] {
def pure[A](a: A): M[A] // also called point
def flatMap[A,B](ma: M[A])(f: A->M[B]): M[B] // also called bind or >>==
}
```

By comparing these two code blocks, we can see that we are building a Monad by recursively iterating on the Monad itself through the `f`

parameter in `flatMap`

. As a programmer creates the `flatMap`

s in textual programming code, you are adding "instructions" to the instruction list. The chained structure returns the next instruction in `f`

as a function so that you can specify the logic that creates the next instruction. You accumulate structure as you type in your `flatMap`

s and you are skipping the "reduction" process (the "join") that would eliminate multiple layers of nested Monad structure. This means you are only using `pure`

and `map`

to create the Monad as `flatMap`

is a combination of `map`

and `join`

. Because the reduction never happens and you only need to specify `map`

. You can also see that if the `F[_]`

is already a Monad, it will ignore that Monad's `flatMap/bind`

and only use the `map`

part. Hence the common term "forgetful Monad."

A Free Monad, because it can transform another Monad or Functor into a Monad, allows us to take any set of "instructions" and turn them into a Free Monad. We can have many different instruction sets but each needs to eventually lift into the Free Monad so they can be composed together.

The Free Monad is wrapping the existing Functor/Monad. In the for-comprehension example earlier, we had the problem where we wanted to use different Monads in the for-comprehension. By transforming an existing Monad into a Free Monad we can then use Free Monad's in each part of the for-comprehension. This is the same thing as specifying an instruction stream. All that is needed is to convert the existing Monads into a Free Monad.

To convert a set of Monad's into a Free Monad, you need to create a Coproduct. In the Coproduct section, we mentioned that an example of a Coproduct is `Either`

. Either can be either type `A`

or type `B`

. Generalizing this, if you have several Monad types that need to be converted to a single type so that it can be transformed into a Free Monad, you need to specify the Coproduct of all the disjoint types in your "instruction" set. If you want to merge an Option, a String and a List as Monad's, you would form a Coproduct of an Option, String and List by "injecting" those values into the Coproduct. Then you would lift the Coproduct into the Free Monad. Your Free Monad can now describe any instruction in your Coproduct.

The Free Monad is a bit complex so the links below can help you find out more about Free Monads. The first one is Runar's presentation.

- Reasonably Priced Monads
- Monads for Free
- Monads for Less
- Free Monads Part 1
- Running free with monads
- Cool Idea Free Monads for Testing Redis Calls
- Applicative
- Scalaz getting to grips free monad
- The Free Monad
- Type families make life and free monads simpler
- Purify code using free monads
- Free Monads
- Comparsion of 4 approaches to implementing url routing combinators including the free and operational monads
- Control monad for free
- The monad called free
- Cofree meets free
- Meta programming with the free monad
- Bjarnason trampolines
- Abstracting with applicatives

The Free Monad is used in fs2 to create "instruction streams" for obtaining items from a stream and applying an algorithm to those items. My using a Free Monad, evaluation can be delayed and concurrency/parallelism controlled more explicitly.