left - Scala: cómo fusionar una colección de Mapas

foldleft spark

Question

Tengo una Lista de mapas [String, Double], y me gustaría fusionar sus contenidos en un solo mapa [String, Double]. ¿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 clave 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, 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

Bueno, podrías hacer:

mapList reduce (_ ++ _)

excepto por el requisito especial de colisión.

Ya que tienes ese requerimiento especial, quizás 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 agregar este método a la clase de mapa a través del patrón Pimp My Library y usarlo 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 esto estaba escrito en 2.8, entonces keysIterator convierte en keys para 2.7, filterKeys podría necesitar escribirse en términos de filter y map , & convierte en ** , y así sucesivamente, no debería ser demasiado diferente.

Answer 2

Escribí una publicación de blog sobre esto, compruébalo:

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

básicamente usando Scalaz semi group puedes lograr esto bastante fácil

se vería algo así como:

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

Answer 3

Estoy leyendo esta pregunta rápidamente, así que no estoy seguro de si me falta algo (como que tiene que funcionar para 2.7.xo no 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 para Double y obtener otra forma de acumular los valores, aquí obteniendo 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 4

Interesante, curioseando un poco con esto, obtuve lo siguiente (en 2.7.5):

Mapas generales:

   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 hombre, eso es horrible con la proyección y el forzar y la lista y todo eso. Pregunta separada: ¿cuál es una mejor manera de lidiar con eso dentro del redil?

Para mapas mutables, que es lo que estaba tratando en mi código, y con una solución menos general, obtuve 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 limpio, pero solo funcionará con Mapas mutables tal como está escrito. 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 5

Me sorprende que nadie haya llegado a esta solución todavía:

myListOfMaps.flatten.toMap

Hace exactamente lo que necesita:

1. Combina la lista en un solo mapa
2. Elimina cualquier clave duplicada

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 eliminadas

Answer 6

Que 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 como en 2.8.0.

Answer 7

un oneliner helper-func, cuyo uso se lee casi tan limpio como usar 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 una mejor legibilidad, envuélvalo en un tipo personalizado implícito:

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