在 Scala 中以尾递归方式遍历树状对象

Question

我正在尝试创建一个函数，以尾递归方式遍历具有树状结构的对象，但到目前为止我无法编写执行此操作的代码。

我的树状对象是：

case class Node(lex: String,
                position: Int,
                posTag: String,
                var dependency: Int = -1,
                var left: Vector[Node],
                var right: Vector[Node])

版本 1，尾递归（不工作）

到目前为止，我已经尝试了最简单的形式：

def matchNodes(goldSentence: LabeledSentence): Int = {

  def condition(n: Node): Boolean = ???

  @tailrec
  def match0(acc: Int, n: Seq[Node]): Int =
    (n: @switch) match {
      case head :: tail => {
        if (condition(head)) {
          match0(acc + 1, tail)
        } else {
          acc
        }
      }
      case _ => acc
    }
  match0(0, left) + match0(0, right)
}

上面的代码是tailrec，但是并没有遍历整棵树，只遍历了第一层。

版本 2，尾递归（不工作）

其他方式是：

def matchNodes(goldSentence: LabeledSentence): Int = {
  @inline def condition(n: Node): Boolean = ???

  def sumAcc(nodes: Vector[Node]): Vector[Node] = nodes match {
    case head +: tail => sumAcc(head.left ++ head.right ++ tail)
    case _ => nodes
  }

  @tailrec
  def match0(acc: Int, n: Seq[Node]): Int =
    (n: @switch) match {
      case head :: tail => {
        if (condition(head)) {
          match0(acc + 1, tail)
        } else {
          acc
        }
      }
      case _ => acc
    }

  val flatTree  =  sumAcc(right ++ left)
  match0(0, flatTree)
}

在这里，我尝试将所有节点扁平化为一个 Vector[Node]，但由于某种原因，处理树后的预期结果不正确。

版本 3，无尾递归（有效）

我试过的最后一个代码不是尾递归的，但它是唯一计算出正确结果的代码：

def matchNodes(goldSentence: LabeledSentence): Int = {

  var correctRoots = 0
  val position:Int = this.position
  val dep:Int = dependency
  val tag = goldSentence.tags(position)
  if (goldSentence.dep(position) == dep || Constants.punctuationTags.contains(tag))
    correctRoots += 1

  if (right.nonEmpty)
    for (r <- right)
      correctRoots += r.matchNodes(goldSentence)
  if (left.nonEmpty)
    for (l <- left)
      correctRoots += l.matchNodes(goldSentence)

  correctRoots
}

有没有办法让这个函数尾递归？

Answer 1

没有自然的方法可以将其转换为使用尾递归（即您不会在 space 用法中获得渐近改进）。那就是您在此处使用的树遍历算法需要一个堆栈，无论是递归给出的调用堆栈还是您维护的显式堆栈。如果您不想破坏调用堆栈，则可以使用显式堆栈并进行迭代。如果你真的想坚持使用尾递归，你可以将堆栈作为额外的累加器参数传递。

// Simplified version of your Node; let's ignore the value for now
case class Node(value: Unit, children: List[Node])
var counter = 0
def traverseNodeAccum(node: Node)(acc: List[Node]): Unit = {
  counter += 1
  (node.children, acc) match {
    case (Nil, Nil) => 
      ()
    case (Nil, x :: rest) =>
      traverseNodeAccum(x)(rest)
    case (child :: otherChildren, xs) => 
      traverseNodeAccum(child)(otherChildren ++ xs)
  }
}

如果您想在完全不产生堆栈成本的情况下进行遍历，则必须具有树的可变表示（至少据我所知）。不幸的是，您的 case class 治疗无效。

Answer 2

我终于写了一个尾递归方法来遍历整棵树，这里是作为@badcook回答的替代：

def matchNodes(goldSentence: LabeledSentence): Int = {
  @inline def condition(n: Node): Boolean = ???

  @tailrec
  def match0(acc:Int, n: Node)(queue:Seq[Node]): Int = {
    val count = if (condition(n)) acc + 1 else acc

    (queue: @switch) match {
      case head +: tail =>
        match0(count, head)(head.left ++ head.right ++ tail)
      case Nil =>
        count
    }
  }

  match0(0, this)(left ++ right)
}

在 Scala 中以尾递归方式遍历树状对象

Transverse a tree like object in a Tail recursive way in scala

scala

recursion

traversal

tail-recursion

版本 1，尾递归（不工作）

版本 2，尾递归（不工作）

版本 3，无尾递归（有效）