In part one of this post, we talked about how Free Monad can build a monad from Functor. To do so, you can create a DSL like programs and generate another program. The program that you make becomes plain data structures that represent a domain logic. Once you composed the program, you can connect those programs with an interpreter. You can switch a different interpreter on dev and QA. You can also abstract out the implementation of your program or optimize them without changing your domain logic.

We started by creating a Todo application with these algebras:

```
case class Todo(id: Long, description: String, isFinished: Boolean)
sealed trait Action[T] extends Product with Serializable
case class Create(description: String) extends Action[Todo]
case class Find(description: String) extends Action[Option[Todo]]
case class Mark(id: Long) extends Action[Unit]
case class Delete(id: Long) extends Action[Option[Todo]]
case object Read extends Action[List[Todo]]
```

First, we created an algebra `FlatMap`

and `Pure`

and introduce what it’s like to make a monad like programs by wrapping our Todo algebras into the “Free” data structure:

```
sealed trait Free[F[_], A] {
import Free._
def flatMap[B](fn: A => Free[F, B]): Free[F, B] = this match {
case Free.Pure(a) =>
fn(a)
case Free.FlatMap(fa, fun) =>
FlatMap(fa, fun andThen (a => a.flatMap(fn)))
}
def map[B](fn: A => B): Free[F, B] = flatMap(a => Pure(fn(a)))
}
object Free {
final case class FlatMap[A, B, F[_]](fa: F[A], fun: A => Free[F, B]) extends Free[F, B]
final case class Pure[F[_], A](a: A) extends Free[F, A]
}
```

Then, we created a way to “lift” these algebras to a “Free” monad by creating an implicit conversion of `Action[A] => Free[Action, A]`

:

```
implicit def lift[A](fa: Action[A]): Free[Action, A] = FlatMap(fa, Pure.apply)
```

Lastly, we ended with connecting the program and the interpreter with our “Free” algebras that we construct.

```
def runProgram[A](program: Free[Action, A]): A = program match {
case Free.Pure(a) => a
case FlatMap(fa: Action[A], fn: (A => Free[Action, A])) =>
// execute the Action here
val res = execute(fa)
// thread the function into a new Free
val newFree = fn(res)
// execute the next function
runProgram(newFree)
}
```

Note: This is the short recap from “Explain Free Monad like I’m Five (Part one)” I explain my thought process on how I came up to these conclusions. If you are interested, check it out before reading further.

## Problem

The above solutions seem to work for constructing a program using Free Monad for a Todo Application. However, that solution will only work for that particular application. We cannot use our `runProgram`

function or “lift” our algebras to a “Free” version. It will be quite tedious if we need to implement the `runProgram`

for every program that we construct and also creating an implicit conversion each time we build a new set of algebras.

## Generalizing Lift

To generalized lift, we just need to abstract out `Action`

to an `F[_]`

type constructor:

```
implicit def lift[F[_], A](fa: F[A]): Free[F, A] = FlatMap(fa, Pure.apply)
```

However, if we do this, it will cost compile error because a lot of the times, we will want to lift concrete type constructors instead of the generic “sealed trait”:

```
val create: Free[Create, String] = lift(Create("Check Homework"))
```

This will throw an error in for-comprehension because it cannot automatically lift the value to the `Action`

sealed trait.

One way to do this is to create a “smart-constructor”, by first setting the value as the generic algebra `Action`

, and defined the function that abstract out regular input to a “free” version of it.

```
type TodoAction[A] = Free[Action, A]
def create(description: String): TodoAction[Todo] = lift(Create(description))
def find(description: String): TodoAction[Option[Todo]] = lift(Find(description))
def mark(id: Long): TodoAction[Unit] = lift(Mark(id))
def delete(id: Long): TodoAction[Option[Todo]] = lift(Delete(id))
def read: TodoAction[List[Todo]] = lift(Read)
```

Remember that the return of the “Free” type is defined by the generalized algebra return type. For instance, `create`

will return a `TodoAction[Todo]`

because the algebra for `Create`

returns an `Action[Todo]`

:

```
case class Create(description: String) extends Action[Todo]
```

Then we can construct our program with these smart constructors:

```
val program =
for {
todo <- create("Do Laundry")
_ <- mark(todo.id)
listOfTodo <- read
} yield {
println(listOfTodo)
}
```

## Generalizing RunProgram

Referencing from the `runProgram`

from the previous article:

```
def runProgram[A](program: Free[Action, A]): A = program match {
case Free.Pure(a) => a
case FlatMap(fa: Action[A], fn: (A => Free[Action, A])) =>
// execute the Action here
val res = execute(fa)
// thread the function into a new Free
val newFree = fn(res)
// execute the next function
runProgram(newFree)
}
```

The current run program has an `execute`

function tied to the ones with `Action`

. Moreover, `Free[Action,A]`

is restricted to the particular `Todo`

application. How can we generalize this further to take any program of `F[_]`

?

We can generalize the `runProgram`

by taking a type constructor `F[_]`

, but how will we generalize the `execute`

function?

```
def runProgram[F[_], A](program: Free[F, A]): A = program match {
case Free.Pure(a) => a
case FlatMap(f: F[A], fn: (A => Free[F,A])) =>
val res = execute(fa) // where is this execute come from?
val newFree = fn(res)
runProgram(newFree)
}
```

Somehow, the `execute`

function should be a generic function that the user defines when creating the program. Therefore, it needs to be some `trait`

that will need to pass in as an argument. If you look closely at the implementation above, the function `execute(fa)`

takes in an `F[A]`

and returns an `A`

. That `A`

, then, can be an input to the `fn`

function. Therefore, we need to define the `execute`

function that takes an `F[A]`

and returns an `A`

. Let’s define the `execute`

function inside an `Executor`

trait:

```
trait Executor[F[_]] {
def execute[A](fa: F[A]): A
}
```

We pass in the `Executor`

trait class as an argument in `runProgram`

, and call the `execute`

within that `Executor`

trait:

```
def runProgram[F[_], A](program: Free[F, A], executor: Executor[F]): A = program match {
case Pure(a) => a
case FlatMap(fa: F[A], f: (A => Free[F, A])) =>
val res = executor.execute(fa)
runProgram(f(res), executor)
}
```

Then, we can define our interpreter for Todo application in the `Executor`

, `execute`

function and pass the value into the `runProgram`

:

```
runProgram(program, executor)
```

We finally can run `Free[F,A]`

on any programs by providing the custom “execute” that interprets our algebra. However, can we generalized this even further?

## Generalizing Executor

The current `Executor`

function takes in an `F[A]`

and returns an `A`

. However, this function is limited to the pure effect type. We can somehow generalize this further by generalizing its effect type. If you are unsure about what effect means, check out my article on What is “effect” or “effectful” mean in Functional Programming? | edward-huang.com.

This kind of transformation between functors is called natural transformation. Instead of having a signature of `F[A] => A`

, which is equivalent to `F[A] => Id[A]`

, we can have `F[A] => G[A]`

where `G[_]`

can be any type constructor.

Let’s refactor our `Executor`

function to take in 2 type constructor:

```
trait Executor[F[_], G[_]] {
def execute[A](fa: F[A]): G[A]
}
```

Then, `runProgram`

will take an additional type constructor `G[_]`

:

```
def runProgram[F[_], G[_], A](program: Free[F, A], executor: Executor[F, G]): G[A] = program match {
case Pure(a) => a
case FlatMap(fa: F[A], f: (A => Free[F, A])) =>
val res = executor.execute(fa)
runProgram(f(res), executor) // something is not right here ....
}
```

You noticed that the above code would not compile. Initially, `execute`

function returns `A`

. However, after changing our `Executor`

function to return `G[A]`

, we cannot pass in the result to the `f`

function in `FlatMap`

.

We can resolve this issue by requiring `G`

to be a Monad, and use `flatMap`

to bind the value inside of `G`

to `f`

:

```
import cats.{Monad}
def runProgram[F[_], A, G[_]](program: Free[F, A], executor: Executor[F, G])(implicit M: Monad[G]): G[A] =
program match {
case Pure(a) => M.pure(a)
case FlatMap(fa: F[A], f: (A => Free[F, A])) =>
val res = executor.execute(fa)
M.flatMap(res)(a => runProgram(f(a), executor))
}
```

## Conclusion

In this article, we learn how to generalize our application even further by generalizing our “Free” wrapper to use it in various applications.

First, we generalize the `lift`

functions and introduce a “smart-constructor” to construct our program. Then, we generalized our `runProgram`

, the interpreter that runs the program, by submitting an `Executor`

trait. Lastly, we generalized our `Executor`

trait further by introducing natural-transformation on our `Executor`

trait.

The Free structure exists in the `Cats`

library with different names. Hopefully, you can understand the concept of Free and how Free works. There are also Free Applicative, and the difference is in the `runProgram`

and its “Free” algebra, where instead of being a Monad, it is an Applicative functionality.

All source code on this article can be viewed here.

Source and Reference: Free Monads Explained (pt 1). Building composable DSLs | by Oleksii Avramenko | Medium Cats: FreeMonads