Une façon élégante d'inverser une carte dans Scala

Question

Apprendre Scala actuellement et nécessaire pour inverser une carte pour faire des recherches inversées valeur-> clé. Je cherchais un moyen simple de le faire, mais est venu avec seulement:

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

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

Answer 1

valeurs En supposant sont uniques, cela fonctionne:

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

Sur Scala 2.8, cependant, il est plus facile:

origMap.map(_.swap) 

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

Answer 2

Vous pouvez éviter le contenu ._1 en effectuant plusieurs itérations.

Voici un moyen. Celui-ci utilise une fonction partielle qui couvre l'un et seul 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 carte appelle une fonction avec deux tuple élément, et fonction anonyme veut deux paramètres. Function.tupled fait la traduction.

Answer 3

1. inverse est un meilleur nom pour cette opération que la marche arrière (comme dans « inverse d'une fonction mathématique »)

2. Je fais souvent cette transformation inverse non seulement sur les cartes, mais sur d'autres (y compris Seq) collections. 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 je travaille pour les cartes (veuillez suggérer des améliorations à ma mise en œuvre).

   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 à une carte, vous vous retrouvez avec des listes uniques qui peuvent être trivialement testés et transformé à une carte [B, A] plutôt que la carte [B, Liste [A ]].

Answer 4

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 dupliquer les valeurs seront remplacé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) 

Answer 5

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

E.g.,
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 type Map[B, Seq[A]]

Les foldLefts imbriquées me faire grincer un peu, mais c'est la façon la plus simple que je pourrais trouver pour accomplir ce ty pe d'inversion. Quelqu'un at-il une solution plus propre?

Answer 6

Mathématiquement, la cartographie pourrait ne pas être inversible, par exemple, de Map[A,B], vous ne pouvez pas obtenir Map[B,A], mais plutôt vous faire Map[B,Set[A]], parce qu'il pourrait y avoir différentes clés associées aux mêmes valeurs. Donc, si vous êtes intéressé à 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)) 

Answer 7

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 ont maintenant devenir les clés de hachage dans votre carte, ne sont pas uniques, vous allez supprimer 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 convertir votre carte à une liste de tuples d'abord, puis inverser, de sorte que vous ne laissez pas tomber de valeurs 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)) 

Answer 8

Nous pouvons essayer d'utiliser cette fonction foldLeft prendra en charge les collisions et inversera la carte en traversée simple.

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