Making more "functional" code in Scala to use immutable collections

data-structures, functional-programming, scala

Solution

I wonder if you would get good performance by using the standard immutable `List`. All `search` does is to check one node at a time and append the current element if it meets some criteria, then do a double recursion. So you can use an immutable accumulator:

def search(node: VPNode[TPoint, TObject], query: TPoint, radius: Double,
    acc: List[TObject] = Nil): List[TObject] = {

  val dist = distance(query, node.point)
  val mid = if (dist < radius) node.obj :: acc else acc

  val midLeft =
    if (node.left != null && dist <= radius + node.radius)
      search(node.left, query, radius, mid)
    else mid

  if (node.right != null && dist >= radius + node.radius)
    search(node.right, query, radius, midLeft)
  else midLeft
}

As far as I can see this only prepends to the beginning of the accumulator and should be fast.

Note that I think it's fine to use a mutable collection internally and return an immutable one to the caller:

def search(node: VPNode[TPoint, TObject], query: TPoint, radius: Double): Vector[TObject] = {
  import collection.immutable.{VectorBuilder => Builder}
  def rec(n: VPNode[TPoint, TObject], acc: Builder[TObject]): Builder[TObject] = {
    val dist = distance(query, node.point)
    val mid = if (dist < radius) acc += node.obj
    if (node.left != null && dist <= radius + node.radius) rec(node.left, acc)
    if (node.right != null && dist >= radius + node.radius) rec(node.right, acc)
    acc
  }
  rec(node, new Builder()).result
}

Problem

I'm porting an algorithm from Java to Scala that does a range search on a VP Tree. Briefly, the nodes in the tree have coordinates in space and a radius: nodes within that radius can be found on the left subtree, whilst nodes outside that radius are found on the right subtree. A range search attempts to find all objects in the tree within a specified distance to a query object. In Java I passed the function an arraylist in which it accumulated results, possibly recursing down one of either or both subtrees. Here's a straight port into Scala: ``` def search(node: VPNode[TPoint, TObject], query: TPoint, radius: Double, results: collection.mutable.Set[TObject]) { var dist = distance(query, node.point) if (dist < radius) results += node.obj if (node.left != null && dist <= radius + node.radius) search(node.left, query, radius, results) if (node.right != null && dist >= radius + node.radius) search(node.right, query, radius, results) } ``` Scala's default collection types are immutable, and I was thinking it was a bit annoying having to type `collection.mutable.` all the time, so I started looking into it. It seems to be recommended that using the immutable collections are nearly always fine: I'm using this code to do millions of lookups though, and it seems to me that copying and concatenating the results array would slow it down. Answers like this for example suggest that the problem needs to be approached more 'functionally'. So, what should I do to solve this problem in a more Scala-esque fashion? Ideally I'd like it to be as fast as the Java version, but I'm interested in solutions regardless (and can always profile them to see if it makes much difference). Note, I only just started learning Scala (figured I may as well cut my teeth on something useful) but I'm not new to functional programming, having used Haskell before (although I don't think I'm that good at it!).

Original source

Related problems