懒惰，广度优先遍历玫瑰树？ [英] Lazy, breadth-first traversal of a Rose Tree?

问题描述

我正在尝试使用相当昂贵的递归算法来重构当前生成 Seq [X] 的组件，以使其生成 Stream [X] 代替，因此 X 可以按需加载/计算，并且制作人不必事先猜测要满足消费者需要多少挖掘工作。

I'm trying to refactor a component that currently produces a Seq[X] using a fairly expensive recursive algorithm so that it produces a Stream[X] instead, so X's can be loaded/calculated on-demand, and the producer doesn't have to try to guess beforehand how much digging it'll have to do to satisfy the consumer.

根据我的阅读，这是展开的理想用法，所以这就是我一直在尝试的方法。

From what I've read, this is an ideal use for an "unfold", so that's the route I've been trying to take.

这是我的展开函数，该函数源自大卫·波拉克（David Pollak）的例子，已由莫里斯先生进行了审查：

Here's my unfold function, derived from David Pollak's example, which has been vetted by a certain 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 a little tree to 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 my failed attempt at a breadth-first traversal that 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 anyone give me some hints as to how to fix (or rewrite) my traversal logic so that all the nodes are returned? Thanks!

推荐答案

您只是忘了在遍历树时包括内部节点的子级：

You just forgot to include the inner nodes' children during the traversal of the 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
}

这篇关于懒惰，广度优先遍历玫瑰树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！