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.]
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:Now we can use
resume
, which we'll need for the conversion fromBinTree
back toT
:Now we can define your example tree:
Let's demonstrate our isomorphism and the monad for
BinTree
by replacing every leaf value with the tree containing its predecessor and successor:After some reformatting, the result will look like this:
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 andMore(xs)
for branches.Your type needs
map
for thefor
-comprehension syntax to work. Fortunately you can writemap
in terms offlatMap
andDone
—just add the following to the definition ofFree
:Now the following is exactly the same as the
newTree
above:The same thing will work with the
Free[List, _]
rose tree.