Elegancki sposób na odwrócenie mapy w Scali

Nauka Scali jest obecnie potrzebna do odwrócenia mapy, aby wykonać kilka odwróconych wartości-> wyszukiwania kluczy. Szukałem prostego sposobu na zrobienie tego, ale wymyśliłem tylko:

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

Czy ktoś ma bardziej eleganckie podejście?

Zakładając, że wartości są unikalne, działa to:

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

W Scali 2.8 jest jednak łatwiej:

origMap.map(_.swap)

Możliwość tego jest jednym z powodów, dla których Scala 2.8 ma nową bibliotekę kolekcji.

Matematycznie mapowanie może nie być odwracalne (iniekcyjne), np. Z Map[A,B], którego nie można pobrać Map[B,A], ale raczej otrzymujemy Map[B,Set[A]], ponieważ mogą być różne klucze powiązane z tymi samymi wartościami. Jeśli więc chcesz poznać 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))

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

Oto jeden sposób. Używa częściowej funkcji, która obejmuje jedyny przypadek, który ma znaczenie dla mapy:

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

Oto inny sposób:

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

Iteracja mapy wywołuje funkcję z dwuelementową krotką, a funkcja anonimowa potrzebuje dwóch parametrów. Function.tupled dokonuje tłumaczenia.

Przyszedłem tutaj, szukając sposobu na odwrócenie mapy typu Map [A, Seq [B]] na Map [B, Seq [A]], gdzie każdy B na nowej mapie jest powiązany z każdym A na starej mapie dla które B było zawarte w sekwencji skojarzonej z A.

Np.
Map(1 -> Seq("a", "b"), 2-> Seq("b", "c"))
Odwróciłby się 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 staraMapa jest typu, Map[A, Seq[B]]a nowaMapa jest typuMap[B, Seq[A]]

Zagnieżdżone foldLefts sprawiają, że trochę się wzdrygam, ale jest to najprostszy sposób na wykonanie tego typu inwersji. Czy ktoś ma czystsze rozwiązanie?

OK, więc jest to bardzo stare pytanie z wieloma dobrymi odpowiedziami, ale zbudowałem ostateczny, uniwersalny, szwajcarski scyzoryk, Mapfalownik i jest to miejsce, w którym można to opublikować.

Właściwie to dwa falowniki. Jeden dla poszczególnych elementów wartości ...

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

... i inny, całkiem podobny, dla kolekcji wartościowych.

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

stosowanie:

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

Wolałbym mieć obie metody w tej samej niejawnej klasie, ale im więcej czasu poświęcałem na jej badanie, tym bardziej wydawało się to problematyczne.

Możesz odwrócić mapę używając:

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

Problem z tym podejściem polega na tym, że jeśli wartości, które stały się kluczami mieszania na mapie, nie są unikalne, zduplikowane wartości zostaną usunięte. Ilustrować:

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żesz najpierw przekonwertować mapę na listę krotek, a następnie odwrócić, aby nie upuścić żadnych zduplikowanych 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))

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

Zwróć uwagę, że zduplikowane wartości zostaną zastąpione ostatnim dodatkiem 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)

Zaczynając Scala 2.13, aby zamienić klucz / wartości bez utraty kluczy skojarzonych z tymi samymi wartościami, możemy skorzystać z Mapnowej metody groupMap , która (jak sama nazwa wskazuje) jest odpowiednikiem groupByai mapping na zgrupowanych elementach.

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

To:

• groupelementy s oparte na drugiej części krotki ( _._2) (część grupowa mapy grupy )

• maps pogrupowane elementy, biorąc ich pierwszą część krotki ( _._1) (część mapy grupy mapy )

Może to być postrzegane jako wersja jednego przejścia z map.groupBy(_._2).mapValues(_.map(_._1)).

1. Odwrotna to lepsza nazwa dla tej operacji niż odwrotna (np. „Odwrotność funkcji matematycznej”)

2. Często wykonuję tę odwrotną transformację nie tylko na mapach, ale na innych kolekcjach (w tym Seq). Uważam, że najlepiej nie ograniczać definicji mojej operacji odwrotnej do map jeden do jednego. Oto definicja, z jaką 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, otrzymujesz listy singletonów, które można trywialnie przetestować i przekształcić w Mapę [B, A], a nie Map [B, List [A]].

Możemy spróbować użyć tej foldLeftfunkcji, która zajmie się kolizjami i odwróci mapę w pojedynczym przejściu.

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