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 

}