Stackless Scala With Free Monads, a complete example

Question

The following code is adapted from an article (RO Bjarnason, Stackless Scala with free monads).

The name of the document indicates the purpose of the proposed data structures as a whole - that is, to provide recursive processing in a constant stack space and allow the user to express recursion in a clear way.

Specifically, my goal is to have a monadic structure that provides structural rewriting of an immutable pair tree (binary tree) or lists (n-ary-tree) based on simple pattern matching in a constant stack space on an upstream one.

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 rewriting done with Free?

Where is the hook for the template? - The template connector must be open for every integer subtree when upstream!

Can this be done inside the block?

[The question has been edited.]

Answer 1

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

---

First of all, your code will not work as it is. You can either make everything unchanged, or go with dispersion annotations in the original article. For simplicity, I will take an invariant route (see here for a full example), but I also just confirmed that the version in the document will work on 2.10.2.

First answer your first question: your binary tree type is isomorphic to BinTree[Int] . Before we can show this, 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 the resume , which we will need to convert 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) 

We demonstrate our isomorphism and monad for BinTree , replacing each leaf value with a 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 for rosewood, you just replace the pair with a list (or stream). You will need to provide a functor instance for lists, as it was above for pairs, and then you have a tree with Done(x) representing the leaves and More(xs) for the branches.

---

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

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

Now the following is the same as newTree above:

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

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