Modo elegante per invertire una mappa in Scala

Question

Imparare Scala al momento e necessario per invertire una mappa per fare qualche valore invertito-> ricerca chiavi. Stavo cercando un modo semplice per farlo, ma ho trovato solo:

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

Chiunque ha un approccio più elegante?

Answer 1

valori Supponendo sono uniche, questo funziona:

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

Su Scala 2.8, tuttavia, è più facile:

origMap.map(_.swap) 

Essere in grado di fare che è parte del motivo per cui Scala 2.8 ha un nuova biblioteca di raccolta.

Answer 2

È possibile evitare il contenuto di ._1 mentre si itera in alcuni modi.

Ecco un modo. Questo utilizza una funzione parziale che copre l'unico caso che conta per la mappa:

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

Ecco un altro modo:

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

La mappa iterazione chiama una funzione con un elemento tupla due, e la la funzione anonima vuole due parametri. Function.tupled rende la traduzione.

Answer 3

1. inversa è un nome migliore per questa operazione di inversione (come in "inversa di una funzione matematica")

2. faccio spesso questa trasformazione inversa non solo sulle mappe, ma su altre (tra cui Seq) collezioni. Trovo sia meglio non limitare la definizione della mia operazione inversa a mappe one-to-one. Ecco la definizione con cui lavoro per le mappe (si prega di suggerire miglioramenti alla mia implementazione).

   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 si tratta di una mappa uno-a-uno, si finisce con gli elenchi di unico che può essere banalmente testati e trasformato in un Map [B, A] piuttosto che mappa [B, Lista [A ]].

Answer 4

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

Nota che duplicano i valori saranno sovrascritti da l'ultima aggiunta alla mappa:

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) 

Answer 5

Sono venuto qui in cerca di un modo per invertire una mappa di tipo Mappa [A, Seq [B]] per mappare [B, Seq [A]], dove ogni B nella nuova mappa è associata ad ogni A nella vecchia mappa per cui la B era contenuta nella sequenza associata di A.

E.g.,
Map(1 -> Seq("a", "b"), 2-> Seq("b", "c"))
sarebbe capovolgere per
Map("a" -> Seq(1), "b" -> Seq(1, 2), "c" -> Seq(2))

Ecco la mia soluzione:

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

dove oldMap è di tipo Map[A, Seq[B]] e newMap è di tipo Map[B, Seq[A]]

I foldLefts nidificate mi fanno rabbrividisco un po ', ma questo è il modo più diretto che potrei trovare per realizzare questo ty pe di inversione. Qualcuno ha una soluzione più pulita?

Answer 6

Matematicamente, la mappatura potrebbe non essere invertibile, per esempio, da Map[A,B], non è possibile ottenere Map[B,A], ma piuttosto si ottiene Map[B,Set[A]], perché ci potrebbero essere diversi tasti associati stessi valori. Quindi, se siete interessati a conoscere tutte le chiavi, ecco il codice:

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

Answer 7

Si potrebbe invertire una mappa utilizzando:

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

Il problema di questo approccio è che se i valori, che hanno ora diventano le chiavi di hash nella tua mappa, non sono univoci, i valori duplicati cadranno. Per illustrare:

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) 

per evitare questo è possibile convertire la vostra mappa per una lista di tuple, poi invertire, in modo da non far cadere eventuali valori duplicati:

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

Answer 8

Possiamo provare a utilizzare questa funzione foldLeft che si occuperà delle collisioni e invertirà la mappa 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))