- Stackless Scala with Free Monads

The notion of free monad goes beyond just the interpreter pattern. I think people are still discovering new ways of harnessing its power.

Rúnar (@runarorama) has been a proponent of using `Free`

in Scala.
His talk that we covered on day 6, Dead-Simple Dependency Injection, uses `Free`

to implement
a mini language to implement a key-value store.
The same year, Rúnar also gave a talk at Scala Days 2012 called
Stackless Scala With Free Monads.
I recommend watching the talk before reading the paper, but it’s easier to quote the paper version,
Stackless Scala With Free Monads.

Rúnar starts out with code that uses an implementation of the `State`

monad to zip a list with its indices.
It blows the stack when the list is larger than the stack limit.
Then he introduces trampoline, which is a single loop that drives the entire program.

```
sealed trait Trampoline [+ A] {
final def runT : A =
this match {
case More (k) => k().runT
case Done (v) => v
}
}
case class More[+A](k: () => Trampoline[A])
extends Trampoline[A]
case class Done [+A](result: A)
extends Trampoline [A]
```

In the above code, `Function0`

`k`

is used as a thunk for the next step.

To extend its usage for State monad, he then reifies `flatMap`

into a data structure called `FlatMap`

:

```
case class FlatMap [A,+B](
sub: Trampoline [A],
k: A => Trampoline[B]) extends Trampoline[B]
```

Next, it is revealed that `Trampoline`

is a free monad of `Function0`

. Here’s how it’s defined in Cats:

```
type Trampoline[A] = Free[Function0, A]
```

Using Trampoline any program can be transformed into a stackless one.
`Trampoline`

object defines a few useful functions for trampolining:

```
object Trampoline {
def done[A](a: A): Trampoline[A] =
Free.Pure[Function0,A](a)
def defer[A](a: => Trampoline[A]): Trampoline[A] =
Free.defer(a)
def delay[A](a: => A): Trampoline[A] =
suspend(done(a))
}
```

Let’s try implementing `even`

and `odd`

from the talk:

```
import cats._, cats.syntax.all._, cats.free.{ Free, Trampoline }
import Trampoline._
def even[A](ns: List[A]): Trampoline[Boolean] =
ns match {
case Nil => done(true)
case x :: xs => defer(odd(xs))
}
def odd[A](ns: List[A]): Trampoline[Boolean] =
ns match {
case Nil => done(false)
case x :: xs => defer(even(xs))
}
even(List(1, 2, 3)).run
// res0: Boolean = false
even((0 to 3000).toList).run
// res1: Boolean = false
```

While implementing the above I ran into SI-7139 again, so I had to tweak the Cats’ code. #322

In addition, Rúnar introduces several datatypes that can be derived using `Free`

:

```
type Pair[+A] = (A, A)
type BinTree[+A] = Free[Pair, A]
type Tree[+A] = Free[List, A]
type FreeMonoid[+A] = Free[({type λ[+α] = (A,α)})#λ, Unit]
type Trivial[+A] = Unit
type Option[+A] = Free[Trivial, A]
```

There’s also an iteratees implementation based on free monads. Finally, he summarizes free monads in nice bullet points:

- A model for any recursive data type with data at the leaves.
- A free monad is an expression tree with variables at the leaves and flatMap is variable substitution.

Let’s try defining “List” using `Free`

.

```
type FreeMonoid[A] = Free[(A, +*), Unit]
def cons[A](a: A): FreeMonoid[A] =
Free.liftF[(A, +*), Unit]((a, ()))
val x = cons(1)
// x: FreeMonoid[Int] = Suspend(a = (1, ()))
val xs = cons(1) flatMap { _ => cons(2) }
// xs: Free[(Int, β0), Unit] = FlatMapped(
// c = Suspend(a = (1, ())),
// f = <function1>
// )
```

As a way of interpreting the result, let’s try converting this to a standard `List`

:

```
implicit def tuple2Functor[A]: Functor[(A, *)] =
new Functor[(A, *)] {
def map[B, C](fa: (A, B))(f: B => C) =
(fa._1, f(fa._2))
}
def toList[A](list: FreeMonoid[A]): List[A] =
list.fold(
{ _ => Nil },
{ case (x: A @unchecked, xs: FreeMonoid[A]) => x :: toList(xs) })
toList(xs)
// res2: List[Int] = List(1, 2)
```

herding cats — Stackless Scala with Free Monads