Pli de queue récursif sur un arbre binaire dans Scala

Question

J'essaie de trouver une fonction de pli récursif de queue pour un arbre binaire. Étant donné les définitions suivantes:

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

mise en œuvre d'une fonction récursive non la queue est assez simple:

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

Mais maintenant, je me bats pour trouver une fonction de rabattement récursive de la queue de sorte que l'annotation @annotation.tailrec peut être utilisé.

Au cours de ma recherche, j'ai trouvé plusieurs exemples où les fonctions récursives de la queue sur un arbre peuvent, par exemple, calculer la somme de toutes les feuilles en utilisant une propre pile qui est alors fondamentalement un List[Tree[Int]]. Mais dans la mesure où je comprends dans ce cas, cela ne fonctionne que pour les ajouts car il n'est pas important que vous évaluiez d'abord le côté gauche ou le côté droit de l'opérateur. Mais pour un pli généralisé, c'est tout à fait pertinent. Pour montrer mon intension voici quelques exemples des arbres:

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) 

Sur la base de ces arbres, je veux créer une copie en profondeur avec la méthode de pliage donnée comme:

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

Et la preuve que la condition de l'égalité est valable pour toutes les copies créées:

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) 

Quelqu'un pourrait-il me donner des indications?

Vous pouvez trouver le code utilisé dans cette question à ScalaFiddle: https://scalafiddle.io/sf/eSKJyp2/15

Answer 1

Vous pouvez arriver à une solution récursive queue si vous arrêtez d'utiliser la pile d'appels de fonction et commencer à utiliser une pile gérée par votre code et un accumulateur:

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 

} 

l'idée est d'accumuler des valeurs de gauche à droite, garder la trace de la relation parentale par l'introduction d'un nœud de talon et de réduire le résultat en utilisant votre fonction red en utilisant les deux derniers éléments de l'accumulateur à chaque fois qu'un noeud de talon est trouvé dans l'exploration.

Cette solution pourrait être optimisée mais c'est déjà une implémentation de fonction récursive en queue.

EDIT:

Il peut être légèrement simplifiée en modifiant la structure de données de l'accumulateur à une liste considérée comme une pile:

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 

}