Manera elegante de invertir un mapa en Scala

Aprendiendo Scala actualmente y necesitaba invertir un mapa para hacer algunas búsquedas de valores invertidos-> claves. Estaba buscando una forma sencilla de hacer esto, pero solo se me ocurrió:

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

¿Alguien tiene un enfoque más elegante?

Suponiendo que los valores son únicos, esto funciona:

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

En Scala 2.8, sin embargo, es más fácil:

origMap.map(_.swap)

Poder hacer eso es parte de la razón por la que Scala 2.8 tiene una nueva biblioteca de colección.

Matemáticamente, el mapeo puede no ser invertible (inyectivo), por ejemplo, de Map[A,B], no se puede obtener Map[B,A], sino que se obtiene Map[B,Set[A]], porque puede haber diferentes claves asociadas con los mismos valores. Entonces, si está interesado en conocer todas las claves, aquí está el código:

scala> val m = Map(1 -> "a", 2 -> "b", 4 -> "b")
scala> m.groupBy(_._2).mapValues(_.keys)
res0: Map[String,Iterable[Int]] = Map(b -> Set(2, 4), a -> Set(1))

Puede evitar las cosas ._1 mientras itera de varias maneras.

He aquí una forma. Esto usa una función parcial que cubre el único caso que importa para el mapa:

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

He aquí otra forma:

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

La iteración del mapa llama a una función con una tupla de dos elementos y la función anónima quiere dos parámetros. Function.tupled realiza la traducción.

Vine aquí buscando una manera de invertir un mapa de tipo Map [A, Seq [B]] a Map [B, Seq [A]], donde cada B en el nuevo mapa está asociado con cada A en el mapa antiguo para que el B estaba contenido en la secuencia asociada de A.

Por ejemplo,
Map(1 -> Seq("a", "b"), 2-> Seq("b", "c"))
invertiría a
Map("a" -> Seq(1), "b" -> Seq(1, 2), "c" -> Seq(2))

Esta es mi solución:

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))
}

donde oldMap es de tipo Map[A, Seq[B]]y newMap es de tipoMap[B, Seq[A]]

Los foldLefts anidados me hacen encoger un poco, pero esta es la forma más sencilla que pude encontrar para lograr este tipo de inversión. ¿Alguien tiene una solución más limpia?

De acuerdo, esta es una pregunta muy antigua con muchas buenas respuestas, pero he construido el Mapinversor de navaja suiza definitivo y definitivo y este es el lugar para publicarlo.

En realidad, son dos inversores. Uno para los elementos de valor individuales ...

//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))
    }
}

... y otro, bastante similar, para colecciones de valor.

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())
}

uso:

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()

Preferiría tener ambos métodos en la misma clase implícita, pero cuanto más tiempo pasaba investigándolo, más problemático parecía.

Puede invertir un mapa usando:

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

El problema con este enfoque es que si sus valores, que ahora se han convertido en las claves hash en su mapa, no son únicos, eliminará los valores duplicados. Para ilustrar:

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)

Para evitar esto, puede convertir su mapa en una lista de tuplas primero, luego invertir, para que no suelte ningún valor duplicado:

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

En 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)

Tenga en cuenta que los valores duplicados se sobrescribirán con la última adición al mapa:

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)

Comenzando Scala 2.13, para intercambiar claves / valores sin perder las claves asociadas a los mismos valores, podemos usar Mapel nuevo método groupMap , que (como su nombre indica) es un equivalente de aygroupBy un mapping sobre elementos agrupados.

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

Esta:

• groups elementos basados ​​en su segunda parte de tupla ( _._2) (parte de grupo del mapa de grupo )

• maps elementos agrupados mediante la adopción de su primera parte tupla ( _._1) (mapa de parte del grupo Mapa )

Esto puede verse como una versión de un solo paso de map.groupBy(_._2).mapValues(_.map(_._1)).

1. Inverso es un nombre mejor para esta operación que inverso (como en "inverso de una función matemática")

2. A menudo hago esta transformación inversa no solo en mapas sino en otras colecciones (incluida Seq). Me parece mejor no limitar la definición de mi operación inversa a mapas uno a uno. Aquí está la definición con la que opero para mapas (sugiera mejoras a mi implementación).

   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
   }

Si se trata de un mapa uno a uno, terminará con listas singleton que se pueden probar y transformar trivialmente en un mapa [B, A] en lugar de un mapa [B, lista [A]].

Podemos intentar usar esta foldLeftfunción que se encargará de las colisiones e invertirá el mapa en un solo recorrido.

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))