I am playing around with Scala and I am starting from some simple examples such as implementing binary trees. Having prior knowledge of functional programming (OCaml, F#) I was trying to replicate the common approach of using continuations in order to make a binary tree traversal tail-recursive. I am reading as much as I can about Scala's Delimited Continuations, but I have not been able to make it work.
You can read an OCaml implementation of this behaviour from this StackOverflow question
I followed the examples in this Introduction to Programming with Shift and Reset, but I am always getting type errors and the modifications I made to try making it work, gave correct results, but without making the function tail recursive.
Here's my implementation
abstract class IntTree
case object EmptyTree extends IntTree
case class Node( value : Int, left : IntTree, right : IntTree) extends IntTree
abstract class Result
case object Done extends Result
case class Next( n:Int, f : ( Unit => Result ) ) extends Result
def Sum(tree: IntTree): Int = {
def walk( t : IntTree) : Unit = t match {
case EmptyTree => ()
case Node(v, left, right) => {
walk(left)
reset {
shift { k: (Unit => Result) => Next(v, k) }
walk(right)
}
}
}
def start( t : IntTree) = { walk(t); Done }
def sumResult( ls : Result, acc : Int) : Int = ls match {
case Done => acc
case Next(value, k) => {
sumResult(k(), acc + value)
}
}
sumResult( start(tree), 0 )
}
I am also wondering if Delimited Continuations are the right tool for this job. I know this problem can be solved efficiently passing an explicit stack, but I would like to understand how to use cps in Scala.
