scala - 在Scala中二叉树上的尾递归折叠

Question

我正在尝试为二叉树找到尾部递归折叠函数。给出以下定义:

// From the book "Functional Programming in Scala", page 45
sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

实现非尾递归函数非常简单:

def fold[A, B](t: Tree[A])(map: A => B)(red: (B, B) => B): B =
  t match {
    case Leaf(v)      => map(v)
    case Branch(l, r) => 
      red(fold(l)(map)(red), fold(r)(map)(red))
  }

但是现在我在努力寻找尾部递归折叠函数，以便可以使用批注 @annotation.tailrec。

在研究过程中，我发现了几个例子，其中树上的尾递归函数可以例如使用自己的堆栈计算所有叶子的总和，然后基本上是 List[Tree[Int]]。但是据我了解，在这种情况下，它仅适用于加法运算，因为先评估运算符的左侧还是右侧并不重要。但是对于一般的弃牌，这是非常相关的。为了显示我的意图，这里有一些示例树:

val leafs = Branch(Leaf(1), Leaf(2))
val left = Branch(Branch(Leaf(1), Leaf(2)), Leaf(3))
val right = Branch(Leaf(1), Branch(Leaf(2), Leaf(3)))
val bal = Branch(Branch(Leaf(1), Leaf(2)), Branch(Leaf(3), Leaf(4)))
val cmb = Branch(right, Branch(bal, Branch(leafs, left)))
val trees = List(leafs, left, right, bal, cmb)

基于这些树，我想使用给定的fold方法创建一个深拷贝，例如:

val oldNewPairs = 
  trees.map(t => (t, fold(t)(Leaf(_): Tree[Int])(Branch(_, _))))

然后证明相等条件适用于所有已创建的副本:

val conditionHolds = oldNewPairs.forall(p => {
  if (p._1 == p._2) true
  else {
    println(s"Original:\n${p._1}\nNew:\n${p._2}")
    false
  }
})
println("Condition holds: " + conditionHolds)

有人可以给我一些指示吗？

您可以在ScalaFiddle中找到此问题中使用的代码: https://scalafiddle.io/sf/eSKJyp2/15

Answer 1

如果停止使用函数调用堆栈，而开始使用由代码和累加器管理的堆栈，则可以找到尾部递归解决方案:

def fold[A, B](t: Tree[A])(map: A => B)(red: (B, B) => B): B = {

  case object BranchStub extends Tree[Nothing]

  @tailrec
  def foldImp(toVisit: List[Tree[A]], acc: Vector[B]): Vector[B] =
    if(toVisit.isEmpty) acc
    else {
      toVisit.head match {
        case Leaf(v) =>
          val leafRes = map(v)
          foldImp(
            toVisit.tail,
            acc :+ leafRes
          )
        case Branch(l, r) =>
          foldImp(l :: r :: BranchStub :: toVisit.tail, acc)
        case BranchStub =>
          foldImp(toVisit.tail, acc.dropRight(2) ++   Vector(acc.takeRight(2).reduce(red)))
      }
    }

  foldImp(t::Nil, Vector.empty).head

}

这个想法是从左到右累积值，通过引入 stub 节点来跟踪 parent 关系，并在探索中找到 stub 节点时，使用 red函数使用累加器的最后两个元素来减少结果。

可以优化此解决方案，但它已经是尾递归函数实现。

编辑:

通过将累加器数据结构更改为一个列表，可以将其稍微简化一下:

def fold[A, B](t: Tree[A])(map: A => B)(red: (B, B) => B): B = {

  case object BranchStub extends Tree[Nothing]

  @tailrec
  def foldImp(toVisit: List[Tree[A]], acc: List[B]): List[B] =
    if(toVisit.isEmpty) acc
    else {
      toVisit.head match {
        case Leaf(v) =>
          foldImp(
            toVisit.tail,
            map(v)::acc 
          )
        case Branch(l, r) =>
          foldImp(r :: l :: BranchStub :: toVisit.tail, acc)
        case BranchStub =>
          foldImp(toVisit.tail, acc.take(2).reduce(red) :: acc.drop(2))
      }
    }

  foldImp(t::Nil, Nil).head

}