玫瑰樹的懶惰，廣度優先遍歷？

Question

我試圖重構一個當前使用相當昂貴的遞歸算法生成Seq[X]的組件，以便生成Stream[X]，因此可以按需加載/計算X，並且生產者不必嘗試事先猜測爲了滿足消費者需要做多少挖掘。

從我讀過的內容來看，這是「展開」的理想用途，所以這就是我一直試圖採用的路線。

這是我的unfold功能，從David Pollak's example衍生，已審覈通過一定的莫里斯先生：

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

而且這裏有一個小的樹試試我們的運氣：

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

而且最後，這是我在廣度優先的遍歷中使用展開的失敗嘗試：

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

任何人都可以給我一些關於如何修復（或重寫）我的遍歷邏輯的提示，以便返回所有節點？謝謝！

Answer 1

你忘記了樹的遍歷期間孩子：

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

這裏是聖莫里茨的完整版本」，包括內部節點的答案，與修正部分功能（最後一種情況下從來沒有匹配任何東西在原始問題中）：

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