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

[Richard A. O'Keefe]

On 10/05/16 1:43 AM, Artie Gold wrote:
> Old naïvist here...
>
> Why should a defined order be necessary in an immutable context?
To produce consistent results.

You may be confusing (abstract) value immutability with
(concrete) representation immutability.  They are not the
same thing.

Example 1: a simple hash table implemented as an array
of linked lists, using move-to-front to search the buckets.
Looking things up doesn't change the *value*, but the
*representation* adjusts itself in the expectation that
something you've looked up will be looked up again soon.

Example 2: a splay tree.  When you look a key up, the
tree adjusts itself to put that key near the root.  One
consequence of the way this is done is that you can do
   k := min-key(t)
   while k is not missing do
     use k
     k := next-larger-key(t, k)
in O(n) time instead of O(n.log n).  Here again, the
*value* does not change, but the *representation* adjusts.

Example 3: a hybrid data structure which uses hashing
for point queries but some sort of search tree for
range queries (like min-key and next-larger-key) and
switches from one representation to another based on
what you've been doing lately.  (The Burroughs B6700
MCP used this sort of thing in its file system interface.
There were access procedures optimised for sequential
reading and access procedures optimised for random
access and instead of getting the programmer to guess,
it switched at run time.)

Alternatively, you may be assuming that two equal
abstract values will have the same concrete representation.
Sadly, this is far from true.

On the gripping hand, you may be assuming that the
order in which a container is traversed, while not
revealed to people, would of course be defined by the
contents of the container, and not by accidents of its
history.  In that case, we agree that it *should* be,
but sadly, in practice it is not.

This was always Prolog's worst feature, that it didn't
really support abstract data types.  Given, for example,
an implementation of AVL trees, two AVL trees with
identically the same keys and corresponding values might
not (no, usually DID not) have the same representation,
and so were not equal.  That was pretty bad for a
programming language where "=" was so fundamental.

I can sort of cope with library modules that make my life
hard, but I expect better of basic data structures.