Conditionally merge items in a sequence

Question

I have a list of objects in a sequence val as = Seq[A]. A looks like this:

import java.time.Instant
case class A(t: String, start: Instant, end: Instant)

Now I want to merge the element in as conditionally: whenever two subsequent, i.e. directly adjacent, items a1 and a2 have the same value for t, they should be merged into one like this:

object A {
  def merge(a1: A, a2: A): A = {
    require(a1.t == a2.t)
    A(a1.t, a1.start, a2.end)
  }
}

Note that items that do not directly succeed on another should never be merged, e.g.:

Seq(A("a", ...), A("a", ...), A("b", ...), ...) // -> merge the first two elements

However:

Seq(A("a", ...), A("b", ...), A("a", ...), ...) // -> do not merge any elements

There is a similar question on SO, but it merges multiple lists, so it is not applicable to my case.

My first approach:

as.zip(as.tail)
  .map { 
    case (a1: A, a2: A) if (a1.t == a2.t) => merge(a1, a2)
    case (a1: A, a2: A) => ???
  }

There are multiple flaws though. Apart from that I am not sure what to do in the second case (i.e. keep both a1 and a2 as-is), this also does not work for more than one subsequent elements that should be merged.

My intuition leads me more towards foldLeft:

as.foldLeft(???)(A.merge)

This solves the issue with more than one subsequent elements that need to be merged. However, it will try to merge all the elements which is not possible with my merge implementation.

I could adapt merge(), but it remains unclear to me how: if a1.t == a2.t, the result type should be a new A, whereas otherwise it should 'return' a1 and a2 as they were.

My approach to the latter idea was to add these methods to the class A:

def merge(that: A): (A, Option[A]) =
  if (this.t == that.t)
    (A(t, this.start, that.end), None)
  else
    (this, Some(that))

But here, I cannot really use the output of merge() in a foldLeft() call on the sequence as.

The underlying problem is in either approach: how should I handle the fact that sometimes (when t matches), I want to add a single new A to the new sequence, whereas in the other cases, I need to add two elements.

I am a bit lost on how to tackle this in a functional programming way. I could of course iterate over the list of as, store the ones that should be merged in a new data structure, and generate that again. Is there a better way?

@sirius yes, only adjacent items. I've clarified this in the question now. — Carsten, Jun 27 '18 at 12:51
Use a fold and compare the current item to the last item of the accumulator. If they match, remove the last item from the accumulator, merge it with the current item and add it back to the accumulator. If they don't match, add the current item to the accumulator. — sirius, Jun 27 '18 at 13:21

score 3 · Accepted Answer · answered Jun 27 '18 at 13:40

Building on RoberMP's answer, if you use foldRight to construct a List you can use pattern matching with the cons operator which should be more efficient than tail operations:

def merge(sequence: Seq[A]) = {
  sequence.foldRight(List.empty[A]) {
    case (A(t1, x, _), A(t2, _, y) :: list) if t1 == t2 => A(t1, x, y) :: list
    case (other, list) => other :: list
  }
}

This works from right to left so that we can use :: in matching but should still have the intended output.

score 0 · Answer 2 · answered Jun 27 '18 at 13:35

I think that foldLeft is the proper approach, something like (untested):

as.foldLeft(Seq.empty[A])(merge)

def merge(acc: Seq[A], a: A): Seq[A] = {
  if(acc.isEmpty) Seq(a)
  else if(acc.last.t == a.t) acc.init :+ A(a.t, acc.last.start, a.end)
  else acc :+ a
}

Notice that there is a lot of tail operations here so don't know if Seq is the better kind of collection for this use case

Conditionally merge items in a sequence

2 Answers2