Scala: Structural Recursion (01)

Structural Recursion: a first attempt

Having a Haskell backgound, I am curious to see how to implement structural recursion in Scala. So here is a very first attempt to do implement structural recursion in Scala. I am probably not implementing everything in the most elegant way, so all comments are welcome. I would like to go as far as implementing Conor Mc Bride's ideas about transforming structural recursion to tail recursion (as described in his paper clowns to the left of me, jokers to the right).

Structural recursion is based upon the idea of recursive structures.
Structures are functors, and structural recursion is defined by folding a recursive structure into a value.

trait Structures {
 type Struct[+A] <: Structure[A]
 
 trait Structure[+A] { self: Struct[A] =>
  def struct[B](a2b: A => B): Struct[B]
 }
 
 trait Rec {
  def open: Struct[Rec]
  def fold[A](algebra: Struct[A] => A): A = algebra(open struct (_.fold(algebra)))
 }
 
}

One of the simplest recursive structures are trees. We define the size of a tree using structural recursion.

class Trees extends Structures {
 type Struct[+A] = Tree[A]
 
 sealed class Tree[+A] extends Structure[A] { self: Struct[A] => 
  override def struct[B](a2b: A => B): Struct[B] = this match {
   case Leaf() => Leaf[B]
   case Node(la, ra) => Node[B](a2b(la), a2b(ra))
  }
 }
 case class Leaf[A]() extends Tree[A]
 case class Node[A](la: A, ra: A) extends Tree[A]
     
 class RecTree(val treeRecTree: Tree[RecTree]) extends Rec {
  override def open: Tree[RecTree] = treeRecTree
 }
 
 def leaf: RecTree = new RecTree(Leaf())
 def node(l: RecTree, r: RecTree): RecTree = new RecTree(Node[RecTree](l, r))
 
 val sizeTreeAlgebra: Tree[Int] => Int = (tree: Tree[Int]) => tree match {
  case Leaf() => 1
  case Node(li, ri) => li + ri      
 }
 
 def sizeTree(recTree: RecTree): Int = recTree.fold(sizeTreeAlgebra)

}

Here is a little test program:

object StructuralRecursion01 {
  def main(args: Array[String]) {
   val trees: Trees = new Trees
   val sizeOneTree: trees.RecTree = trees.leaf
   val sizeTwoTree = trees.node(sizeOneTree, sizeOneTree)
   val sizeThreeTree = trees.node(sizeOneTree, sizeTwoTree)
   println(trees.sizeTree(sizeThreeTree))
  }
}