Stackless Scala With Free Monads, complete example

Question

The following code is adapted from a paper (R. O. Bjarnason, Stackless Scala With Free Monads).

The title of the paper points to the purpose of the proposed data structures in general - that is to afford recursive processing in constant stack space, and to let the user express recursion in a clear way.

Specificly, my goal is to have a monadic structure that affords structural rewriting of an immutable Tree of Pairs (binary tree) or of Lists (n-ary-tree) based on simple pattern matching in constant stack space when ascending.

sealed trait Free[S[+_], +A]{
  private case class FlatMap[S[+_], A, +B](
    a: Free[S, A],
    f: A => Free[S, B]
  ) extends Free[S, B]

  def map[B](f: A => B): Free[S, B] = this.flatMap((a:A) => Done[S, B](f(a))) 

  def flatMap[B](f: A => Free[S, B]): Free[S, B] = this match { 
    case FlatMap(a, g) => FlatMap(a, (x: Any) => g(x).flatMap(f))
    case x => FlatMap(x, f)
  } 

  @tailrec
  final def resume(implicit S: Functor[S]): Either[S[Free[S, A]], A] = {
    this match {
      case Done(a) => Right(a)
      case More(k) => Left(k)
      case FlatMap(a, f) => a match {
        case Done(a) => f(a).resume
        case More(k) => Left(S.map(k)((x)=>x.flatMap(f)))
        case FlatMap(b, g) => b.flatMap((x: Any) => g(x).flatMap(f)).resume
      }
    }
  }
}

case class Done[S[+_], +A](a: A) extends Free[S, A]

case class More[S[+_], +A](k: S[Free[S, A]]) extends Free[S,A]

trait Functor[F[+_]] {
  def map[A, B](m: F[A])(f: A => B): F[B]
}

type RoseTree[+A] = Free[List, A] 

implicit object listFunctor extends Functor[List] {
  def map[A, B](a: List[A])(f: A => B) = a.map(f)
}
var tree :  Free[List, Int]=  More(List(More(List(More(List(Done(1), Done(2))), More(List(Done(3), Done(4))))), More(List(More(List(Done(5), Done(6))), More(List(Done(7), Done(8)))))))

How is the rewriting achieved using Free?

Where is a hook for the pattern matcher? - The pattern matcher has to be exposed to each entire subtree when ascending!

Can this be done within a for block?

[The question was edited.]

Answer 1

Update: the answer below addresses an earlier version of the question, but is mostly still relevant.

---

First of all, your code isn't going to work as it is. You can either make everything invariant, or go with the variance annotations in the original paper. For the sake of simplicity I'll take the invariant route (see here for a complete example), but I've also just confirmed that the version in the paper will work on 2.10.2.

To answer your first question first: your binary tree type is isomorphic to BinTree[Int]. Before we can show this, though, we need a functor for our pair type:

implicit object pairFunctor extends Functor[Pair] {
  def map[A, B](a: Pair[A])(f: A => B) = (f(a._1), f(a._2))
}

Now we can use resume, which we'll need for the conversion from BinTree back to T:

def from(tree: T): BinTree[Int] = tree match {
  case L(i) => Done(i)
  case F((l, r)) => More[Pair, Int]((from(l), from(r)))
}

def to(tree: BinTree[Int]): T = tree.resume match {
  case Left((l, r)) => F((to(l), to(r)))
  case Right(i) => L(i)
}

Now we can define your example tree:

var z = 0
def f(i: Int): T = if (i > 0) F((f(i - 1), f(i - 1))) else { z = z + 1; L(z) }
val tree = f(3)

Let's demonstrate our isomorphism and the monad for BinTree by replacing every leaf value with the tree containing its predecessor and successor:

val newTree = to(
  from(tree).flatMap(i => More[Pair, Int]((Done(i - 1), Done(i + 1))))
)

After some reformatting, the result will look like this:

F((
  F((
    F((
      F((L(0), L(2))),
      F((L(1), L(3)))
    )),
    F((
      F((L(2), L(4))),
      F((L(3), L(5)))
    )),
    ...

And so on, as expected.

For your second question: if you want to do the same kind of thing for a rose tree, you'd just replace the pair with a list (or a stream). You'll need to provide a functor instance for lists, as we did above for pairs, and then you've got a tree with Done(x) representing leaves and More(xs) for branches.

---

Your type needs map for the for-comprehension syntax to work. Fortunately you can write map in terms of flatMap and Done—just add the following to the definition of Free:

def map[B](f: A => B): Free[S, B] = this.flatMap(f andThen Done.apply)

Now the following is exactly the same as the newTree above:

val newTree = to(
  for {
    i <- from(tree)
    m <- More[Pair, Int]((Done(i - 1), Done(i + 1)))
  } yield m
)

The same thing will work with the Free[List, _] rose tree.