Scala: Merge map

How can I merge maps like below:

Map1 = Map(1 -> Class1(1), 2 -> Class1(2))
Map2 = Map(2 -> Class2(1), 3 -> Class2(2))

After merged.

Merged = Map( 1 -> List(Class1(1)), 2 -> List(Class1(2), Class2(1)), 3 -> Class2(2))

Can be List, Set or any other collection who has size attribute.

Using the standard lib, you can do it as follows:

// convert maps to seq, to keep duplicate keys and concat
val merged = Map(1 -> 2).toSeq ++ Map(1 -> 4).toSeq
// merged: Seq[(Int, Int)] = ArrayBuffer((1,2), (1,4))

// group by key
val grouped = merged.groupBy(_._1)
// grouped: scala.collection.immutable.Map[Int,Seq[(Int, Int)]] = Map(1 -> ArrayBuffer((1,2), (1,4)))


// remove key from value set and convert to list
val cleaned = grouped.mapValues(_.map(_._2).toList)
// cleaned: scala.collection.immutable.Map[Int,List[Int]] = Map(1 -> List(2, 4))

This is the simplest implementation i could come up with,

val m1 = Map(1 -> "1", 2 -> "2")
val m2 = Map(2 -> "21", 3 -> "3")

def merge[K, V](m1:Map[K, V], m2:Map[K, V]):Map[K, List[V]] = 
  (m1.keySet ++ m2.keySet) map { i => i -> (m1.get(i).toList ::: m2.get(i).toList) } toMap

merge(m1, m2) // Map(1 -> List(1), 2 -> List(2, 21), 3 -> List(3))

You could use scalaz:

import scalaz._, Scalaz._

val m1 = Map('a -> 1, 'b -> 2)
val m2 = Map('b -> 3, 'c -> 4)

m1.mapValues{List(_)} |+| m2.mapValues{List(_)}
// Map('b -> List(2, 3), 'c -> List(4), 'a -> List(1))

You could use Set(_) instead of List(_) to get Sets as values in Map.

See Semigroup in scalaz cheat sheet (or in learning scalaz) for details about |+| operator.

For Int |+| works as +, for List - as ++, for Map it applies |+| to values of same keys.

One clean way to do it, with cats:

import cats.implicits._

Map(1 -> "Hello").combine(Map(2 -> "Goodbye"))
//Map(2 -> Goodbye, 1 -> Hello)

It's important to note that both maps have to be of the same type (in this case, Map[Int, String]).

Long explanation:

combine isn't really a member of Map. By importing cats.implicits you're bringing into scope cats's Map built-in monoid instances, along with some implicit classes which enable the terse syntax.

The above is equivalent to this:

Monoid[Map[Int, String]].combine(Map(1 -> "Hello"), Map(2 -> "Goodbye"))

Where we're using the Monoid "summoner" function to get the Monoid[Map[Int, String]] instance in scope and using its combine function.

I wrote a blog post about this , check it out :

http://www.nimrodstech.com/scala-map-merge/

basically using scalaz semi group you can achieve this pretty easily

would look something like :

  import scalaz.Scalaz._
  Map1 |+| Map2

Starting Scala 2.13, another solution only based on the standard library consists in using groupMap which (as its name suggests) is an equivalent of a groupBy followed by mapValues:

// val m1 = Map(1 -> "a", 2 -> "b")
// val m2 = Map(2 -> "c", 3 -> "d")
(m1.toSeq ++ m2).groupMap(_._1)(_._2)
// Map[Int,Seq[String]] = Map(2 -> List("b", "c"), 1 -> List("a"), 3 -> List("d"))

This:

• Concatenates the two maps as a sequence of tuples (List((1,"a"), (2,"b"), (2,"c"), (3,"d"))). For conciseness, m2 is implicitly converted to Seq to adapt to the type of m1.toSeq - but you could choose to make it explicit by using m2.toSeq.

• groups elements based on their first tuple part (_._1) (group part of groupMap)

• maps grouped values to their second tuple part (_._2) (map part of groupMap)

You can use foldLeft to merge two Maps of the same type

def merge[A, B](a: Map[A, B], b: Map[A, B])(mergef: (B, Option[B]) => B): Map[A, B] = {
  val (big, small) = if (a.size > b.size) (a, b) else (b, a)
  small.foldLeft(big) { case (z, (k, v)) => z + (k -> mergef(v, z.get(k))) }
}

def mergeIntSum[A](a: Map[A, Int], b: Map[A, Int]): Map[A, Int] =
  merge(a, b)((v1, v2) => v2.map(_ + v1).getOrElse(v1))

Example:

val a = Map("a" -> 1, "b" -> 5, "c" -> 6)
val b = Map("a" -> 4, "z" -> 8)
mergeIntSum(a, b)
res0: Map[String,Int] = Map(a -> 5, b -> 5, c -> 6, z -> 8)

There is a Scala module called scala-collection-contrib, which offers very useful methods like mergeByKey.

First, we need to add an additional dependency to build.sbt:

libraryDependencies += "org.scala-lang.modules" %% "scala-collection-contrib" % "0.1.0"

and then it's possible to do merge like this:

import scala.collection.decorators._

val map1 = Map(1 -> Class1(1), 2 -> Class1(2))
val map2 = Map(2 -> Class2(1), 3 -> Class2(2))

map1.mergeByKeyWith(map2){
  case (a,b) => a.toList ++ b.toList
}

Solution to combine two maps: Map[A,B], the result type: Map[A,List[B]] via the Scala Cats (slightly improved version, offered by @David Castillo)

//convert each original map to Map[A,List[B]]. //Add an instance of Monoid[List] into the scope to combine lists:

import cats.instances.map._ // for Monoid
import cats.syntax.semigroup._ // for |+|
import cats.instances.list._

val map1 = Map("a" -> 1, "b" -> 2)
  .mapValues(List(_))
val map2 = Map("b" -> 3, "d" -> 4)
  .mapValues(List(_))
map1 |+| map2

If you don't want to mess around with original maps you could do something like following

val target = map1.clone()
val source = map2.clone()
source.foreach(e => target += e._1 -> e._2)

left.keys map { k => k -> List(left(k),right(k)) } toMap

Is concise and will work, assuming your two maps are left and right. Not sure about efficiency.

But your question is a bit ambiguous, for two reasons. You don't specify

1. The subtyping relationship between the values (i.e. class1,class2),
2. What happens if the maps have different keys

For the first case, consider the following example:

val left = Map("foo" ->1, "bar" ->2)
val right = Map("bar" -> 'a', "foo" -> 'b')

Which results in

res0: Map[String,List[Int]] = Map(foo -> List(1, 98), bar -> List(2, 97))

Notice how the Chars have been converted to Ints, because of the scala type hierarchy. More generally, if in your example class1 and class2 are not related, you would get back a List[Any]; this is probably not what you wanted.

You can work around this by dropping the List constructor from my answer; this will return Tuples which preserve the type:

res0: Map[String,(Int, Char)] = Map(foo -> (1,b), bar -> (2,a))

The second problem is what happens when you have maps that don't have the same keys. This will result in a key not found exception. Put in another way, are you doing a left, right, or inner join of the two maps? You can disambiguate the type of join by switching to right.keys or right.keySet ++ left.keySet for right/inner joins respectively. The later will work around the missing key problem, but maybe that's not what you want i.e. maybe you want a left or right join instead. In that case you can consider using the withDefault method of Map to ensure every key returns a value, e.g. None, but this needs a bit more work.

m2.foldLeft(m1.mapValues{List[CommonType](_)}) { case (acc, (k, v)) =>
  acc.updated(k, acc.getOrElse(k, List.empty) :+ v)
}

As noted by jwvh, List type should be specified explicitly if Class1 is not upper type bound for Class2. CommonType is a type which is upper bound for both Class1 and Class2.

This answer does not solve the initial question directly although it solves a common/related scenario which is merging two maps by the common keys.

Based on @Drexin's answer I wrote a generic method to extend the existing Map functionality by providing a join method for Maps:

object implicits {
  type A = Any
  implicit class MapExt[K, B <: A, C <: A](val left: immutable.Map[K, B]) {
    def join(right: immutable.Map[K, C]) : immutable.Map[K, Seq[A]] = {
      val inter = left.keySet.intersect(right.keySet)

      val leftFiltered =  left.filterKeys{inter.contains}
      val rightFiltered = right.filterKeys{inter.contains}

      (leftFiltered.toSeq ++ rightFiltered.toSeq)
        .groupBy(_._1)
        .mapValues(_.map{_._2}.toList)
    }
  }
}

Notes:

• Join is based on intersection of the keys, which resembles an "inner join" from the SQL world.
• It works with Scala <= 2.12, for Scala 2.13 consider using groupMap as @Xavier Guihot suggested.
• Consider replacing type A with your own base type.

Usage:

import implicits._

val m1 = Map("k11" -> "v11", "k12" -> "v12")
val m2 = Map("k11" -> "v21", "k12" -> "v22", "k13" -> "v23")
      
println (m1 join m2)
// Map(k11 -> List(v11, v21), k12 -> List(v12, v22))

this's two map merge

  def mergeMap[A, B](map1: Map[A, B], map2: Map[A, B], op: (B, B) => B, default: => B): Map[A, B] = (map1.keySet ++ map2.keySet).map(x => (x, op(map1.getOrElse(x, default), map2.getOrElse(x, default)))).toMap

this’s multiple map merge

  def mergeMaps[A, B](maps: Seq[Map[A, B]], op: (B, B) => B, default: => B): Map[A, B] = maps.reduce((a, b) => mergeMap(a, b, op, default))