Scala: como mesclar uma coleção de mapas

Question

Eu tenho uma lista de Mapa [String, dupla], e eu gostaria de mesclar seu conteúdo em um único Mapa [String, dupla]. Como devo fazer isso de uma forma idiomática? Imagino que eu deveria ser capaz de fazer isso com uma dobra. Algo como:

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

Além disso, eu gostaria de lidar com colisões chave de uma forma genérica. Isto é, se eu adicionar uma chave para o mapa que já existe, eu deveria ser capaz de especificar uma função que retorna um duplo (neste caso) e leva o valor existente para essa chave, mais o valor que eu estou tentando adicionar . Se a chave ainda não existe no mapa, em seguida, basta adicioná-lo e seu valor inalterado.

No meu caso específico eu gostaria de construir um único Mapa [String, dupla] de tal forma que se o mapa já contém uma chave, em seguida, a dupla será adicionado ao valor do mapa existente.

Eu estou trabalhando com mapas mutáveis ??no meu código específico, mas estou interessado em soluções mais genéricas, se possível.

Answer 1

Como sobre 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)

E funciona tanto em 2.7.5 e 2.8.0.

Answer 2

Bem, você poderia fazer:

mapList reduce (_ ++ _)

exceto para a exigência especial para a colisão.

Uma vez que você tem essa exigência especial, talvez o melhor seria fazer algo assim (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
}

Você pode então adicionar este método para o mapa de classe através do padrão Pimp My Library, e usá-lo no exemplo original em vez 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 _)

Enquanto isto foi escrito em 2,8, então keysIterator se torna keys para 2,7, filterKeys pode ter de ser escrito em termos de filter e map, & se torna **, e assim por diante, ele não deve ser muito diferente.

Answer 3

Estou surpreso que ninguém de vir para cima com esta solução ainda:

myListOfMaps.flatten.toMap

faz exatamente o que você precisa:

1. Mescla a lista para um único Map
2. elimina quaisquer chaves duplicadas

Exemplo:

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 transforma a lista de mapas em uma lista simples de tuplas, toMap transforma a lista de tuplas em um mapa com todas as chaves duplicadas removidas

Answer 4

Eu ler esta pergunta rapidamente, então eu não tenho certeza se eu estou faltando alguma coisa (como ele tem que trabalhar para 2.7.x ou nenhuma 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)

Você pode alterar a definição monoid para Double e obter uma outra maneira de acumular os valores, aqui recebendo o 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

Interessante, noodling ao redor com esta um pouco, eu tenho o seguinte (no 2.7.5):

Mapas gerais:

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

Mas o homem, que é hediondo com a projeção e forçando e ToList e outros enfeites. questão em separado: qual é a melhor maneira de lidar com isso dentro do rebanho

Para Mapas mutáveis, que é o que eu estava lidando com no meu código, e com uma solução menos geral, eu tenho o seguinte:

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

Isso parece um pouco mais limpo, mas só funcionará com Mapas mutáveis ??como está escrito. Curiosamente, primeiro eu tentei o acima (antes eu fiz a pergunta) usando /: em vez de foldLeft, mas eu estava recebendo erros de tipo. Pensei /: e foldLeft eram basicamente equivalente, mas o compilador vivia reclamando que eu precisava de tipos explícitas para (m, s). O que há com isso?

Answer 6

Eu escrevi um post sobre isso, confira:

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

usando basicamente grupo semi scalaz você pode conseguir isso muito facilmente

seria algo parecido com:

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

Answer 7

Iniciando Scala 2.13, outra solução que alças duplicar chaves e só é baseado na biblioteca padrão consiste na fusão das Maps como seqüências (flatten) antes de aplicar o novo groupMapReduce operador que (como o nome sugere) é um equivalente de uma groupBy seguido por um mapeamento e um passo de reduzir a valores agrupados:

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)

Este:

• flattens (concatena) os mapas como uma seqüência de tuplas (List(("hello", 1.1), ("world", 2.2), ("goodbye", 3.3), ("hello", 4.4))), que mantém todas as chaves / valores (até mesmo chaves duplicadas)

• groups elementos com base na sua primeira parte tuplo (_._1) (parte de grupo grupo MapReduce)

• maps valores agrupados para a sua segunda parte tupla (_._2) (mapa parte do grupo Map Reduzir)

valores

• reduces mapeadas agrupadas (_+_) tomando sua soma (mas pode ser qualquer função reduce: (T, T) => T) (reduzir parte de groupMap Reduzir )

---

O passo groupMapReduce pode ser visto como um versão de uma passagem equivalente a:

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

Answer 8

a oneliner helper-func, cujo uso lê quase tão limpa como a utilização 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 embrulhar legibilidade final-lo em um 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(_)(_ + _) }