[erlang-questions] map elements in defined order

Richard Carlsson carlsson.richard@REDACTED
Sat Oct 28 22:46:10 CEST 2017


2017-10-27 23:58 GMT+02:00 Fred Hebert <mononcqc@REDACTED>:

> On 10/27, Richard Carlsson wrote:
>
>> One way to
>> avoid this situation would be to say that you can't have two keys that
>> compare equal with == in the same map, just as for an orddict.
>>
>
> This would, unfortunately, break pattern matching:
>
> M = #{1 => 1},
> case M of
>    #{1.0 := _} -> % it is safe to add 1.0 if we match
>        M#{1.0 := 2}; % does this crush a value and change the key?
>    _ ->
>        other
> end.
>
> The fourth line here is problematic. Either (1) maps have a special
> magical pattern matching case where 1.0 and 1 compare equal (which happens
> nowhere else) and decide whether to replace the key or keep it the same, or
> (2) you keep current pattern matching semantics and you can't use existing
> pattern matching to enforce the constraints above.
>

Yes, you can't change it now that it's in existing code; it would have had
to be done when maps were new. But, having slept on the issue, I now think
that the current state of things is fine. The keys must be seen as existing
on a different level than the values they map to, more part of the
structure of the thing, much like the arity of a tuple. As in your example,
they are used in matching, where exact equality is the expected behaviour.
It is still bothersome for people like Ulf who want to easily generate a
list of the key-value pairs in the order that '<' would consider them - but
that is a fairly unusual use case and can be fixed by making separate
ordering functions accessible (either as a new :< operator or as a regular
BIF).

One thing can be noted: there is no strict need as far as I can see for the
key order to be related to any other particular order like < or :< (apart
from convenience), as long as there is always a canonical key order
independent of underlying implementation. One could hypothetically use
lexicographical order on the stringified keys, and it would work just as
well, since the ordering is really only used for deciding which maps are at
all comparable. It does decide the ordering of maps of the same size and
with different keys (in which case the values are never examined), but if
that by necessity must be different from the arithmetic order anyway, it
doesn't matter much which order it is. The main thing is that it's cheap to
compute, and the :< order is as cheap as any.

But until :< is actually available as an operator or function, poor Ulf
will need to emulate it using 0/1/2-tagging like I showed (recursively, as
he pointed out). Or write a NIF for performance.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20171028/deb8cf49/attachment.htm>


More information about the erlang-questions mailing list