Maneira elegante de inverter um mapa no Scala

Aprendendo Scala atualmente e necessário inverter um mapa para fazer algumas pesquisas de valor invertido-> chave. Eu estava procurando uma maneira simples de fazer isso, mas só encontrei:

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

Alguém tem uma abordagem mais elegante?

Assumindo que os valores são únicos, isso funciona:

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

No Scala 2.8, no entanto, é mais fácil:

origMap.map(_.swap)

Ser capaz de fazer isso é parte da razão pela qual Scala 2.8 tem uma nova biblioteca de coleção.

Matematicamente, o mapeamento pode não ser invertível (injetivo), por exemplo, de Map[A,B], você não pode obter Map[B,A], mas sim Map[B,Set[A]], porque pode haver chaves diferentes associadas aos mesmos valores. Então, se você estiver interessado em conhecer todas as chaves, aqui está o 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))

Você pode evitar as coisas ._1 enquanto itera de algumas maneiras.

Aqui está uma maneira. Isso usa uma função parcial que cobre o único caso que importa para o mapa:

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

Aqui está outra maneira:

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

A iteração do mapa chama uma função com uma tupla de dois elementos, e a função anônima deseja dois parâmetros. Function.tupled faz a tradução.

Eu vim aqui procurando uma maneira de inverter um Mapa do tipo Mapa [A, Seq [B]] para Mapa [B, Seq [A]], onde cada B no novo mapa está associado a cada A no mapa antigo para em que o B estava contido na sequência associada de A.

Por exemplo,
Map(1 -> Seq("a", "b"), 2-> Seq("b", "c"))
seria invertido para
Map("a" -> Seq(1), "b" -> Seq(1, 2), "c" -> Seq(2))

Esta é minha solução:

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

onde oldMap é do tipo Map[A, Seq[B]]e newMap é do tipoMap[B, Seq[A]]

Os foldLefts aninhados me fazem estremecer um pouco, mas esta é a maneira mais direta que encontrei de realizar esse tipo de inversão. Alguém tem uma solução mais limpa?

OK, então esta é uma pergunta muito antiga com muitas respostas boas, mas eu construí o Mapinversor definitivo e definitivo, canivete suíço, e este é o lugar para postá-lo.

Na verdade, são dois inversores. Um para elementos de valor individuais ...

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

... e outro, bastante semelhante, para coleções de valores.

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

Eu preferiria ter os dois métodos na mesma classe implícita, mas quanto mais tempo eu gastava examinando isso, mais problemático parecia.

Você pode inverter um mapa usando:

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

O problema com essa abordagem é que se seus valores, que agora se tornaram as chaves hash em seu mapa, não forem exclusivos, você descartará os valores duplicados. 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 isso, você pode primeiro converter seu mapa em uma lista de tuplas e, em seguida, inverter, para não eliminar nenhum 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))

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

Observe que os valores duplicados serão substituídos pela última adição ao 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)

Começando Scala 2.13, para trocar chaves / valores sem perder as chaves associadas aos mesmos valores, podemos usar Mapo novo método groupMap , que (como o próprio nome sugere) é equivalente a aegroupBy a mapping sobre itens agrupados.

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

Este:

• groupelementos s com base em sua segunda parte da tupla ( _._2) (parte do grupo do mapa do grupo )

• maps itens agrupados pegando sua primeira parte da tupla ( _._1) (parte do mapa do grupo Mapa )

Isso pode ser visto como uma versão de uma passagem do map.groupBy(_._2).mapValues(_.map(_._1)).

1. Inverso é um nome melhor para esta operação do que reverso (como em "inverso de uma função matemática")

2. Costumo fazer essa transformação inversa não apenas em mapas, mas em outras coleções (incluindo Seq). Acho melhor não limitar a definição da minha operação inversa a mapas um-para-um. Aqui está a definição com a qual trabalho para mapas (sugira melhorias para minha implementação).

   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
   }

Se for um mapa um-para-um, você acaba com listas singleton que podem ser trivialmente testadas e transformadas em um Mapa [B, A] ao invés de Mapa [B, Lista [A]].

Podemos tentar usar esta foldLeftfunção que cuidará das colisões e inverterá o mapa em uma travessia única.

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