Combining scala items

Question

I am trying to port the following Java snippet to Scala. It takes a list of MyColor objects and combines all those that are inside each other's delta. This seems like a problem that can be solved gracefully using some of the Scala 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

Here's another recursive solution that has the advantage that it is tail recursive (so there is no way), but on the other hand, does a lot of list manipulation, so it can be wasteful. The callback at the end is to return the output colors in input order, but not required if you don't care about the order.

 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 2

I assume that you somehow arrange your colors in the list, so that the colors "close" in the color space (i.e. with a low diff value) are adjacent in the list. Then I use the 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 am assuming that the merge modified to return a new color that was the two previous ones merged (so your colors are unchanged); otherwise you would oldc.merge(c) ; list oldc.merge(c) ; list in the first case.

See what happens here.

Start with an empty list for new colors. Then, for each color in an unrelated list, we have two cases:

• The combined list has a head, and the color of the head is within the delta of the color we are testing. In this case, combine the head and the new color and navigate through the saved list with the new head.
• Otherwise, add a new color to the top of the growing list and pass it on.

Finally, since we use them as stack operations, we complete the list change.

Answer 3

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

• should the decision be invariant in the initial order of your list
• if the distinction is to be made against merged or unrelated values ​​as you move

But here is something fun that uses recursion (although it is not tail recursive, it can of course be done like this), for example:

 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 this:

• Take your head
• Get all the tail elements that can be combined with the head, and then combine them (you can use the fold) in a new head
• passes a new head onto the tail, which is formed by accepting everything that cannot be combined in step No. 2, and then reconnected to it in step No. 1 (with the mandatory terminal sentence when the tail is empty)

It works better like Stream , I think. Please note that I assume that the list was originally ordered by diff, because I use span . This would be superfluous if it were replaced by partition .

Answer 4

I would 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, a little 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 is also another cool trick using Scala's ListBuffer to avoid the opposite 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