¿Recorrido de ancho, ancho de un árbol de rosas?

Question

Estoy tratando de refactorizar un componente que actualmente produce un Seq[X] usando un algoritmo recursivo bastante caro para que produzca un Stream[X] en su lugar, así que X se puede cargar/calcular bajo demanda, y el productor no tiene que trate de adivinar de antemano cuánto excavación tendrá que hacer para satisfacer al consumidor.

Por lo que he leído, este es un uso ideal para un "despliegue", así que esa es la ruta que he estado tratando de tomar.

Aquí está mi función unfold, derivado de David Pollak's example, que ha sido examinada por un tal señor Morris:

def unfold[T,R](init: T)(f: T => Option[(R,T)]): Stream[R] = f(init) match { 
    case None => Stream[R]() 
    case Some((r,v)) => r #:: unfold(v)(f) 
} 

Y aquí hay un pequeño árbol para probar suerte con:

case class Node[A](data: A, children: List[Node[A]]) { 
    override def toString = "Node(" + data + ", children=(" + 
           children.map(_.data).mkString(",") + 
           "))" 
} 

val tree = Node("root", List(
    Node("/a", List(
    Node("https://stackoverflow.com/a/1", Nil), 
    Node("https://stackoverflow.com/a/2", Nil) 
)), 
    Node("/b", List(
    Node("/b/1", List(
     Node("/b/1/x", Nil), 
     Node("/b/1/y", Nil) 
    )), 
    Node("/b/2", List(
     Node("/b/2/x", Nil), 
     Node("/b/2/y", Nil), 
     Node("/b/2/z", Nil) 
    )) 
)) 
)) 

Y finalmente, aquí está mi intento fallido de un recorrido transversal de ancho que usa desplegar:

val initial = List(tree) 
    val traversed = ScalaUtils.unfold(initial) { 
    case node :: Nil => 
     Some((node, node.children)) 
    case node :: nodes => 
     Some((node, nodes)) 
    case x => 
     None 
    } 
    assertEquals(12, traversed.size) // Fails, 8 elements found 

/* 
traversed foreach println => 

Node(root, children=(/a,/b)) 
Node(/a, children=(/a/1,/a/2)) 
Node(/b, children=(/b/1,/b/2)) 
Node(/b/1, children=(/b/1/x,/b/1/y)) 
Node(/b/2, children=(/b/2/x,/b/2/y,/b/2/z)) 
Node(/b/2/x, children=()) 
Node(/b/2/y, children=()) 
Node(/b/2/z, children=()) 
*/ 

¿Alguien puede darme algunas pistas sobre cómo corregir (o reescribir) mi lógica transversal para que se devuelvan todos los nodos? ¡Gracias!

Answer 1

Sólo se olvidó de incluir niños durante el recorrido del árbol:

val traversed = unfold(initial) { 
    case node :: Nil => 
    Some((node, node.children)) 
    case node :: nodes => 
    // breadth-first 
    Some((node, nodes ::: node.children)) 
    // or depth-first: Some((node, node.children ::: nodes)) 
    case x => 
    None 
} 

Answer 2

Aquí es una versión completa de Moritz' los nodos internos respuesta, con una función parcial corregido (el último caso nunca emparejado nada en el problema original):

case class CNode[A](data: A, children: List[CNode[A]]=Nil) { 
    override def toString: String = if (children.isEmpty) s"node($data)" else 
    s"node($data, children=(${ children.map(_.data).mkString(",") }))" 
} 

object Main extends App { 
    def unfold[T, R](init: T)(f: T => Option[(R, T)]): Stream[R] = f(init) match { 
    case None => Stream[R]() 

    case Some((r, v)) => r #:: unfold(v)(f) 
    } 

    val tree = List(
       CNode("root", List(
         CNode("/a", List(
          CNode("https://stackoverflow.com/a/1", Nil), 
          CNode("https://stackoverflow.com/a/2", Nil) 
         )), 
         CNode("/b", List(
          CNode("/b/1", List(
          CNode("/b/1/x", Nil), 
          CNode("/b/1/y", Nil) 
         )), 
          CNode("/b/2", List(
          CNode("/b/2/x", Nil), 
          CNode("/b/2/y", Nil), 
          CNode("/b/2/z", Nil) 
         )) 
         )) 
      )) 
      ) 

    val traversed = unfold(tree) { 
    case node :: Nil => 
     Some((node, node.children)) 

    case node :: nodes => 
     // breadth-first 
     Some((node, nodes ::: node.children)) 
     // or depth-first: Some((node, node.children ::: nodes)) 

    case Nil => 
     None 
    } 

    println(traversed.force.mkString("\n")) 
}