0

我尝试使用中的连续传递样式实现尾调用优化以遍历树线结构。不幸的是，我以前使用的经验并没有多大帮助。我有没有尾优化的递归调用：

def traverseTree(tree: Tree)(action: Int => Unit): Unit = {
  def traverseTreeRec(tree: Tree, continuation: () => Unit, action: Int => Unit): Unit = tree match {
    case Leaf(n) => {
      action(n)
      continuation()
    }
    case Node(n1, n2) => {
      traverseTreeRec(n1, () => traverseTreeRec(n2, continuation, action), action)
    }
  }
  traverseTreeRec(tree, () => (), action)
}

之后我尝试使用@annotation.tailrecand重写TailCalls，但仍然不确定如何装饰延续

def traverseTree(tree: Tree)(action: Int => Unit): Unit = {
  @annotation.tailrec
  def traverseTreeRec(tree: Tree, continuation: () => TailRec[Unit], action: Int => Unit): TailRec[Unit] = tree match {
    case Leaf(n) => {
      action(n)
      continuation()
    }
    case Node(n1, n2) =>
      // how to properly implement tail call here?
      // ERROR: it contains a recursive call not in tail position
      traverseTreeRec(n1, () => tailcall(traverseTreeRec(n2, continuation, action)), action)
  }
  traverseTreeRec(tree, () => done(), action)
}

提前致谢

ps：关于要点的完整示例

4

2 回答 2

1

最后，我有一个来自 Coursera 论坛的答案：

def traverseTree(tree: Tree)(action: Int => Unit): Unit = {
  def traverseTreeRec(tree: Tree, continuation: () => TailRec[Unit]): TailRec[Unit] = tree match {
    case Leaf(n) => {
      action(n)
      continuation()
    }
    case Node(n1, n2) =>
      tailcall(traverseTreeRec(n1,
        () => traverseTreeRec(n2,
          () => tailcall(continuation()))))
  }
  traverseTreeRec(tree, () => done(())).result
}

ps：@rob-napier 建议的问题包含一些详细信息，为什么应该以这种方式应用它

于 2013-11-24T07:33:13.413 回答
0

我对 Scala 知之甚少，但在您的代码中，我猜您可以这样做：

tailcall(traverseTreeRec(n1, () => tailcall(traverseTreeRec(n2, continuation, action)), action))

由于tailcall实际上存在于另一个匿名函数中，因此它会在碰到叶子时调用。也许您在所有尾部位置都需要它：

def traverseTree(tree: Tree)(action: Int => Unit): Unit = {
  @annotation.tailrec
  def traverseTreeRec(tree: Tree, continuation: () => TailRec[Unit], action: Int => Unit): TailRec[Unit] = tree match {
    case Leaf(n) => {
      action(n)
      tailcall(continuation())
    }
    case Node(n1, n2) =>
      tailcall(traverseTreeRec(n1, () => tailcall(traverseTreeRec(n2, continuation, action)), action))
  }
  tailcall(traverseTreeRec(tree, () => done(), action))
}

在Scheme中，让第一个分支的递归不是尾调用而第二个是尾调用会更快，但我想你不能在Scala中混合，因为它需要蹦床来做TCO。

于 2013-11-24T00:32:40.250 回答