Stackless Scala with Free Monads 

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]

Free monads 

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.

Trampoline 

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.

List using Free 

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.