[erlang-questions] map elements in defined order

[Jesper Louis Andersen]

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 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

It is a total order even! So you can use maps as keys in a balanced search
tree for instance.

However, your point does seem to touch on a couple of important things that
should be considered for future inclusion:

* We may want to have an "ordered map" in the language. These are
self-balancing binary trees. They are more costly in lookup time and they
take up more memory space, but they have the "natural ordering" of keys
which means they are well-defined in their traversal.

* 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.

In short, one has to weigh different implementation details when building
data structures. If you want to have it all, your efficiency eventually has
to give.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20171028/5e05e8ae/attachment.htm>