[erlang-questions] map elements in defined order

[Richard Carlsson]

2017-10-28 17:41 GMT+02:00 Jesper Louis Andersen <
jesper.louis.andersen@REDACTED>:

> On Thu, Oct 26, 2017 at 9:13 PM Ulf Wiger <ulf@REDACTED> wrote:
>
>> But again, Jesper, just about everyone relies on the fact that maps
>> follow the general principle that there is a well-defined term comparison
>> order. Otherwise, maps would be highly unsuitable to use in keys, and
>> generally treacherous to use as a replacement for records. Following the
>> Principle of Least Surprise, it's a darned good thing that Erlang doesn't
>> randomize the key order in its maps.
>>
>
> I largely regard a total term order as a language mistake. The right
> solution, obviously, is to have several equalities, where the programmer
> can define what they mean by equality in a certain part of the program.
> Equality is way too important in programming for you to be left with a
> single one!
>

That may well be right, but doesn't change the fact that Erlang is pretty
much permeated with the idea of the total term order, and in many cases it
does make things very straightforward. So it would be a very bad thing if
some language change would break this property.


> That said, there is a well-defined order of maps currently, but it is not
> the logical one you might expect (which is by ordering the keys of the
> map). Rather the order is defined on
>
> * What the key hashes to
> * What the internal HAMT structure looks like right now
>

As we quoted from the reference manual, the < ordering on maps is actually
implementation independent and future proof (while still being a total
order). The sacrifice is that to compare two maps with <, their keys must
be mapped into canonical order (with integers before floats as discussed).
This is clearly more costly than just taking whatever order the current
underlying hash+HAMT produces, but worth it since it preserves those nice
properties.

On the other hand, the result from maps:to_list(M) is returned in the
current internal order, which is efficient but subject to change between
versions (albeit also well defined and total as you said), and there is
also no current comparison function available that you could give to
lists:sort(CompFunc, List) which would produce the key order used by < for
comparing maps - which is what Ulf needs for sext.

* Your "sext" library exists to plug yet another hole in the language,
> namely that binary_to_term have certain freedoms with certain data
> structures and this leads to situations where you cannot rely on the binary
> output for, e.g., cryptographic applications.
>

Not only that it wants to provide a stable mapping from terms to their
serialized forms, but also ensure that these binary representations sort in
the same order as the corresponding terms - a trickier problem.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20171028/a2e259d7/attachment.htm>