CODEWITHSUNDEEP
scalascalazzipper
devth
devth

Reputation: 2750

Iteratively update a scalaz Tree

I have a list of paths:

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

I want to represent that in a scalaz Tree:

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

Result:

pathsToTree("paths", paths)

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

I've read some about TreeLoc from http://eed3si9n.com/learning-scalaz/Tree.html but it seems pretty tedious using left/right or child indices. I imagine doing something like:

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

It looks like I could use find and setTree or modifyTree but that seems quite inefficient.

Upvotes: 1

Views: 357

Answers (1)

Odomontois
Odomontois

Reputation: 16308

This is general builder: 

  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: _*)

for online modifing we can define:

  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)): _*)
    }

so 

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

yields

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

and println(addPath(Seq("foo","baz"), tree).drawTree) prints

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

Upvotes: 3

Related Questions