迭代更新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)) 

我已經從http://eed3si9n.com/learning-scalaz/Tree.html讀了一些關於TreeLoc的內容，但是使用左/右或子索引似乎很乏味。我想這樣做是這樣的：

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

它看起來像我可以用find和setTree或modifyTree但似乎非常低效的。

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"