Pliegue recursivo de cola en un árbol binario en Scala

tree binary-tree

Question

Estoy tratando de encontrar una función de plegado recursivo de cola para un árbol binario. Dadas las siguientes definiciones:

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

Implementar una función recursiva sin cola es bastante sencillo:

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

Pero ahora estoy luchando para encontrar una función de plegado recursivo de cola para que se pueda usar la anotación @annotation.tailrec .

Durante mi investigación, he encontrado varios ejemplos en los que las funciones recursivas de la cola en un árbol pueden, por ejemplo, calcular la suma de todas las hojas utilizando una pila propia, que básicamente es una List[Tree[Int]] . Pero por lo que entiendo en este caso, solo funciona para las adiciones porque no es importante si primero evalúa el lado izquierdo o derecho del operador. Pero para un pliegue generalizado es bastante relevante. Para mostrar mi intención aquí hay algunos árboles de ejemplo:

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)

Basado en esos árboles, quiero crear una copia profunda con el método de doblado dado, como:

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

Y luego prueba de que la condición de igualdad se cumple para todas las copias creadas:

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)

¿Podría alguien darme algunos consejos, por favor?

Puede encontrar el código utilizado en esta pregunta en ScalaFiddle: https://scalafiddle.io/sf/eSKJyp2/15

Answer 1

Podría llegar a una solución recursiva de cola si deja de usar la pila de llamadas de función y comienza a usar una pila administrada por su código y un acumulador:

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

}

La idea es acumular valores de izquierda a derecha, realizar un seguimiento de la relación de parentalidad mediante la introducción de un nodo y reducir el resultado utilizando la función red utilizando los dos últimos elementos del acumulador cada vez que se encuentre un nodo en la exploración.

Esta solución podría optimizarse pero ya es una implementación de función recursiva de cola.

EDITAR:

Se puede simplificar un poco cambiando la estructura de datos del acumulador a una lista vista como una pila:

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

}