Scala: come unire una collezione di mappe

Question

Ho una lista di Map [String, Double], e mi piacerebbe di fondere le loro contenuto in una singola mappa [String, Double]. Come devo fare questo in modo idiomatica? Immagino che dovrei essere in grado di fare questo con una piega. Qualcosa di simile:

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

Inoltre, mi piacerebbe gestire collisioni chiave in modo generico. Cioè, se posso aggiungere una chiave per la mappa che esiste già, dovrei essere in grado di specificare una funzione che restituisce una doppia (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, quindi basta aggiungerlo e il suo valore inalterato.

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

Sto lavorando con le mappe mutabili nel mio codice specifico, ma sono interessati a soluzioni più generici, 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

Bene, si potrebbe fare:

mapList reduce (_ ++ _)

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

È possibile aggiungere questo metodo per la classe di mappa attraverso il modello di Pimp My Library, e usarlo nell'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 _)

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

Answer 3

Sono sorpresa di nessuno venire con ancora questa soluzione:

myListOfMaps.flatten.toMap

fa esattamente quello che vi serve:

1. Unisce l'elenco per una singola mappa
2. erbacce duplicati delle 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

Answer 4

I leggendo 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 Double 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

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

Mappe 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 listaA e quant'altro. domanda separata:? che cosa è un modo migliore per affrontare questo entro la piega

Per 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 funziona solo con mappe delle mutevoli come è scritto. È interessante notare che, in primo luogo ho provato quanto sopra (prima ho fatto la domanda) utilizzando /: al posto di foldLeft, ma mi è stato sempre errori di tipo. Ho pensato /: e foldLeft erano sostanzialmente equivalente, ma il compilatore continuava a lamentarsi che avevo bisogno di tipi espliciti (m, s). Cosa c'è in questo?

Answer 6

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

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

fondamentalmente utilizzando scalaz gruppo semi si può raggiungere questo abbastanza facilmente

sarebbe simile:

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

Answer 7

Scala 2.13 di partenza, un'altra soluzione che gestisce chiavi duplicate ed è solo sulla base della libreria standard consiste nel fondere le Maps come sequenze (flatten) prima di applicare la nuova groupMapReduce operatore che (come suggerisce il nome) è un equivalente di un groupBy seguita da una mappatura e una fase di ridurre valori raggruppati:

List(Map("hello" -> 1.1, "world" -> 2.2), Map("goodbye" -> 3.3, "hello" -> 4.4))
  .flatten
  .groupMapReduce(_._1)(_._2)(_ + _)
// Map("world" -> 2.2, "goodbye" -> 3.3, "hello" -> 5.5)

Questa:

• flattens (concatena) le mappe come una sequenza di tuple (List(("hello", 1.1), ("world", 2.2), ("goodbye", 3.3), ("hello", 4.4))), che mantiene tutti i principali valori / (anche chiavi duplicate)

• groups elementi in base alla loro prima parte tupla (_._1) (parte del gruppo gruppo MapReduce)

• maps valori raggruppati per la loro seconda parte tuple (_._2) (mappa parte del gruppo Mappa Riduzione)

• reduces mappati valori raggruppati (_+_) prendendo loro somma (ma può essere qualsiasi funzione reduce: (T, T) => T) (ridurre parte groupMap Ridurre )

---

Il passo groupMapReduce può essere visto come un -pass una versione equivalente di:

list.groupBy(_._1).mapValues(_.map(_._2).reduce(_ + _))

Answer 8

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