How to invert a map in scala?

Question

What is the shortest/idiomatic way to invert from Map[K, V] to Map[V, Iterable[K]] in Scala?

While it's true that this question overlaps the other, the top answers for the other assume that the map to be inverted is an injection (no two keys map to the same value). Not so for this question, and that is a critical difference. Also, this question uses the standard term "invert" rather than "reverse". Perhaps this question should be changed to "How can I invert a non-injective Map in Scala?" and the other to "How can I invert an injective Map in Scala?" — AmigoNico, Apr 07 '13 at 18:34

score 7 · Accepted Answer · answered Apr 07 '13 at 12:53

Marius' solution can be simplified using mapValues,

m.groupBy(_._2).mapValues(_.map(_._1))

Sample REPL session,

scala> val m = Map(1 -> "foo", 2 -> "foo", 3 -> "bar", 4 -> "bar", 5 -> "baz")
m: Map[Int,String] = Map(5 -> baz, 1 -> foo, 2 -> foo, 3 -> bar, 4 -> bar)

scala> m.groupBy(_._2).mapValues(_.map(_._1))
res0: Map[String, Iterable[Int]] = Map(baz -> List(5), foo -> List(1, 2), bar -> List(3, 4))

Marius Danila · Answer 2 · 2013-04-07T11:26:53.520

This should do the trick:

def invert[A, B](m: Map[A, B]): Map[B, Iterable[A]] = {
  m.groupBy(_._2).map {
    case (v, kvPairs) => (v, kvPairs.map(_._1))
  }
}

This iterates over the key-value pairs in the map and groups the pairs using the value (_._2 is a getter for the second element of a tuple).

This gets us a list of pairs where the first element is the value and the second element is a sequence containing all the pairs in the original map that have as the second element that value.

And finally, for each of these latter pairs, we extract only the first element from the sequence - thus obtaining for a value all the keys that mapped to it in the original map.

How to invert a map in scala?

2 Answers2