Creando árbol de suma de Scala árbol binario

Question

Para una tarea que escribió algo de código Scala en los que he las siguientes clases y objetos (utilizado para el modelado de un árbol binario):

object Tree { 
    def fold[B](t: Tree, e: B, n: (Int, B, B) => B): B = t match { 
    case Node(value, l, r) => n(value,fold(l,e,n),fold(r,e,n)) 
    case _ => e 
    } 
    def sumTree(t: Tree): Tree = 
    fold(t, Nil(), (a, b: Tree, c: Tree) => { 
     val left = b match { 
     case Node(value, _, _) => value 
     case _ => 0 
     } 
     val right = c match { 
     case Node(value, _, _) => value 
     case _ => 0 
     } 
     Node(a+left+right,b,c) 
    }) 
} 

abstract case class Tree 
case class Node(value: Int, left: Tree, right: Tree) extends Tree 
case class Nil extends Tree 

Mi pregunta es acerca de la sumTree función que crea un nuevo árbol donde los nodos tienen valores iguales a la suma de los valores de sus hijos más su propio valor.

Me parece bastante feo aspecto y me pregunto si hay una forma mejor de hacer esto. Si utilizo la recursividad que funciona de arriba hacia abajo, sería más fácil, pero no podría encontrar esa función.

tengo para implementar la función fold, con una firma como en el código, para calcular sumTree

me dio la sensación de que esto puede ser implementado de una manera mejor, tal vez usted tiene alguna sugerencia?

Answer 1

En primer lugar, creo y si se puede decir así, usted ha hecho un muy buen trabajo. Puedo sugerir un par de pequeños cambios a su código:

abstract class Tree 
case class Node(value: Int, left: Tree, right: Tree) extends Tree 
case object Nil extends Tree 

1. árbol no tiene que ser una clase caso, además de usar un caso de clase como nodo no hoja está en desuso debido a la posible errónea comportamiento de los métodos generados automáticamente
2. Nil es un singleton y se define mejor como un caso-objeto en lugar de caso-clase.

3. Además consideran que la calificación de superclase Tree con sealed. sealed le dice al compilador que la clase solo se puede heredar desde el mismo archivo fuente. Esto permite al compilador emitir advertencias siempre que la siguiente expresión de coincidencia no sea exhaustiva; en otras palabras, no incluye todos los casos posibles.

   clase abstracta sellado árbol

El siguiente par de mejora podría ser hecha al sumTree:

def sumTree(t: Tree) = { 
    // create a helper function to extract Tree value 
    val nodeValue: Tree=>Int = { 
    case Node(v,_,_) => v 
    case _ => 0 
    } 
    // parametrise fold with Tree to aid type inference further down the line 
    fold[Tree](t,Nil,(acc,l,r)=>Node(acc + nodeValue(l) + nodeValue(r) ,l,r)) 
} 

nodeValue función auxiliar también se puede definir como (la notación alternativa utilicé anterior es posible porque una secuencia de los casos entre llaves es tratado como una función literal):

def nodeValue (t:Tree) = t match { 
    case Node(v,_,_) => v 
    case _ => 0 
} 

pocas mejoras continuación se parametrizando fold método con Tree (fold[Tree]). Debido a que Scala tipo inferer funciona a través de la expresión secuencialmente de izquierda a derecha, diciéndole temprano que vamos a tratar con Tree's, omite información de tipo al definir el literal de la función que se pasa al fold más adelante.

Así que aquí es el código completo que incluye sugerencias:

sealed abstract class Tree 
case class Node(value: Int, left: Tree, right: Tree) extends Tree 
case object Nil extends Tree 

object Tree { 
    def fold[B](t: Tree, e: B, n: (Int, B, B) => B): B = t match { 
    case Node(value, l, r) => n(value,fold(l,e,n),fold(r,e,n)) 
    case _ => e 
    } 
    def sumTree(t: Tree) = { 
    val nodeValue: Tree=>Int = { 
     case Node(v,_,_) => v 
     case _ => 0 
    } 
    fold[Tree](t,Nil,(acc,l,r)=>Node(acc + nodeValue(l) + nodeValue(r) ,l,r)) 
    } 
} 

La recursividad se le ocurrió es la única dirección posible que le permite recorrer el árbol y producir una copia modificada de la estructura de datos inmutables. Todos los nodos de hoja deben crearse antes de agregarse a la raíz, porque los nodos individuales del árbol son inmutables y todos los objetos necesarios para construir un nodo deben conocerse antes de la construcción: los nodos de hoja deben crearse antes de poder crear una raíz nodo.

Answer 2

Su solución es probablemente más eficiente (sin duda utiliza menos de pila), pero aquí es una solución recursiva, fwiw

def sum(tree:Tree):Tree ={ 
    tree match{ 
    case Nil =>Nil 
    case Tree(a, b, c) =>val left = sum(b) 
         val right = sum(c) 
         Tree(a+total(left)+total(right), left, right) 
    } 
} 

def total(tree:Tree):Int = { 
    tree match{ 
    case Nil => 0 
    case Tree(a, _, _) =>a 
} 

Answer 3

Como escribe Vlad, su solución tiene la única forma general que puede tener con tal pliegue.

Todavía hay una manera de deshacerse de la coincidencia de valores de nodo, no solo de factorizarlo. Y personalmente lo preferiría de esa manera.

Usa coincide con porque no todos los resultados que obtienes de un pliegue recursivo llevan una suma. Sí, no todos los árboles pueden llevarlo, Nil no tiene lugar para un valor, pero su doblez no se limita a los árboles, ¿o sí?

Así que vamos a tener:

case class TreePlus[A](value: A, tree: Tree) 

Ahora podemos doblarla como esto:

def sumTree(t: Tree) = fold[TreePlus[Int]](t, TreePlus(0, Nil), (v, l, r) => { 
    val sum = v+l.value+r.value 
    TreePlus(sum, Node(sum, l.tree, r.tree)) 
}.tree 

Por supuesto, el TreePlus no es realmente necesario ya que tenemos el producto canónica Tuple2 en la biblioteca estándar.

Answer 4

Probablemente ya hayas entregado tu tarea, pero creo que todavía vale la pena señalar que la forma en que tu código (y el código en las respuestas de otras personas) parece es el resultado directo de cómo modelaste los árboles binarios. Si, en lugar de utilizar un tipo de datos algebraico (Tree, Node, Nil), hubiera utilizado una definición de tipo recursiva, no habría tenido que usar la coincidencia de patrones para descomponer sus árboles binarios. Aquí está mi definición de un árbol binario:

case class Tree[A](value: A, left: Option[Tree[A]], right: Option[Tree[A]]) 

Como se puede ver que no hay necesidad de Node o Nil aquí (este último es simplemente glorificado null de todos modos - que no quiere nada como esto en su código, ¿estás ?).

Con tal definición, fold es esencialmente una sola línea:

def fold[A,B](t: Tree[A], z: B)(op: (A, B, B) => B): B = 
    op(t.value, t.left map (fold(_, z)(op)) getOrElse z, t.right map (fold(_, z)(op)) getOrElse z) 

Y sumTree es también corto y dulce:

def sumTree(tree: Tree[Int]) = fold(tree, None: Option[Tree[Int]]) { (value, left, right) => 
    Some(Tree(value + valueOf(left, 0) + valueOf(right, 0), left , right)) 
}.get 

donde se define valueOf ayudante como:

def valueOf[A](ot: Option[Tree[A]], df: A): A = ot map (_.value) getOrElse df 

No se necesitan coincidencias de patrones anywher e - todo por una buena definición recursiva de árboles binarios.