Merging elements in a scala list

Question

I'm trying to port the following Java snippet to Scala. It takes a list of MyColor objects and merges all of the ones that are within a delta of each other. It seems like a problem that could be solved elegantly using some of Scala's functional bits. Any tips?

List<MyColor> mergedColors = ...;
MyColor lastColor = null;
for(Color aColor : lotsOfColors) {
  if(lastColor != null) {
    if(lastColor.diff(aColor) < delta) {
      lastColor.merge(aColor);
      continue;
    }
  }
  lastColor = aColor;
  mergedColors.add(aColor);
}

Answer 1

I'm assuming that you somehow have your colors arranged in the list such that colors "close" in color space (i.e. with a low diff value) are adjacent in the list. Then I'd use a fold:

val unmergedColors: List[MyColor] = ...
val mergedColors = (Nil:List[MyColor] /: unmergedColors)( (list,c) => {
  list match {
    case oldc :: rest if (oldc.diff(c) < delta) => oldc.merge(c) :: rest
    case _ => c :: list
  }
}).reverse

Here, I'm assuming that merge is altered to take return a new color that is the previous two merged (so that your colors are immutable); otherwise, you'd oldc.merge(c) ; list in the first case.

Let's see what's going on here.

We start with an empty list for the new colors. Then, for each color in the unmerged list, we have two cases:

• The merged list has a head, and the color of the head is within delta of the color we're testing. In that case, merge the head and the new color, and pass along the saved list with the new head.
• Otherwise, add the new color to the front of the growing list and pass it along.

Finally, since we're using these as stack operations, we finish off by reversing the list.

Answer 2

It seems to me that this problem can lead to various questions around exactly what the problem is. For example:

• should the solution be invariant in the initial ordering of your list
• should the diff be done against the merged or unmerged values as you go along

But here is something fun which uses recursion (although it is not tail-recursive it could of course be made so), like:

type C = MyColor
type Cs = list[C]

def merge(val delta: Double, diff: (C, C) => Double, colors: Cs) : Cs = {

   def _mergeHeadAndGTDiff(head: C, tail: Cs) : Cs = { 
      val (toMerge, rest) = tail.span(diff(head, _) < delta) 
      val newHead = (head :: toMerge).reduceLeft(_ merge _)
      newHead :: (rest match {
           case Nil     => Nil
           case x :: xs => _mergeHeadAndGTDiff(newHead, xs) 
        })          
   }

   colors match {
      case Nil     => Nil
      case x :: xs => _mergeHeadAndGTDiff(x, xs)
   }
}

The solution looks like:

1. Grab the head
2. Get all elements of the tail which can be merged with the head and then merge them (could use fold) into a new head
3. cons the new head onto a tail which is formed by taking everything which could not be merged at step #2 and then plugging them back in at step #1 (with the obligatory terminal clause in the case that the tail is empty)

This works better as a Stream, I think. Note that I am assuming that the list was originally ordered by diff because I am using span. This would be unnecessary if this were replaced by partition.

Answer 3

Here's another recursive solution, which has the advantage of being tail recursive (so no chance of stack overflow) but on the downside does a lot of list manipulation, so may be wasteful. The call to reverse at the end is to put the output colors back in the input order, but isn't needed if you don't care about the ordering.

def processColors(colors: List[Color], delta: Double): List[Color] = {
  def process(in: List[Color], accum: List[Color]): List[Color] = in match {
      case x :: y :: ys if x.diff(y) < delta => process( x.merge(y) :: ys, accum )
      case x :: xs                           => process( xs, x :: accum )
      case Nil                               => accum
    }

  process(colors, Nil).reverse
}

Answer 4

I'd try folding:

def merge(lotsOfColor: List[MyColor], delta: Double): List[MyColor] =
  lotsOfColor.tail.foldLeft((List(lotsOfColor.head), lotsOfColor.head)) {
    case ((mergedColors, lastColor), aColor) if (lastColor diff aColor) < delta =>
      (mergedColors, lastColor merge aColor)
    case ((mergedColors, _), aColor) => (aColor :: mergedColors, aColor)
  }._1.reverse

Or, slightly different,

def merge(lotsOfColor: List[MyColor], delta: Double): List[MyColor] =
  lotsOfColor.tail.foldLeft((List(lotsOfColor.head), lotsOfColor.head)) {
    case ((mergedColors, lastColor), aColor) =>
      if ((lastColor diff aColor) < delta)
        (mergedColors, lastColor merge aColor)
      else
        (aColor :: mergedColors, aColor)
  }._1.reverse

There's also another cool trick using ListBuffer in Scala, to avoid the reverse at the end:

import scala.collection.mutable.ListBuffer
def merge(lotsOfColor: List[MyColor], delta: Double): List[MyColor] =
  lotsOfColor.tail.foldLeft((ListBuffer(lotsOfColor.head), lotsOfColor.head)) {
    case ((mergedColors, lastColor), aColor) if (lastColor diff aColor) < delta =>
      (mergedColors, lastColor merge aColor)
    case ((mergedColors, _), aColor) => 
      mergedColors += aColor
      (mergedColors, aColor)
  }._1.toList