[erlang-questions] Wanted additions to the maps module?

[Richard A. O'Keefe]

On 10/05/16 12:36 AM, Graham Hay wrote:
>
>     "next" implies a "previous" and that implies an ordering -- and that
>     ordering seems like it should mean something (or, in other words, be
>     consistent). Or... what am I missing?
>
>
> I think the point is that you shouldn't rely on the order, as it as an
> implementation detail and subject to change
No, it's much worse than that.  It's not that the order may change
from one release to the next.  THAT would not be such a problem.
The problem is that
  - two EQUAL tables may have DIFFERENT orders
  - my possibly incorrect understanding is that a map may change
    its representation, so that a SINGLE table may have different
    orders at different times
  - for efficiency, a map representation should be allowed to change
    in response to pure queries, but that would mean that the
    order could change DURING A TRAVERSAL.

Background: for years I've been working on a Smalltalk->C compiler
and its supporting library.  The library naturally includes hash tables.
And yes,
  - two equal Dictionaries generally DO have different orders
  - adding associations to a Dictionary and then removing them
    WILL in general result in the order changing even though it's
    the same object with the same contents
  - I wanted to use the move-to-front heuristic to improve lookup
    times, but it DID break traversal (associations could be lost or
    visited twice) so I had to give up on that, because while
    Smalltalk forbids *changing* a collection while iterating over it,
    it doesn't forbid *examining* it.

When we speak of "THE order", our mouths are deceiving us.
There is no "THE order", and that is the heart of the problem.

Smalltalk can get away with it, because Smalltalk is an Object-Oriented
language, not a functional one, and the compiler is entitled to make
very few assumptions, not even that an object won't change class.
But Erlang is (at least within a process) a functional language, and
something like maps:first(Map) is supposed to be a *function* of the
*value* of its argument.

If Map1 == Map2, then maps:first(Map1) must == maps:first(Map2)
otherwise we are adrift without a compass.

One of the goals underlying the frames proposal was that none of these
problems should exist.

By the way, it's easy enough to impose an order.
What you do is to exploit the fact that a representation may change
without the value appearing to change.  If first/next (or last/previous)
are used, at that point you switch from some sort of hashed structure
to some sort of tree, such as a splay tree or a red-black tree. Iterating
over a splay tree (once formed) takes linear time, so that would probably
be the way to go.

I couldn't do that in Smalltalk, because there is no total order on 
Smalltalk
objects that could be used, but there is one on Erlang terms.
>
> JS object properties are similar:

Yes, but JavaScript is frankly insane and while it uses functions a lot,
it's basically an imperative language, much closer to Smalltalk than to
Erlang, although not in a terribly useful way.  JavaScript is the
ultimate test of Agile programming: it's what you get from doing a
coding sprint instead of design.