2

我在玩 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。

4

0 回答 0