[erlang-questions] Wanted additions to the maps module?
Richard A. O'Keefe
Tue May 10 00:31:42 CEST 2016
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.
- 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
objects that could be used, but there is one on Erlang terms.
> JS object properties are similar:
it's basically an imperative language, much closer to Smalltalk than to
ultimate test of Agile programming: it's what you get from doing a
coding sprint instead of design.
More information about the erlang-questions