scala - 迭代更新 scalaz 树

Question

我有一个路径列表：

val paths = List(List("foo"), List("bar", "a"), List("bar", "b"))

我想在 scalaz 树中表示它：

def pathsToTree(root: String, paths: List[List[String]]): Tree[String] = ???

结果：

pathsToTree("paths", paths)

=> "paths".node("foo".leaf, "bar".node("a".leaf, "b".leaf))

我TreeLoc从http://eed3si9n.com/learning-scalaz/Tree.html读到了一些内容，但使用左/右或子索引似乎很乏味。我想像做这样的事情：

paths.foldLeft(root.node()) { case (acc: Tree[String], path: List[String]) =>
  acc // how to add all the items from `path` to the tree?
}

看起来我可以使用findand setTreeormodifyTree但这似乎效率很低。

Answer 1

这是一般的建设者：

  def pathTree[E](root: E, paths: Seq[Seq[E]]): Tree[E] =
    root.node(paths groupBy (_.head) map {
      case (parent, subpaths) => pathTree(parent, subpaths collect {
        case parent +: rest if rest.nonEmpty => rest
      })
    } toSeq: _*)

对于在线修改，我们可以定义：

  def addPath[E](path: Seq[E], tree: Tree[E]): Tree[E] = if (path.isEmpty) tree
  else
    tree match {
      case Tree.Node(root, children) if children.exists(_.rootLabel == path.head) => root.node(
        children map (subtree => if (subtree.rootLabel == path.head) addPath(path.tail, subtree) else subtree): _*
      )
      case Tree.Node(root, children) => root.node(children :+ path.init.foldRight(path.last.leaf)((root, sub) => root.node(sub)): _*)
    }

所以

  val tree = pathTree("root", List(List("foo"), List("bar", "a"), List("bar", "b", "c")))
  println(tree.drawTree)

产量

"root"
|
+- "foo"
|
`- "bar"
   |
   +- "b"
   |  |
   |  `- "c"
   |
   `- "a"

并 println(addPath(Seq("foo","baz"), tree).drawTree)打印

"root"
|
+- "foo"
|  |
|  `- "baz"
|
`- "bar"
   |
   +- "b"
   |  |
   |  `- "c"
   |
   `- "a"