Manière élégante d'inverser une carte dans Scala

Apprentissage de Scala actuellement et nécessaire pour inverser une carte pour faire des recherches de valeurs inversées> clés. Je cherchais un moyen simple de le faire, mais je n'ai proposé que:

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

Quelqu'un a-t-il une approche plus élégante?

En supposant que les valeurs sont uniques, cela fonctionne:

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

Sur Scala 2.8, cependant, c'est plus simple:

origMap.map(_.swap)

Être capable de le faire fait partie de la raison pour laquelle Scala 2.8 a une nouvelle bibliothèque de collections.

Mathématiquement, le mappage peut ne pas être inversible (injectif), par exemple, à partir de Map[A,B], vous ne pouvez pas obtenir Map[B,A], mais plutôt vous obtenez Map[B,Set[A]], car il peut y avoir différentes clés associées aux mêmes valeurs. Donc, si vous souhaitez connaître toutes les clés, voici le code:

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

Vous pouvez éviter les éléments ._1 lors de l'itération de plusieurs façons.

Voici un moyen. Cela utilise une fonction partielle qui couvre le seul et unique cas qui compte pour la carte:

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

Voici une autre façon:

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

L'itération de la carte appelle une fonction avec un tuple à deux éléments et la fonction anonyme veut deux paramètres. Function.tupled effectue la traduction.

Je suis venu ici à la recherche d'un moyen d'inverser une carte de type Map [A, Seq [B]] en Map [B, Seq [A]], où chaque B de la nouvelle carte est associé à chaque A de l'ancienne carte pour dont le B était contenu dans la séquence associée de A.

Par exemple,
Map(1 -> Seq("a", "b"), 2-> Seq("b", "c"))
inverserait
Map("a" -> Seq(1), "b" -> Seq(1, 2), "c" -> Seq(2))

Voici ma solution:

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

où oldMap est de type Map[A, Seq[B]]et newMap est de typeMap[B, Seq[A]]

Les plis imbriqués me font un peu grincer des dents, mais c'est le moyen le plus simple que je puisse trouver pour accomplir ce type d'inversion. Quelqu'un a-t-il une solution plus propre?

OK, c'est donc une très vieille question avec de nombreuses bonnes réponses, mais j'ai construit l'ultime, le couteau suisse, l' Maponduleur et c'est ici qu'il faut l'afficher.

Il s'agit en fait de deux onduleurs. Un pour les éléments de valeur individuels ...

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

... et un autre, assez similaire, pour les collections de valeur.

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

usage:

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

Je préférerais avoir les deux méthodes dans la même classe implicite, mais plus je passais de temps à l'examiner, plus elle apparaissait problématique.

Vous pouvez inverser une carte en utilisant:

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

Le problème avec cette approche est que si vos valeurs, qui sont maintenant devenues les clés de hachage de votre carte, ne sont pas uniques, vous supprimerez les valeurs en double. Pour illustrer:

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)

Pour éviter cela, vous pouvez d'abord convertir votre carte en une liste de tuples, puis inverser, afin de ne supprimer aucune valeur en double:

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

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

Notez que les valeurs en double seront écrasées par le dernier ajout à la carte:

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)

Pour commencer Scala 2.13, pour échanger les clés / valeurs sans perdre les clés associées aux mêmes valeurs, nous pouvons utiliser la Mapnouvelle méthode groupMap , qui (comme son nom l'indique) est l'équivalent d'un groupByet d'un mapping sur des éléments groupés.

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

Ce:

• groups éléments basés sur leur deuxième partie de tuple ( _._2) (partie de groupe du groupe Map)

• maps éléments groupés en prenant leur première partie de tuple ( _._1) (partie map du groupe Map )

Cela peut être considéré comme une version en un seul passage de map.groupBy(_._2).mapValues(_.map(_._1)).

1. Inverse est un meilleur nom pour cette opération que reverse (comme dans "inverse d'une fonction mathématique")

2. Je fais souvent cette transformation inverse non seulement sur des cartes mais sur d'autres collections (y compris Seq). Je trouve préférable de ne pas limiter la définition de mon opération inverse aux cartes un-à-un. Voici la définition avec laquelle j'opère pour les cartes (veuillez suggérer des améliorations à mon implémentation).

   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 c'est une carte un-à-un, vous vous retrouvez avec des listes de singleton qui peuvent être testées de manière triviale et transformées en une carte [B, A] plutôt qu'en une carte [B, Liste [A]].

Nous pouvons essayer d'utiliser cette foldLeftfonction qui prendra en charge les collisions et inversera la carte en un seul parcours.

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