我在玩 Scala,我从一些简单的例子开始,比如实现二叉树。具有函数式编程(OCaml,F#)的先验知识,我试图复制使用延续的常用方法,以使二叉树遍历尾递归。我正在尽可能多地阅读有关 Scala 的 Delimited Continuations 的内容,但我无法让它发挥作用。
您可以从此StackOverflow 问题中读取此行为的 OCaml 实现
我遵循了Shift 和 Reset 编程简介中的示例,但我总是遇到类型错误,并且我为尝试使其工作所做的修改得到了正确的结果,但没有使函数尾递归。
这是我的实现
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 )
}
我还想知道 Delimited Continuations 是否适合这项工作。我知道这个问题可以通过显式堆栈有效地解决,但我想了解如何在 Scala 中使用 cps。