Elegant way to invert a map in Scala

Learning Scala curren开发者_运维技巧tly and needed to invert a Map to do some inverted value->key lookups. I was looking for a simple way to do this, but came up with only:

(Map() ++ origMap.map(kvp=>(kvp._2->kvp._1)))

Anybody have a more elegant approach?

Assuming values are unique, this works:

(Map() ++ origMap.map(_.swap))

On Scala 2.8, however, it's easier:

origMap.map(_.swap)

Being able to do that is part of the reason why Scala 2.8 has a new collection library.

Mathematically, the mapping might not be invertible (injective), e.g., from Map[A,B], you can't get Map[B,A], but rather you get Map[B,Set[A]], because there might be different keys associated with same values. So, if you are interested in knowing all the keys, here's the code:

val m = Map(1 -> "a", 2 -> "b", 4 -> "b")
m.groupBy(_._2).mapValues(_.keys)

res0: Map[String,Iterable[Int]] = Map(b -> Set(2, 4), a -> Set(1))

Starting scala 2.13, this becomes even simpler and more efficient:

m.groupMap(_._2)(_._1)

You can avoid the ._1 stuff while iterating in few ways.

Here's one way. This uses a partial function that covers the one and only case that matters for the map:

Map() ++ (origMap map {case (k,v) => (v,k)})

Here's another way:

import Function.tupled        
Map() ++ (origMap map tupled {(k,v) => (v,k)})

The map iteration calls a function with a two element tuple, and the anonymous function wants two parameters. Function.tupled makes the translation.

OK, so this is a very old question with many good answers, but I've built the ultimate, be-all-and-end-all, Swiss-Army-knife, Map inverter and this is the place to post it.

It's actually two inverters. One for individual value elements...

//from Map[K,V] to Map[V,Set[K]], traverse the input only once
implicit class MapInverterA[K,V](m :Map[K,V]) {
  def invert :Map[V,Set[K]] =
    m.foldLeft(Map.empty[V, Set[K]]) {
      case (acc,(k, v)) => acc + (v -> (acc.getOrElse(v,Set()) + k))
    }
}

...and another, quite similar, for value collections.

import scala.collection.generic.CanBuildFrom
import scala.collection.mutable.Builder
import scala.language.higherKinds

//from Map[K,C[V]] to Map[V,C[K]], traverse the input only once
implicit class MapInverterB[K,V,C[_]](m :Map[K,C[V]]
                                     )(implicit ev :C[V] => TraversableOnce[V]) {
  def invert(implicit bf :CanBuildFrom[Nothing,K,C[K]]) :Map[V,C[K]] =
    m.foldLeft(Map.empty[V, Builder[K,C[K]]]) {
      case (acc, (k, vs)) =>
        vs.foldLeft(acc) {
          case (a, v) => a + (v -> (a.getOrElse(v,bf()) += k))
        }
    }.mapValues(_.result())
}

usage:

Map(2 -> Array('g','h'), 5 -> Array('g','y')).invert
//res0: Map(g -> Array(2, 5), h -> Array(2), y -> Array(5))

Map('q' -> 1.1F, 'b' -> 2.1F, 'c' -> 1.1F, 'g' -> 3F).invert
//res1: Map(1.1 -> Set(q, c), 2.1 -> Set(b), 3.0 -> Set(g))

Map(9 -> "this", 8 -> "that", 3 -> "thus", 2 -> "thus").invert
//res2: Map(this -> Set(9), that -> Set(8), thus -> Set(3, 2))

Map(1L -> Iterator(3,2), 5L -> Iterator(7,8,3)).invert
//res3: Map(3 -> Iterator(1, 5), 2 -> Iterator(1), 7 -> Iterator(5), 8 -> Iterator(5))

Map.empty[Unit,Boolean].invert
//res4: Map[Boolean,Set[Unit]] = Map()

I would prefer to have both methods in the same implicit class but the more time I spent looking into it the more problematic it appeared.

I came here looking for a way to invert a Map of type Map[A, Seq[B]] to Map[B, Seq[A]], where each B in the new map is associated with every A in the old map for which the B was contained in A's associated sequence.

E.g.,
Map(1 -> Seq("a", "b"), 2-> Seq("b", "c"))
would invert to
Map("a" -> Seq(1), "b" -> Seq(1, 2), "c" -> Seq(2))

Here's my solution :

val newMap = oldMap.foldLeft(Map[B, Seq[A]]().withDefaultValue(Seq())) {
  case (m, (a, bs)) => bs.foldLeft(m)((map, b) => map.updated(b, m(b) :+ a))
}

where oldMap is of type Map[A, Seq[B]] and newMap is of type Map[B, Seq[A]]

The nested foldLefts make me cringe a little bit, but this is the most straightforward way I could find to accomplish this type of inversion. Anyone have a cleaner solution?

You could invert a map using:

val i = origMap.map({case(k, v) => v -> k})

The problem with this approach is that if your values, which have now become the hash keys in your map, are not unique you will drop the duplicate values. To illustrate:

scala> val m = Map("a" -> 1, "b" -> 2, "c" -> 3, "d" -> 1)
m: scala.collection.immutable.Map[String,Int] = Map(a -> 1, b -> 2, c -> 3, d -> 1)

// Notice that 1 -> a is not in our inverted map
scala> val i = m.map({ case(k , v) => v -> k})
i: scala.collection.immutable.Map[Int,String] = Map(1 -> d, 2 -> b, 3 -> c)

To avoid this you can convert your map to a list of tuples first, then invert, so that you don't drop any duplicate values:

scala> val i = m.toList.map({ case(k , v) => v -> k})
i: List[(Int, String)] = List((1,a), (2,b), (3,c), (1,d))

Starting Scala 2.13, in order to swap key/values without loosing keys associated to same values, we can use Maps new groupMap method, which (as its name suggests) is an equivalent of a groupBy and a mapping over grouped items.

Map(1 -> "a", 2 -> "b", 4 -> "b").groupMap(_._2)(_._1)
// Map("b" -> List(2, 4), "a" -> List(1))

This:

• groups elements based on their second tuple part (_._2) (group part of groupMap)

• maps grouped items by taking their first tuple part (_._1) (map part of groupMap)

This can be seen as a one-pass version of map.groupBy(_._2).mapValues(_.map(_._1)).

In scala REPL:

scala> val m = Map(1 -> "one", 2 -> "two")
m: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> one, 2 -> two)

scala> val reversedM = m map { case (k, v) => (v, k) }
reversedM: scala.collection.immutable.Map[java.lang.String,Int] = Map(one -> 1, two -> 2)

Note that duplicate values will be overwritten by the last addition to the map:

scala> val m = Map(1 -> "one", 2 -> "two", 3 -> "one")
m: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> one, 2 -> two, 3 -> one)

scala> val reversedM = m map { case (k, v) => (v, k) }
reversedM: scala.collection.immutable.Map[java.lang.String,Int] = Map(one -> 3, two -> 2)

1. Inverse is a better name for this operation than reverse (as in "inverse of a mathematical function")

2. I often do this inverse transformation not only on maps but on other (including Seq) collections. I find it best not to limit the definition of my inverse operation to one-to-one maps. Here's the definition I operate with for maps (please suggest improvements to my implementation).

   def invertMap[A,B]( m: Map[A,B] ) : Map[B,List[A]] = {
     val k = ( ( m values ) toList ) distinct
     val v = k map { e => ( ( m keys ) toList ) filter { x => m(x) == e } }
     ( k zip v ) toMap
   }
   

If it's a one-to-one map, you end up with singleton lists which can be trivially tested and transformed to a Map[B,A] rather than Map[B,List[A]].

We can try using this foldLeft function that will take care of collisions and invert the map in single traversal.

scala> def invertMap[A, B](inputMap: Map[A, B]): Map[B, List[A]] = {
     |     inputMap.foldLeft(Map[B, List[A]]()) {
     |       case (mapAccumulator, (value, key)) =>
     |         if (mapAccumulator.contains(key)) {
     |           mapAccumulator.updated(key, mapAccumulator(key) :+ value)
     |         } else {
     |           mapAccumulator.updated(key, List(value))
     |         }
     |     }
     |   }
invertMap: [A, B](inputMap: Map[A,B])Map[B,List[A]]

scala> val map = Map(1 -> 2, 2 -> 2, 3 -> 3, 4 -> 3, 5 -> 5)
map: scala.collection.immutable.Map[Int,Int] = Map(5 -> 5, 1 -> 2, 2 -> 2, 3 -> 3, 4 -> 3)

scala> invertMap(map)
res0: Map[Int,List[Int]] = Map(5 -> List(5), 2 -> List(1, 2), 3 -> List(3, 4))

scala> val map = Map("A" -> "A", "B" -> "A", "C" -> "C", "D" -> "C", "E" -> "E")
map: scala.collection.immutable.Map[String,String] = Map(E -> E, A -> A, B -> A, C -> C, D -> C)

scala> invertMap(map)
res1: Map[String,List[String]] = Map(E -> List(E), A -> List(A, B), C -> List(C, D))