Scala: comment fusionner une collection de cartes

Question

J'ai une liste de carte [String, Double], et je voudrais fusionner leur contenu en une seule carte [String, Double]. Comment dois-je faire cela de manière idiomatique? J'imagine que je devrais être capable de le faire avec un pli. Quelque chose comme:

val newMap = Map[String, Double]() /: listOfMaps { (accumulator, m) => ... } 

En outre, je voudrais gérer les collisions de clés d'une manière générique. Autrement dit, si j'ajoute une clé à la carte qui existe déjà, je devrais pouvoir spécifier une fonction qui renvoie un double (dans ce cas) et prend la valeur existante pour cette clé, plus la valeur que j'essaie d'ajouter . Si la clé n'existe pas encore dans la carte, il suffit de l'ajouter et sa valeur non modifiée.

Dans mon cas spécifique, je voudrais construire une seule carte [Chaîne, Double] telle que si la carte contient déjà une clé, alors le Double sera ajouté à la valeur de carte existante.

Je travaille avec des cartes mutables dans mon code spécifique, mais je suis intéressé par des solutions plus génériques, si possible.

Answer 1

Que diriez-vous celui-ci:

def mergeMap[A, B](ms: List[Map[A, B]])(f: (B, B) => B): Map[A, B] = 
    (Map[A, B]() /: (for (m <- ms; kv <- m) yield kv)) { (a, kv) => 
    a + (if (a.contains(kv._1)) kv._1 -> f(a(kv._1), kv._2) else kv) 
    } 

val ms = List(Map("hello" -> 1.1, "world" -> 2.2), Map("goodbye" -> 3.3, "hello" -> 4.4)) 
val mm = mergeMap(ms)((v1, v2) => v1 + v2) 

println(mm) // prints Map(hello -> 5.5, world -> 2.2, goodbye -> 3.3) 

Et cela fonctionne dans les deux 2.7.5 et 2.8.0.

Answer 2

Eh bien, vous pouvez faire:

mapList reduce (_ ++ _) 

sauf l'exigence spéciale de collision.

Puisque vous avez cette exigence particulière, peut-être le mieux serait de faire quelque chose comme ça (2.8):

def combine(m1: Map, m2: Map): Map = { 
    val k1 = Set(m1.keysIterator.toList: _*) 
    val k2 = Set(m2.keysIterator.toList: _*) 
    val intersection = k1 & k2 

    val r1 = for(key <- intersection) yield (key -> (m1(key) + m2(key))) 
    val r2 = m1.filterKeys(!intersection.contains(_)) ++ m2.filterKeys(!intersection.contains(_)) 
    r2 ++ r1 
} 

Vous pouvez ensuite ajouter cette méthode à la classe de carte à travers le motif Pimp Ma bibliothèque, et l'utiliser dans l'exemple d'origine au lieu de « ++ »:

class CombiningMap(m1: Map[Symbol, Double]) { 
    def combine(m2: Map[Symbol, Double]) = { 
    val k1 = Set(m1.keysIterator.toList: _*) 
    val k2 = Set(m2.keysIterator.toList: _*) 
    val intersection = k1 & k2 
    val r1 = for(key <- intersection) yield (key -> (m1(key) + m2(key))) 
    val r2 = m1.filterKeys(!intersection.contains(_)) ++ m2.filterKeys(!intersection.contains(_)) 
    r2 ++ r1 
    } 
} 

// Then use this: 
implicit def toCombining(m: Map[Symbol, Double]) = new CombiningMap(m) 

// And finish with: 
mapList reduce (_ combine _) 

Bien que cela a été écrit en 2.8, donc keysIterator devient keys 2,7, filterKeys faudra peut-être écrit en termes de filter et map, & devient **, et ainsi de suite, il ne devrait pas être trop différent.

Answer 3

Intéressant, noodling autour de cela un peu, je suis la suivante (sur 2.7.5):

général Cartes:

def mergeMaps[A,B](collisionFunc: (B,B) => B)(listOfMaps: Seq[scala.collection.Map[A,B]]): Map[A, B] = { 
    listOfMaps.foldLeft(Map[A, B]()) { (m, s) => 
     Map(
     s.projection.map { pair => 
     if (m contains pair._1) 
      (pair._1, collisionFunc(m(pair._1), pair._2)) 
     else 
      pair 
     }.force.toList:_*) 
    } 
    } 

Mais l'homme, qui est hideux avec la projection et en forçant et toList et autres joyeusetés. Question distincte: quelle est la meilleure façon de faire face à ce problème?

Pour mutables Cartes, qui est ce que je traitais dans mon code, et avec une solution moins générale, je me suis ceci:

def mergeMaps[A,B](collisionFunc: (B,B) => B)(listOfMaps: List[mutable.Map[A,B]]): mutable.Map[A, B] = { 
    listOfMaps.foldLeft(mutable.Map[A,B]()) { 
     (m, s) => 
     for (k <- s.keys) { 
     if (m contains k) 
      m(k) = collisionFunc(m(k), s(k)) 
     else 
      m(k) = s(k) 
     } 
     m 
    } 
    } 

qui semble un peu plus propre, mais ne fonctionne qu'avec mutable Cartes comme il est écrit. Fait intéressant, j'ai d'abord essayé ce qui précède (avant de poser la question) en utilisant /: au lieu de foldLeft, mais je recevais des erreurs de type. Je pensais /: et foldLeft étaient fondamentalement équivalents, mais le compilateur continuait de se plaindre que j'avais besoin de types explicites pour (m, s). Qu'est-ce qui se passe avec ça?

Answer 4

Je lisant cette question rapidement, donc je ne sais pas si je manque quelque chose (comme il doit travailler pour 2.7.x ou non scalaz):

import scalaz._ 
import Scalaz._ 
val ms = List(Map("hello" -> 1.1, "world" -> 2.2), Map("goodbye" -> 3.3, "hello" -> 4.4)) 
ms.reduceLeft(_ |+| _) 
// returns Map(goodbye -> 3.3, hello -> 5.5, world -> 2.2) 

Vous pouvez modifier la définition monoid pour Double et obtenir une autre façon d'accumuler les valeurs, ici obtenir le maximum:

implicit val dbsg: Semigroup[Double] = semigroup((a,b) => math.max(a,b)) 
ms.reduceLeft(_ |+| _) 
// returns Map(goodbye -> 3.3, hello -> 4.4, world -> 2.2) 

Answer 5

une oneliner aide-Func, dont l'utilisation se lit presque aussi propre que l'utilisation scalaz:

def mergeMaps[K,V](m1: Map[K,V], m2: Map[K,V])(f: (V,V) => V): Map[K,V] = 
    (m1 -- m2.keySet) ++ (m2 -- m1.keySet) ++ (for (k <- m1.keySet & m2.keySet) yield { k -> f(m1(k), m2(k)) }) 

val ms = List(Map("hello" -> 1.1, "world" -> 2.2), Map("goodbye" -> 3.3, "hello" -> 4.4)) 
ms.reduceLeft(mergeMaps(_,_)(_ + _)) 
// returns Map(goodbye -> 3.3, hello -> 5.5, world -> 2.2) 

pour une meilleure lisibilité ultime envelopper dans un type personnalisé implicite:

class MyMap[K,V](m1: Map[K,V]) { 
    def merge(m2: Map[K,V])(f: (V,V) => V) = 
    (m1 -- m2.keySet) ++ (m2 -- m1.keySet) ++ (for (k <- m1.keySet & m2.keySet) yield { k -> f(m1(k), m2(k)) }) 
} 
implicit def toMyMap[K,V](m: Map[K,V]) = new MyMap(m) 

val ms = List(Map("hello" -> 1.1, "world" -> 2.2), Map("goodbye" -> 3.3, "hello" -> 4.4)) 
ms reduceLeft { _.merge(_)(_ + _) } 

Answer 6

J'ai écrit un billet de blog à ce sujet, check it out:

http://www.nimrodstech.com/scala-map-merge/

essentiellement en utilisant le groupe semi-scalaz vous pouvez obtenir ce assez facilement

ressemblerait à quelque chose comme:

import scalaz.Scalaz._ 
    listOfMaps reduce(_ |+| _) 

Answer 7

Je suis surpris personne ne est venu avec cette solution encore:

myListOfMaps.flatten.toMap 

fait exactement ce dont vous avez besoin:

1. Fusionne la liste à une seule carte
2. les mauvaises herbes tout en double clés

Exemple:

scala> List(Map('a -> 1), Map('b -> 2), Map('c -> 3), Map('a -> 4, 'b -> 5)).flatten.toMap 
res7: scala.collection.immutable.Map[Symbol,Int] = Map('a -> 4, 'b -> 5, 'c -> 3) 

flatten transforme la liste des cartes dans une liste plate de tuples, toMap transforme la liste de tuples en une carte avec toutes les clés en double enlevé