Scalaのバイナリツリーのテールの再帰的な折り返し

Question

私はバイナリツリーの末尾の再帰的な折畳み関数を見つけようとしています。以下の定義を考える：

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を使用することができるように末尾再帰倍機能を見つけるのに苦労しています：

// 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] 

非末尾再帰関数の実装は非常に簡単です。

私の研究の中で、ツリー上のテールの再帰的な機能が次のようないくつかの例を見出しました。基本的にList[Tree[Int]]である独自のスタックを使用して、すべてのリーフの合計を計算します。しかし、このケースでは、オペレータの左手側と右手側のどちらを最初に評価するかは重要ではないので、追加する場合にのみ機能します。しかし一般化された倍の場合、それはかなり関連性があります。ここに私の意思を表示するには、いくつかの例の木は、以下のとおりです。

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

そして平等の条件その証拠：私のような特定のフォールド方法でディープコピーを作成したいものを木に基づいて

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 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 

} 

アイデアはアキュムレータの最後の2つの要素を使用して、red機能を使用して、左から右に値を蓄積するスタブノードの導入によって親子関係を追跡し、その結果を低減することであるときはいつでも、スタブノード探査の中で見つけられる。

このソリューションは最適化できますが、すでにテール再帰関数の実装です。

EDIT：

それはわずかにスタックとして見リストにアキュムレータ・データ構造を変更することによって簡略化することができる。

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 

}