1

パスのリストがあります：

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

それを Scalaz Tree で表現したい:

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.htmlTreeLocからいくつか読んだことがありますが、左/右または子インデックスを使用するのはかなり面倒です。次のようなことを想像します：

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

findand setTreeorを使用できるように見えますmodifyTreeが、それは非常に非効率的です。

4

1 に答える 1

3

これは一般的なビルダーです:

  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"
于 2015-05-08T07:29:17.643 に答える