Elegancki sposób odwrócenia mapy w Scala

Question

Nauka Scala obecnie i potrzebna do odwrócenia mapy, aby wykonać odwrócone wartości-> wyszukiwania kluczy. Szukałem prostego sposobu, aby to zrobić, ale wymyśliłem tylko:

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

Ktoś ma bardziej eleganckie podejście?

Answer 1

wartości Zakładając są wyjątkowe, to działa:

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

Na Scala 2.8, jednak łatwiej:

origMap.map(_.swap) 

Będąc w stanie zrobić to jednym z powodów dlaczego Scala 2.8 ma nowa biblioteka kolekcji.

Answer 2

Możesz uniknąć rzeczy ._1 podczas iteracji na kilka sposobów.

Oto jeden sposób. Wykorzystuje częściową funkcję, która obejmuje jeden i jedyny przypadek, że liczy na mapie:

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

Oto kolejny sposób:

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

Mapa iteracja wywołuje funkcję z dwóch elementów krotki i anonimowa funkcja chce dwóch parametrów. Function.tupled dokonuje tłumaczenia.

Answer 3

1. Odwrotny jest lepsza nazwa dla tej operacji niż rewersie (jak w „odwrotności funkcji matematycznej”)

2. ja często zrobić tę transformację odwrotną nie tylko na mapach, ale na innych (w tym kolejne) kolekcje. Uważam, że najlepiej nie ograniczać definicji mojej operacji odwrotnej do map typu jeden do jednego. Oto definicja, z którą operuję dla map (proszę sugerować ulepszenia mojej implementacji).

   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 
   } 
   

Jeśli jest to mapa jeden-do-jednego, kończy się z pojedynczych list, które mogą być trywialnie testowanych i przekształconych do mapy [b, a] zamiast mapą [b, listy [A ]].

Answer 4

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

Zauważ, że zduplikowane wartości zostaną zastąpione przez ostatni dodatek do mapy:

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

Przyjechałem tu szuka sposobu, aby odwrócić mapę typu Map [A, Seq [B]] na Map [B, Seq [A]], gdzie każde B na nowej mapie jest powiązane z każdym A na starej mapie, dla której B było zawarte w sekwencji A.

E.g.,
Map(1 -> Seq("a", "b"), 2-> Seq("b", "c"))
by odwrócić do
Map("a" -> Seq(1), "b" -> Seq(1, 2), "c" -> Seq(2))

Oto moje rozwiązanie:

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

gdzie oldMap jest typu Map[A, Seq[B]] i newMap jest typu Map[B, Seq[A]]

W zagnieżdżone foldLefts uczynić mnie trochę troche, ale to najprostszy sposób, jaki mogłem znaleźć, aby osiągnąć ten cel pe inwersji. Ktoś ma czystsze rozwiązanie?

Answer 6

Matematycznie, odwzorowanie nie może być odwracalna, na przykład, od Map[A,B], nie można dostać Map[B,A], ale raczej masz Map[B,Set[A]], bo nie może być różne klucze związane z tymi samymi wartościami. Tak więc, jeśli jesteś zainteresowany wiedząc, wszystkie klucze, oto kod:

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

Można odwrócić mapę za pomocą:

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

Problem z tego podejścia jest to, że jeśli wartości, które mają teraz stają się hashami na mapie, nie są unikatowe, usuniesz zduplikowane wartości. Aby zilustrować:

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) 

Aby tego uniknąć można konwertować mapy do listy krotek, potem odwrócić, tak aby nie upuścić żadnych zduplikowane wartości:

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

Możemy spróbować użyć ta funkcja foldLeft, która zajmie się kolizjami i odwróci mapę w pojedynczym ruchu.

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