玫瑰树的延迟广度优先遍历？

Question

我正在尝试重构一个组件，它目前使用一种相当昂贵的递归算法生成Seq[X]，以便它可以生成一个Stream[X]，因此可以按需加载/计算X，而生产者不必预先猜测满足消费者需要进行多少挖掘。

根据我所读的内容，这是使用“展开”（unfold）的理想用例，因此这是我一直在尝试的路线。

这是我的unfold函数，从David Pollak的示例中派生出来的，并经过某位莫里斯先生的审查：

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

最后，这是我尝试使用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=())
*/

请问有人能给我一些提示，如何修复（或重写）我的遍历逻辑，以便返回所有节点？谢谢！

- Alex Cruise

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
}

- Moritz

Answer 2

这是Moritz的完整回答，其中包含已更正的部分函数（原问题中最后一个情况从未匹配任何内容）：

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("/a/1", Nil),
                          CNode("/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"))
}

- Mike Slinn

---

谢谢！这让我想起了往事... :) - Alex Cruise