Now that we have general understanding of Free monads, let’s watch Rúnar’s presentation from Scala Days 2012: 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 a code that uses State monad to zip a list with index. It blows the stack when the list is larger than the stack limit. Then he introduces tranpoline, 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 Scalaz 7:
type Trampoline[+A] = Free[Function0, A]
In addition, Rúnar introduces several data structures that can form useful free monad:
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 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.
Using Trampoline any program can be transformed into a stackless one. Let’s try implementing even and odd from the talk using Scalaz 7’s Trampoline. Free object extends FreeFunction which defines a few useful functions for tramplining:
trait FreeFunctions {
/** Collapse a trampoline to a single step. */
def reset[A](r: Trampoline[A]): Trampoline[A] = { val a = r.run; return_(a) }
/** Suspend the given computation in a single step. */
def return_[S[+_], A](value: => A)(implicit S: Pointed[S]): Free[S, A] =
Suspend[S, A](S.point(Return[S, A](value)))
def suspend[S[+_], A](value: => Free[S, A])(implicit S: Pointed[S]): Free[S, A] =
Suspend[S, A](S.point(value))
/** A trampoline step that doesn't do anything. */
def pause: Trampoline[Unit] =
return_(())
...
}
We can call import Free._ to use these.
scala> import Free._
import Free._
scala> :paste
// Entering paste mode (ctrl-D to finish)
def even[A](ns: List[A]): Trampoline[Boolean] =
ns match {
case Nil => return_(true)
case x :: xs => suspend(odd(xs))
}
def odd[A](ns: List[A]): Trampoline[Boolean] =
ns match {
case Nil => return_(false)
case x :: xs => suspend(even(xs))
}
// Exiting paste mode, now interpreting.
even: [A](ns: List[A])scalaz.Free.Trampoline[Boolean]
odd: [A](ns: List[A])scalaz.Free.Trampoline[Boolean]
scala> even(List(1, 2, 3)).run
res118: Boolean = false
scala> even(0 |-> 3000).run
res119: Boolean = false
This was surprisingly simple.
Let’s try defining “List” using Free.
scala> type FreeMonoid[A] = Free[({type λ[+α] = (A,α)})#λ, Unit]
defined type alias FreeMonoid
scala> def cons[A](a: A): FreeMonoid[A] = Free.Suspend[({type λ[+α] = (A,α)})#λ, Unit]((a, Free.Return[({type λ[+α] = (A,α)})#λ, Unit](())))
cons: [A](a: A)FreeMonoid[A]
scala> cons(1)
res0: FreeMonoid[Int] = Suspend((1,Return(())))
scala> cons(1) >>= {_ => cons(2)}
res1: scalaz.Free[[+α](Int, α),Unit] = Gosub(Suspend((1,Return(()))),<function1>)
As a way of interpretting the result, let’s try converting this to a standard List:
scala> def toList[A](list: FreeMonoid[A]): List[A] =
list.resume.fold(
{ case (x: A, xs: FreeMonoid[A]) => x :: toList(xs) },
{ _ => Nil })
scala> toList(res1)
res4: List[Int] = List(1, 2)
That’s it for today.