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) 

基于这些树我想创建一个深刻的副本，如给定的折叠方法：

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 

} 

的想法是使用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 

}