Scala：如何合并一组映射集合

Question

我有一个Map[String, Double]的列表，我想将它们的内容合并为一个Map[String, Double]。我应该如何以惯用方式实现这一点？我想我应该能够使用fold来实现。大概像这样：

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

此外，我希望以通用的方式处理关键字冲突。也就是说，如果我向地图添加已经存在的关键字，则应该能够指定一个函数，该函数返回一个Double值（在这种情况下），并使用该关键字的现有值以及我正在尝试添加的值作为参数。如果地图中不存在该关键字，则只需添加该关键字和其未更改的值。

在我的具体情况下，我想构建一个单一的Map [String，Double]，以便如果地图已经包含一个关键字，则将Double值添加到现有的地图值中。

在我的具体代码中，我正在使用可变映射，但如果可能的话，我对更通用的解决方案感兴趣。

- Jeff

Answer 1

好的，你可以这样做：

mapList reduce (_ ++ _)

除了对碰撞的特殊要求之外。

既然您确实有这样的特殊要求，也许最好的方法是像这样做（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
}

接着，您可以通过使用"Pimp My Library"模式将此方法添加到地图类中，并在原始示例中使用它，而不是"++"：

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

虽然这是在2.8中编写的，所以keysIterator对于2.7变为keys，filterKeys可能需要根据filter和map编写，&变为**等等，但这不应该有太大的区别。

- Daniel C. Sobral

---

使用现代的Scala：val k1 = m1.keysIterator.toSet - qerub

Answer 2

这个怎么样？

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)

它适用于2.7.5和2.8.0两个版本。

- Walter Chang

---

这正是我最初尝试做的方式。我没有想到要把for-comprehension放在那里 - 我仍然在适应像这样使用它们，但这很有道理。在这种情况下，我可以看到它与Python的列表推导式非常相似，而我对此更加熟悉。我也喜欢在调用a.+()时使用结果表达式。 - Jeff

非常感谢！我做了一点改动，不再接收 List[Map[A,B]]，而是改为 Seq[Map[A,B]]，这样更通用，可以避免在 ms 是 ArrayBuffer 的情况下调用 ms.toList。 - Alejandro Alcalde

Answer 3

我很惊讶还没有人想出这个解决方案：

myListOfMaps.flatten.toMap

完全满足您的需求：

1. 将列表合并为单个Map
2. 清除任何重复的键

例子：

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将地图列表转换为元组的平面列表，toMap将元组列表转换为删除所有重复键的映射

- Electric Coffee

---

这正是我所需要的，但它不会像OP要求的那样对重复键进行值求和。 - Don Branson

或者你可以使用flatMap。 - wbmrcb

@wbmrcb 在这种情况下，你会如何使用flatMap？使用flatMap时，扁平化发生在映射之后，但这里是相反的。那么它该如何工作呢？ - vaer-k

@electric-Coffee 如果每个Map包含多个键值对，那么这将仅获取最后一个Map。 - Suvro Choudhury

Answer 4

从 Scala 2.13 开始，另一种解决重复键处理问题且仅基于标准库的方法是在应用新的 groupMapReduce 操作符之前将 Map 合并为序列 (flatten)，该操作符（顾名思义）相当于对分组后的值进行映射和归约操作：groupBy。

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)

这个方法:

• flatten将地图作为元组序列(List(("hello", 1.1), ("world", 2.2), ("goodbye", 3.3), ("hello", 4.4)))连接在一起，保留所有键/值(即使是重复的键)

• group根据它们的第一个元组部分(_._1)对元素进行分组(groupMapReduce 的 group 部分)

• map将分组的值映射到它们的第二个元组部分(_._2) (groupMapReduce 的 map 部分)

• reduce通过取它们的和(但可以是任何reduce: (T, T) => T函数)(groupMapReduce 的 reduce 部分)来减少映射的分组值(_+_)

---

groupMapReduce 步骤可以看作是单遍版本的等价形式：

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

- Xavier Guihot

Answer 5

有趣的是，我稍微探索了一下，得出了以下结果（在2.7.5上）：

常规地图：

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

但是，使用projection、forcing、toList等操作太过丑陋。另外一个问题：有没有更好的方法在fold中处理这个问题？

对于可变映射（mutable Maps），这也是我代码中处理的对象，并且采用了不那么通用的解决方案，我得到了以下结果：

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

这看起来更加简洁，但只适用于可变 Map。有趣的是，在我提问之前，我首先尝试了上述方法（使用 /: 而不是 foldLeft），但是我一直在收到类型错误。我认为 /: 和 foldLeft 基本等价，但编译器一直在抱怨需要为 (m, s) 显式指定类型。这是怎么回事？

- Jeff

---

дҪ дёҚйңҖиҰҒеңЁиҝҷйҮҢдҪҝз”ЁforceпјҢеӣ дёәtoListжҳҜдёҘж јзҡ„гҖӮ - Daniel C. Sobral

关于 foldLeft 和 /:，你应该意识到它们之间的对象和第一个参数是交换的吧？表达式 x foldLeft y 等同于 y /: x。除此之外，还有一堆语法问题。基本上，你必须写成 (y /: x) (折叠表达式)，而 foldLeft 可以写成 x.foldLeft(y)(折叠表达式)。 - Daniel C. Sobral

是的，我知道以 : 结尾的方法可以交换对象和参数。这就是我在问题中编写示例的方式。不过，我忘记将 y /: x 放在括号中了，我想那可能是个问题。谢谢！ - Jeff

Answer 6

我快速阅读了这个问题，所以不确定是否漏掉了什么（例如它必须适用于2.7.x或无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)

您可以更改Double的幺半群定义，从而获得另一种累加值的方式，在此处获取最大值：

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)

- huynhjl

---

+1，虽然我会写ms.suml，这样更简洁，并且不会在空列表上抛出运行时异常。 - Travis Brown

@TravisBrown，scalaz 中有许多方便的函数；不过 suml 可能仅适用于 scalaz 7？我只在 6.x 版本中看到了 sumr。 - huynhjl

Answer 7

我写了一篇关于这个的博客文章，请查看：

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

基本上使用Scalaz半群，你可以轻松地实现这个。

看起来会像这样：

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

- Nimrod007

---

你实际上可以使用 listOfMaps.suml；它应该做相同的事情。从我的理解来看，它的意思是 sumLeft，它基本上运行了 reduceLeft(_ |+| _)。 - JBarber

Answer 8

def mergeMap[A, B](ms: List[Map[A, B]])(f: (B, B) => B): Map[A, B] = {
  ms.flatten.foldLeft(Map[A, B]()) { case (acc, (k, v)) =>
    acc + (if (acc.contains(k)) k -> f(acc(k), v) else (k, v))
  }
}

- Taoist

---

感谢您对Stack Overflow社区做出贡献的兴趣。这个问题已经有了相当多的答案，其中一个答案已经得到社区的广泛验证。您确定您的方法之前没有被提到过吗？如果是这样的话，能否解释一下您的方法有何不同，什么情况下您的方法可能更好，并且/或者为什么您认为之前的答案不够满意。您能否友好地编辑您的答案并提供解释？ - undefined

Answer 9

一个单行辅助函数，使用方式几乎与使用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)

为了最大限度地提高可读性，请将其包装在隐式自定义类型中：

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

- bernstein