Scala: cómo combinar una colección de Mapas

Question

Tengo una Lista de Mapa [Cadena, Doble], y me gustaría fusionar sus contenidos en un único Mapa [Cadena, Doble]. ¿Cómo debería hacer esto de una manera idiomática? Me imagino que debería poder hacer esto con un doblez. Algo como:

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

Además, me gustaría manejar las colisiones de teclas de forma genérica. Es decir, si agrego una clave al mapa que ya existe, debería poder especificar una función que devuelva un doble (en este caso) y tome el valor existente para esa clave, más el valor que intento agregar . Si la clave aún no existe en el mapa, simplemente agréguela y su valor sin modificaciones.

En mi caso específico me gustaría construir un solo Mapa [Cadena, Doble] de modo que si el mapa ya contiene una clave, entonces el Doble se agregará al valor del mapa existente.

Estoy trabajando con mapas mutables en mi código específico, pero estoy interesado en soluciones más genéricas, si es posible.

Answer 1

¿Qué tal este:

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) 

Y funciona tanto en 2.7.5 y 2.8.0.

Answer 2

Bueno, usted podría hacer:

mapList reduce (_ ++ _) 

excepto por el requisito especial para la colisión.

Dado que usted tiene ese requisito especial, tal vez lo mejor sería hacer algo como esto (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 
} 

A continuación, puede añadir este método a la clase mapa a través del patrón de Pimp My Library, y utilizarlo en el ejemplo original en lugar 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 _) 

Mientras que esto fue escrito en 2.8, por lo que se convierte en keysIteratorkeys de 2,7, filterKeys que tenga que ser escrito en términos de 01.239.y map, & se convierte en **, y así sucesivamente, no debe ser muy diferente.

Answer 3

Interesante, noodling con esto un poco, tengo los siguientes (en 2.7.5):

generales Maps:

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

Pero el hombre, que es horrible con la proyección y forzando y toList y otras cosas. Pregunta separada: ¿cuál es una mejor manera de lidiar con eso dentro del redil?

Por Mapas mutables, que es lo que estaba tratando con en mi código, y con una solución menos general, tengo esto:

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

Eso parece un poco más limpia, pero sólo funcionará con mutable Mapas tal como están escritos. Curiosamente, primero probé lo anterior (antes de hacer la pregunta) usando /: en vez de foldLeft, pero recibí errores de tipo. Pensé /: y foldLeft eran básicamente equivalentes, pero el compilador no dejaba de quejarse de que necesitaba tipos explícitos para (m, s). ¿Que pasa con eso?

Answer 4

que leer esta pregunta rápidamente así que no estoy seguro de si me falta algo (como tiene que trabajar para 2.7.x o ninguna 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) 

Puede cambiar la definición de monoid doble y obtener otra forma de acumular los valores, aquí conseguir el máximo:

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, cuyo uso se lee casi tan limpio como el uso de 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) 

para facilitar la lectura final se envuelve en un tipo personalizado implícita:

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

escribí un post sobre esto, Hay que ver:

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

básicamente utilizando grupo semi scalaz se puede lograr esto bastante fácil

se vería algo así como:

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

Answer 7

me sorprende nadie llegar a esta solución aún:

myListOfMaps.flatten.toMap 

hace exactamente lo que necesita:

1. fusiona la lista a un solo mapa
2. Las malas hierbas a cabo cualquier duplicado teclas

Ejemplo:

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 convierte la lista de mapas en una lista plana de tuplas, toMap convierte la lista de tuplas en un mapa con todas las claves duplicadas eliminado