Semantics of lists keymerge

Questions / Help
1

I seldomly use lists:keymerge, but found it in code of some other people and misunderstand what it is doing.

From the documentation I read that if there are duplicate entries, one is removed… but it is not stricktly spoken saying so.

Erlang/OTP 27 [erts-15.1.2] [source] [64-bit] [smp:12:12] [ds:12:12:10] [async-threads:1] [jit]

Eshell V15.1.2 (press Ctrl+G to abort, type help(). for help)
1> lists:keymerge(1, [{a,[1]}], [{a,[2]}]).
[{a,[1]},{a,[2]}]
2> lists:keymerge(1, [{a,[1]}], [{a,[1]}]).
[{a,[1]},{a,[1]}]

The documentation:

The merge is performed on the N th element of each tuple. Both TupleList1 and TupleList2 must be key-sorted before evaluating this function. When two tuples compare equal, the tuple from TupleList1 is picked before the tuple from TupleList2 .

Why is it important to state that it takes the element from TupleList1 if there is no difference which one to pick?

I had expected with the text above:

1> lists:keymerge(1, [{a,[1]}], [{a,[2]}]).
[{a,[1]}]
1 Like
2

It looks like this is the expected behavior. The lists:keymerge/3 function performs a merge, not a deduplication (usort).

The behavior of lists:keymerge/3 can be a bit confusing at first, especially when dealing with duplicate keys. Let me clarify how it works…

This function merges two lists that are already sorted by a key. It does not deduplicate entries - it simply combines the lists, and when two keys are equal, it keeps both values.

Here’s what’s important to know:

  1. If the keys are equal, the tuple from TupleList1 will appear before the tuple from TupleList2.
  2. It does not remove duplicates. If both lists have the same tuple (key and value), both will remain in the merged result.
2 Likes
3

Thanks for that explanation.

This clarifies it for me. Since one starts with sorted lists, one may falsely believe that the result is also sorted. The text in the documentation tries to explain that that is not guaranteed. The example that clarifies this is:

Erlang/OTP 27 [erts-15.1.2] [source] [64-bit] [smp:12:12] [ds:12:12:10] [async-threads:1] [jit]

Eshell V15.1.2 (press Ctrl+G to abort, type help(). for help)
1> lists:keymerge(1, [{a,3}], [{a, 1}, {a,2}]).
[{a,3},{a,1},{a,2}]
2 Likes