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.