Merging Scala Maps

Question

I want to merge large maps in Scala

This a question that has been asked before, but none of the answers seemed efficient. All of the idiomatic solutions seemed to have quadratic cost, and allocate lots of memory

Scala: Merge maps by key Improvements for a Map merge function

Here's the basic problem:

Given

val x: Map[A,B] = ... 
val y: Map[A,C] = ...
def f(Option[B],Option[C]): D = ...

Generate

val z: Map[A,D]

So I want to merge x and y and produce a map z with a union of all the keys. The values are calculated combining the values of x and y.

Is there an idiomatic way to do this that is both functional and efficient for very large maps? Has something been added to Scala 10 or 11 (or coming in 12)?

Thank you Peter

The solutions from the links have effectively linear complexity. You merge both keysets. Then you iterate over the combined keyset, lookup the values from both sets (which is effectivly constant time) and apply your function `f`. — Kigyo, Jul 30 '14 at 03:58
If you don't want to pay the cost of merging maps up front you can create a custom map that hides the first 2 maps in it. You'll need to implement `Map` interface. — yǝsʞǝla, Jul 30 '14 at 06:20

score 0 · Answer 1 · answered Jul 30 '14 at 12:42

Excellent suggestion Aleksey!

class MergeMap[A,B,C,D](x: Map[A,B], y: Map[A,C], f: (Option[B],Option[C]) => Option[D]) {
def get(key: A) = f(x.get(key),y.get(key))
}

This seems to be a common need, so perhaps the Scala gods might consider adding this to Map

def merge[C,D]( other: Map[A,C], f: (Option[B],Option[C]) => Option[D]) = MergeMap[A,B,C,D](this,other,f)

score 0 · Answer 2 · answered Aug 02 '14 at 04:46

To avoid the cost of merging maps I was thinking of something like that:

class LazyMap[A, B, C, D](x: Map[A, B], y: Map[A, C],
f: (Option[B], Option[C]) => Option[D]) extends Map[A, D] {

  def get(key: A): Option[D] =
    f(x get key, None) orElse f(None, y get key)

  def iterator: Iterator[(A, D)] = ???

  def +[B1 >: D](kv: (A, B1)): Map[A, B1] = ???
    // perhaps?: new LazyMap(x + kv, y, f)

  def -(key: A): Map[A, D] =
    new LazyMap(x - key, y - key, f)
}

This obviously needs some work. It implements Map trait and thus can be used as a regular map afterwards.

Merging Scala Maps

2 Answers2