11

I have two lists in Scala, how to merge them such that the tuples are grouped together?

Is there an existing Scala list API which can do this or need I do it by myself?

Input:

 List((a,4), (b,1), (c,1), (d,1))
 List((a,1), (b,1), (c,1))

Expected output:

List((a,5),(b,2),(c,2),(d,1))
kiritsuku
  • 52,967
  • 18
  • 114
  • 136
Shakti
  • 2,013
  • 8
  • 27
  • 40

4 Answers4

21

You can try the following one-line:

scala> ( l1 ++ l2 ).groupBy( _._1 ).map( kv => (kv._1, kv._2.map( _._2).sum ) ).toList
res6: List[(Symbol, Int)] = List(('a,5), ('c,2), ('b,2), ('d,1))

Where l1 and l2 are the lists of tuples you want merge.

Now, the breakdown:

  • (l1 ++ l2) you just concatenate both lists
  • .groupBy( _._1) you group all tuples by their first element. You will receive a Map with the first element as key and lists of tuples starting with this element as values.
  • .map( kv => (kv._1, kv._2.map( _._2).sum ) ) you make a new map, with similar keys, but the values are the sum of all second elements.
  • .toList you convert the result back to a list.

Alternatively, you can use pattern matching to access the tuple elements.

( l1 ++ l2 ).groupBy( _._1 ).map{
  case (key,tuples) => (key, tuples.map( _._2).sum ) 
}.toList
paradigmatic
  • 40,153
  • 18
  • 88
  • 147
4

Alternatively you can also use mapValues to shorten the code.

mapValues, as you can probably guess, allows you to re-map just the value for each (key, value) pair in the Map created by groupBy.

In this case the function passed to mapValues reduces each (Char, Int) tuple to just the Int then sums the resulting List of Ints.

(l1 ::: l2).groupBy(_._1).mapValues(_.map(_._2).sum).toList

If the order of the output list needs to follow your example, just add sorted which relies on an Ordering[(Char, Int)] implicit instance.

(l1 ::: l2).groupBy(_._1).mapValues(_.map(_._2).sum).toList.sorted
Don Mackenzie
  • 7,953
  • 7
  • 31
  • 32
0

If you can assume that both List[(A,B)] are ordered according to Ordering[A], you could write something like:

def mergeLists[A,B](one:List[(A,B)], two:List[(A,B)])(op:(B,B)=>B)(implicit ord:Ordering[A]): List[(A,B)] = (one,two) match {
    case (xs, Nil) => xs
    case (Nil, ys) => ys
    case((a,b)::xs,(aa,bb)::ys) =>
      if (a == aa) (a, op(b,bb)) :: mergeLists(xs,ys)(op)(ord)
      else if (ord.lt(a,aa)) (a, b) :: mergeLists(xs, (aa,bb)::ys)(op)(ord)
      else (aa, bb) :: mergeLists((a,b) :: xs, ys)(op)(ord)
}

Unfortunately this isn't tail recursive.

Landei
  • 54,104
  • 13
  • 100
  • 195
0

Using foldLeft and toMap:

Get a map out of one list, and iterate through the second list. We upsert entries into the map.

l1.foldLeft(l2.toMap)((accumulator, tuple) =>
      accumulator + (tuple._1 -> (accumulator.getOrElse(tuple._1, 0) + tuple._2))
).toList

results into:

List((Symbol(a),5), (Symbol(b),2), (Symbol(c),2), (Symbol(d),1))

Explanation:

  • l2.toMap converts List((a,1), (b,1), (c,1)) into immutable.Map(a->1, b->1, c->1)
  • foldLeft iterates through each tuple of list#1 l1.
    • (a,4) of list1 is added to the generated map, resulting to immutable.Map(a->1+4, b->1, c->1)
    • (b,1) of list1 is added to the generated map, resulting to immutable.Map(a->5, b->2, c->1)
    • (c,1) of list1 is added to the generated map, resulting to immutable.Map(a->5, b->2, c->2)
    • (d,1) of list1 is added to the generated map, resulting to immutable.Map(a->5, b->2, c->2, d->1)
  • toList converts the map back to the original input form, i.e. List[(Symbol, Int)]
Saurav Sahu
  • 13,038
  • 6
  • 64
  • 79