Scala: come unire una raccolta di mappe

Question

Ho un elenco di mappe [String, Double] e vorrei unire il loro contenuto in una singola mappa [String, Double]. Come dovrei farlo in modo idiomatico? Immagino che dovrei essere in grado di farlo con una piega. Qualcosa di simile:

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

Inoltre, mi piacerebbe gestire le collisioni con le chiavi in ​​un modo generico. Cioè, se aggiungo una chiave alla mappa che esiste già, dovrei essere in grado di specificare una funzione che restituisce un doppio (in questo caso) e prende il valore esistente per quella chiave, più il valore che sto cercando di aggiungere . Se la chiave non esiste ancora nella mappa, aggiungila e il suo valore inalterato.

Nel mio caso specifico mi piacerebbe costruire una singola mappa [String, Double] in modo tale che se la mappa contiene già una chiave, quindi il Double verrà aggiunto al valore della mappa esistente.

Sto lavorando con mappe mutabili nel mio codice specifico, ma sono interessato a soluzioni più generiche, se possibile.

Answer 1

Che ne dite di questo:

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) 

E funziona sia in 2.7.5 e 2.8.0.

Answer 2

Beh, si potrebbe fare:

mapList reduce (_ ++ _) 

fatta eccezione per il requisito speciale per la collisione.

Dal momento che si dispone di tale requisito speciale, forse la cosa migliore sarebbe fare qualcosa di simile (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 
} 

è quindi possibile aggiungere questo metodo per la classe di mappa attraverso il modello di Pimp My Library e utilizzare l'esempio originale invece di "++":

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

Mentre questo è stato scritto in 2.8, in modo da keysIterator diventa keys per 2.7, filterKeys potrebbe aver bisogno di essere scritta in termini di 01.239.e map, & diventa ** e così via, non dovrebbe essere troppo diverso.

Answer 3

Interessante, noodling in giro con questo un po ', ho ottenuto il seguente (il 2.7.5):

Maps

Generali:

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:_*) 
    } 
    } 

Ma l'uomo, che è orribile con la proiezione e costringendo e elenchi e quant'altro. Domanda separata: qual è il modo migliore per affrontarlo all'interno della piega?

per le mappe mutevoli, che è quello che avevo a che fare con nel mio codice, e con una soluzione meno generale, ho ottenuto questo:

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

Che sembra un po 'più pulito, ma funzionerà solo con mutevoli Mappe come è scritto. È interessante notare che prima ho provato quanto sopra (prima di porre la domanda) usando /: invece di foldLeft, ma stavo ottenendo errori di tipo. Ho pensato /: e foldLeft erano sostanzialmente equivalenti, ma il compilatore continuava a lamentarsi del fatto che avevo bisogno di tipi espliciti per (m, s). Cosa succede con quello?

Answer 4

ho letto questa domanda in fretta, quindi non sono sicuro se mi manca qualcosa (come si deve lavorare per 2.7.x o nessuna 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) 

È possibile modificare la definizione monoide per doppio e ottenere un altro modo per accumulare i valori, qui ottenere il massimo:

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

un oneliner helper-func, il cui utilizzo si legge quasi più pulita utilizzando 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) 

per la massima leggibilità avvolgerla in un tipo personalizzato implicita:

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

ho scritto un post su questo blog, check it out:

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

fondamentalmente utilizzando scalaz gruppo semi è possibile ottenere abbastanza facilmente

sarebbe simile a qualcosa:

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

Answer 7

Sono sorpresa di nessuno venire con questa soluzione ancora:

myListOfMaps.flatten.toMap 

fa esattamente quello che vi serve:

1. unisce le elenco per una singola mappa
2. Weeds qualsiasi duplicato chiavi

Esempio:

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 trasforma l'elenco delle mappe in una semplice lista di tuple, toMap trasforma la lista di tuple in una mappa con tutte le chiavi duplicate rimossi