In this chapter and the previous chapters, we represented sequenced computations with monads. The flatMap method of the monad describes how the computation steps should be joined and the function given to it as an argument—the computation step itself. The free monad elevates the concept of sequenced computations to the next level. 

First, we start to represent the computation steps as instances of some ADT (algebraic data type) of our choice. Second, we represent the monadic concept with instances of another ADT. 

To substantiate this approach, we can turn to the fishing example once again. Earlier, we had three actions we encoded as functions. These actions will be represented as value classes now. We also need to give specific meaning to the type aliases we've used before to be able to run examples later.

Here is the definition of the fishing model and corresponding ADT as follows:

case class Bait(name: String) extends AnyVal
case class Line(length: Int) extends AnyVal
case class Fish(name: String) extends AnyVal

sealed trait Action[A]
final case class BuyBait[A](name: String, f: Bait => A) extends Action[A]
final case class CastLine[A](bait: Bait, f: Line => A) extends Action[A]
final case class HookFish[A](line: Line, f: Fish => A) extends Action[A]

In the model, we represent some properties of the bait, line, and a fish so that we can make use of them later. 

The Action type has a few aspects worth discussing. First of all, the instances of Action reflect that the functions we had before take a single parameter by declaring this parameter as a field of the class. Second, all actions are typed by the type of the next action and this next action is captured as another field of the class, in the form of a function which expects the result of the wrapping action to be an argument. This second field is how we encode the sequencing of actions.

Now we need to represent the monadic methods as classes.

Done assembles an instance of Free from a value the same way as Monad.unit does:

final case class Done[F[_]: Functor, A](a: A) extends Free[F, A]

The F[_] refers to the type of actions to wrap and A is the type of the result. F needs to have a Functor; we will see why in a moment.

The Join constructs a representation of flatMap—it should do so by applying the F to the previous instance of Free. This gives us the following type of action parameter as follows:

final case class Suspend[F[_]: Functor, A](action: F[Free[F, A]]) extends Free[F, A]

Now, as we said, this is a monad, so we need to provide an implementation of flatMap. We'll do this on the Free so that it is possible to use both instances of Done and Join in for-comprehensions as follows:

class Free[F[_]: Functor, A] {
  def flatMap[B](f: A => Free[F, B]): Free[F, B] = this match {
    case Done(a) => f(a)
    case Join(a) => Join(implicitly[Functor[F]].map(a)(_.flatMap(f)))
  }
}

The flatMap naturally takes the Kleisli arrow as an argument. Similar to the definitions of flatMap on other monads, for example, an Option, we distinguish between shortcutting and exiting and continuing the computation chain. In the former case, we can just apply the given function; in the latter case we have to build up the sequence. This is where we're using the Functor[F] to get inside the F and apply the flatMap on the wrapped Free[F, A], basically doing the sequencing in a good, old monadic way.

The fact that the functor is here to give us the possibility to succeed in computations dictates how the functor for our actions should be implemented —the given function should be called on the result of the next action. Our actions might have quite a different structure, hence the easiest way to describe this approach is pattern matching, as follows:

implicit val actionFunctor: Functor[Action] = new Functor[Action] {
  override def map[A, B](in: Action[A])(f: A => B): Action[B] = in match {
    case BuyBait(name, a) => BuyBait(name, x => f(a(x)))
    case CastLine(bait, a) => CastLine(bait, x => f(a(x)))
    case HookFish(line, a) => HookFish(line, x => f(a(x)))
  }
}

Values of our ADT are structured similarly and this is the reason why the tranformations look alike for all actions.

The last preparation step we need is to have a user-friendly way to create instances of the free monad for each of the actions. Let's create helper methods for that in the following manner:

def buyBait(name: String): Free[Action, Bait] = Join(BuyBait(name, bait => Done(bait)))
def castLine(bait: Bait): Free[Action, Line] = Join(CastLine(bait, line => Done(line)))
def hookFish(line: Line): Free[Action, Fish] = Join(HookFish(line, fish => Done(fish)))

Each of these methods creates a free monad instance which describes a computation consisting of a single action; the Done(...) encodes the fact that we are, well, done, and have some result.

Now we can use these helper functions to build a computation chain like we did before. But this time the computation won't be something callable—it is just a sequence of instances of the free monad captured as a single instance of Free, as follows:

def catchFish(baitName: String): Free[Action, Fish] = for {
  bait <- buyBait(baitName)
  line <- castLine(bait)
  fish <- hookFish(line)
} yield fish

This single instance we have incorporates all of the steps in the form of Free containing actions. Represented as pseudo-code, the result of calling this method would look like a nested structure, as given below:

Join(BuyBait("Crankbait", Join(CastLine(bait, Join(HookFish(line, Done(fish)))))))

At this moment, we have created the computation sequence, but this sequence is useless because it's just a data structure. We need a way to make it useful—we have to create an interpreter for it. And this is where the free monad really starts to shine—it is up to us how we will render this data. We can create as many interpreters as we wish, for example, one for testing purposes and another for production use. For instance, for testing, it might be useful just to collect all of the actions which should happen in some journal—in an event-sourced way (we'll look at event sourcing in detail later in this book). As we're just testing, our journal does not need to be persistent—hence, we can just use some kind of collection; for example, a List would do, as follows:

@tailrec
def goFishingAcc[A](actions: Free[Action, A], log: List[AnyVal]): List[AnyVal] = actions match {
  case Join(BuyBait(name, f)) =>
    val bait = Bait(name)
    goFishingAcc(f(bait), bait :: log)
  case Join(CastLine(bait, f)) =>
    val line = Line(bait.name.length)
    goFishingAcc(f(line), line :: log)
  case Join(HookFish(line, f)) =>
    val fish = Fish(s"CatFish from ($line)")
    goFishingAcc(f(fish), fish :: log)
  case Done(_) => log.reverse
}

The preceding snippet is indeed an interpreter for the program which is built in terms of the actions wrapped in Free. The logic is repetitive—we're producing the result of the action and calling this action recursively, passing the log with the added entry as a parameter. In the case of Done, we're ignoring the result; our goal is the log, and we return it in reversed form by calling .reverse to compensate for building it up in the opposite direction.

The result of the execution looks like the following:

scala> import ch10.FreeMonad._
import ch10.FreeMonad._
scala> println(goFishingAcc(catchFish("Crankbait"), Nil))
List(Bait(Crankbait), Line(9), Fish(CatFish from (Line(9))))

For production, we can do something else, such as collecting the executed actions. We will model this side-effecting by writing to the console, as follows:

def log[A](a: A): Unit = println(a)

@scala.annotation.tailrec
def goFishingLogging[A](actions: Free[Action, A], unit: Unit): A = actions match {
  case Join(BuyBait(name, f)) =>
    goFishingLogging(f(Bait(name)), log(s"Buying bait $name"))
  case Join(CastLine(bait, f)) =>
    goFishingLogging(f(Line(bait.name.length)), log(s"Casting line with ${bait.name}"))
  case Join(HookFish(line, f)) =>
    goFishingLogging(f(Fish("CatFish")), log(s"Hooking fish from ${line.length} feet"))
  case Done(fish) => fish
}

The structure of this interpreter is naturally the same as before. The result type of the computation is Unit—everything we do is side-effecting, so there is no need to pass anything around. Instead of accumulating actions into the log we are just writing a report directly to the console. The case of Done is also little different—we're returning the fish, the result of the performed combined action.

The result of the execution changes as expected, as follows:

scala> println(goFishingLogging(catchFish("Crankbait"), ()))
Buying bait Crankbait
Casting line with Crankbait
Hooking fish from 9 feet
Fish(CatFish)

We managed to implement a very basic version of the free monad along with a small fishing language and two different interpreters. It is quite a bit of code so it's time to answer an obvious question: for what purpose do we invest this additional effort?

The free monad has obvious advantages; we touched upon these, and they are as as follows:

• Gluing the computations together as classes happens in a heap and saves stack memory.
• It is possible to pass the computation over to different parts of the code and the side-effects will be deferred until it is explicitly run.
• Having multiple interpreters allows for different behaviour in different circumstances.
• This chapter's scope has not allowed us to show how different "languages" (ADTs) can be composed into one algebraic structure, which then can be used to define the logic using both languages at the same time. This possibility offers an alternative to the monad transformers and monad transformer stacks, for example, a language that combines business terms and persistence terms.

The disadvantages lie in the same plane as they do for monads. These include additional initial implementation effort, runtime overhead for the garbage collector, and processing additional instructions and mental overhead for developers new to the concept.