scala 如何在遍历树形结构时实现尾部调用优化

bbuxkriu 于 2023-06-23 发布在 Scala

关注(0)|答案(2)|浏览(111)

我尝试在scala中实现尾部调用优化，以使用连续传递的方式遍历树形结构。不幸的是，我以前使用fsharp的经验并没有多大帮助。我有递归调用w/o尾部优化：

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.tailrec和TailCalls重写，但仍然不确定如何装饰continuation

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：full sample on gist

scala

来源：https://stackoverflow.com/questions/20164061/how-to-achieve-tail-call-optimization-while-traversing-tree-like-structure-using

2条答案

按热度按时间

pb3s4cty1#

最后，我从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：suggested question by @rob-napier包含了为什么应该以这种方式应用它的一些细节

赞(0）回复(0）举报 2023-06-23

whlutmcx2#

我对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。

赞(0）回复(0）举报 2023-06-23

我来回答

scala 如何在遍历树形结构时实现尾部调用优化

2条答案

相关问题

热门标签

最新问答