How to "merge" / "map" two sparse maps into one?

Questions / Help
, , ,
1

What is Elixir way to “merge” / “map” two sparse maps onto one? I want to apply some function on both or single value from these maps. By “sparse” i mean that some keys are missing in another map. Like
a = %{1=>1, 2=>2, 4=>4}
b = %{0=>0, 1=>11, 2=>22, 5=>55}
looking for c=%{0=>f(0), 1=>f(1,11), …}

So far I have come with obtaining list of common keys and moving with it as index for both maps.

Closest built-in solution was Map.merge(map1, map2, fun), but it does not cover custom behavior when key is missing in one map.

Can solution be Stream’able?
Should I look for some non-default library?

2

Could you write a function to handle balls without a key and then use it in map.merge?

3

Can you merge the maps first and then apply the function?

Map.merge(a, b, fn _key, value1, value2 -> {value1, value2} end)
|> Map.new(fn
  {key, {value1, value2}} -> {key, f(value1, value2)}
  {key, value} -> {key, f(value)}
end)

It could get a bit cleaner if Elixir had an equivalent of Ruby’s transform_values, then it wouldn’t be necessary to repeat the key manually.

I’m guessing you want to use Stream because of t hef function? In that case I think you could first use Stream.map and then convert the result back into a map.

2 Likes
4

a = %{1=>1, 2=>2, 4=>4}
b = %{0=>0, 1=>11, 2=>22, 5=>55}
c = %{}
keys = Map.merge(a, b) |> Map.keys

for key ← keys do
case {Map.take(a, [key]), Map.take(b, [key])} do
{a_value, b_value} when map_size(b_value) == 0 → Map.put(c, key, f.(a_value))
{a_value, b_value} when map_size(a_value) == 0 → Map.put(c, key, f.(b_value))
{a_value, b_value} → Map.put(c, key, ff.(a_value, b_value))
end
end

Would something like this work?

1 Like
5

The function passed into merge only gets called if there is a conflict - both maps have the same key. That is why I thing this needs to be done in two steps. Merge first and resolve conflicts, then apply the function.

6 
Map.new(Map.keys(a) ++ Map.keys(b), fn key -> 
  case {Map.fetch(a, key), Map.fetch(b, key)} do
    {:error, {:ok, val}} -> {key, f(val)}
    {{:ok, val}, :error} -> {key, f(val)}
    {{:ok, val_a}, {:ok, val_b}} -> {key, f(val_a, val_b)}
    # {:error, :error} not possible
  end
end)
4 Likes
7 
map1 = %{a: 1, b: 2}
map2 = %{b: 1, c: 1}
fun = fn x, y -> x + y end

for {k1, v1} <- map1, {k2, v2} <- map2, reduce: %{} do
  acc ->
    if k1 == k2 do
      Map.put(acc, k1, fun.(v1, v2))
    else
      acc
      |> Map.put(k1, v1)
      |> Map.put(k2, v2)
    end
end

edit: after reviewing it myself this is not a great solution.

2 Likes
8

This one iterates map2 for each key/value pair in map1. That can become expensive rather quickly.

2 Likes
9

I feel this solution will have complexity of k1*k2, but in other solutions it’s something about (k1+k2) *2

10

Map.merge(a, b, fn _k, v1, v2 -> f(v1, v2) end)

edit: ah sorry, this doesn’t run the function if there’s no conflict. Knew it seemed too simple.

11

this is my current solution but written in a much nicer way =) thank you)

12

I think you’ll get (k1+k2) *2 only if you can make sure non of the map values is whatever you store in the map as an intermediate representation for “there were matching keys with two separate values”.

1 Like
13

I like how the case statement makes this approach very readable.

Just wanted to add that, depending on how often both maps contain overlapping keys, it could make sense to manually remove duplicated keys e.g. Map.keys(a) ++ Map.keys(b) |> Enum.uniq.

Map.new/2 already removes duplicated keys with the latest one prevailing. But that means it would unnecessarily run through the case statement twice whenever a key exists in both maps.

1 Like