1
\$\begingroup\$

I just built a function to merge a set of List[A]s into a single scalaz.Tree[A].

Specifically, if I have the following three List[Int]s as input:

  • List[Int](1,3,5,10,20)
  • List[Int](1,3,5,700,701)
  • List[Int](1,800)

My output should be:

1
|
+- 3
|  |
|  `- 5
|     |
|     +- 700
|     |  |
|     |  `- 701
|     |
|     `- 10
|        |
|        `- 20
|
`- 800

I got the code working exactly as expected, but I was wondering if there is a way to improve it. Specifically, I'd like to make it more:

  1. Functional (as a primary priority)
  2. Performant (as a secondary priority)

Most importantly, I don't like the long chain of if statements.

However, general feedback would also be very appreciated, as I'm still getting warmed up to Scala.

This is the code for the merge:

object TreeBuilder {
  private def mergeAtJunction[A](coreLoc: TreeLoc[A], currentLoc: TreeLoc[A])(currentLevel: Int, maxLevels: Int): TreeLoc[A] = {
    if (currentLevel > maxLevels) {
      if (currentLoc.hasChildren) {
        coreLoc.insertDownFirst(currentLoc.firstChild.get.tree)
      } else {
        coreLoc
      }
    } else if (coreLoc.getLabel == currentLoc.getLabel) {
      if (coreLoc.hasChildren && currentLoc.hasChildren) {
        mergeAtJunction(coreLoc.firstChild.get, currentLoc.firstChild.get)(currentLevel + 1, maxLevels)
      } else if (!coreLoc.hasChildren && currentLoc.hasChildren) {
        coreLoc.insertDownFirst(currentLoc.firstChild.get.tree)
      } else {
        coreLoc
      }
    } else {
      if (coreLoc.rights.nonEmpty) {
        mergeAtJunction(coreLoc.right.get, currentLoc)(currentLevel + 1, maxLevels)
      } else {
        coreLoc.insertRight(currentLoc.tree)
      }
    }
  }

  def buildTreeFromLists[A](lists: List[A]*) = {
    val treeLists =
      lists
        .par
        .map(list => list.reverse.tail.foldLeft(list.reverse.head.node())((acc, next) => next.node(acc)) -> list.length)
        .toList
        .sortBy(_._2)
        .reverse
        .map(_._1)

    treeLists.tail.foldLeft(treeLists.head.loc.root)((coreTreeLoc, currentTree) => {
      mergeAtJunction(coreTreeLoc, currentTree.loc.root)(1, (treeLists.head.levels.length :: currentTree.levels.length :: Nil) max).root
    })
  }
}

Usage:

scala> import scalaz._, Scalaz._
import scalaz._
import Scalaz._

scala> TreeBuilder.buildTreeFromLists(List(1,3,5,10,20), List(1,3,5,700,701), List(1,800)).toTree.drawTree
res0: String =
"1
|
+- 3
|  |
|  `- 5
|     |
|     +- 700
|     |  |
|     |  `- 701
|     |
|     `- 10
|        |
|        `- 20
|
`- 800
"
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.