6

Seq[X]現在、かなり高価な再帰アルゴリズムを使用して を生成するコンポーネントをリファクタリングしようとしています。Stream[X]代わりにを生成するためX、オンデマンドでロード/計算することができ、プロデューサーはどのように事前に推測する必要がありません。消費者を満足させるためには、多くの掘り下げが必要です。

私が読んだことから、これは「展開」の理想的な使用法であり、それが私が取ろうとしてきたルートです。

これは、特定のモリス氏によって精査されたDavid Pollak の exampleunfoldから派生した私の関数です。

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("/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)
    ))
  ))
))

最後に、展開を使用する幅優先トラバーサルで失敗した試みを次に示します。

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

すべてのノードが返されるように、トラバーサル ロジックを修正 (または書き換え) する方法について、誰かヒントを教えてもらえますか? ありがとう！

4

2 に答える 2

6

ツリーの走査中に内部ノードの子を含めるのを忘れただけです。

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
}
于 2011-04-30T00:14:03.117 に答える