2

Possible Duplicate:
Best way to merge two maps and sum the values of same key?

I have a bunch of maps of the type Map[String, Int]. I would like to be able to merge them taking the sum of the values when the keys correspond. For instance, the standard ++ method on maps gives

Map("a" -> 1, "b" -> 2) ++ Map("a" -> 3, "c" -> 5)
// Map[String,Int] = Map(a -> 3, b -> 2, c -> 5)

I would like to define an operation that as a result would give

Map("a" -> 1, "b" -> 2) ?? Map("a" -> 3, "c" -> 5)
// Map[String,Int] = Map(a -> 4, b -> 2, c -> 5)

In fancy wording, Map[A, B] always has a natural structure of monoid, but there is a different one when B is itself a monoid.

Now, it would not be difficult to write, say, a recursive implementation for LinkedHashMap, but I think there must be some trivial and more general way to write this, possibly using scalaz. Any ideas?

Community
  • 1
  • 1
Andrea
  • 20,253
  • 23
  • 114
  • 183
  • There are a number of ways to do this with Scalaz, but it really is a shame that we don't just have a `unionWith` method on `Map` in the Collections API. – Travis Brown Sep 19 '12 at 14:18

2 Answers2

7

Scalaz has a monoid instance for Map[A,B] if B is also a monoid.

> Map("a" -> 1, "b" -> 2) |+| Map("a" -> 3, "c" -> 5)
  Map("a" -> 4, "c" -> 5, "b" -> 2)
Clément D.
  • 284
  • 2
  • 4
0

It looks like you are actually trying to use a Map as a Multiset. For multisets, the operation you are describing is just multiset sum s1 ⊎ s2.

Unfortunately, there is no multiset in the Scala Collections Framework, but there are some for Java.

For a hypothetical Multiset in Scala:

Multiset("a", "b", "b") ++ Multiset("a", "a", "a", "c", "c", "c", "c", "c")
// Multiset[String] = Multiset("a" -> 4, "b" -> 2, "c" -> 5)
Jörg W Mittag
  • 363,080
  • 75
  • 446
  • 653
  • I never fully understood the choice of terminology for Multiset. They form a histogram of their constituents so why not call them Histogram? – Rick-777 Sep 20 '12 at 08:50