scala - Lazy, breadth-first traversal of a Rose Tree? -

i'm trying refactor component produces seq[x] using expensive recursive algorithm produces stream[x] instead, x's can loaded/calculated on-demand, , producer doesn't have try guess beforehand how digging it'll have satisfy consumer.

from i've read, ideal use "unfold", that's route i've been trying take.

here's unfold function, derived david pollak's example, has been vetted mr. 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) } 

and here's little tree try our luck with:

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("/a/1", nil),     node("/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)     ))   )) )) 

and finally, here's failed attempt @ breadth-first traversal uses unfold:

  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=()) */ 

can give me hints how fix (or rewrite) traversal logic nodes returned? thanks!

you forgot include inner nodes' children during traversal of tree:

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 }