Lists/Maps/Sets (Was Re: The story of E, part 2 (fwd))

[Ka-Ping Yee]

On Sun, 11 Oct 1998, Mark S. Miller wrote:
> So adopting this suggestion,
> 
> 	[v1, v2, v3] asSet
> 
> would be shorthand for
> 
> 	[v1 => null, v2 => null, v3 => null]

Works for me!

> I like this direction a lot.  One weird thing that I'm doing though is that
> I don't have a separate "set" data type.  Rather, most purposes should be
> served by the following 2x2 matrix of collection types:
> 
> 	              Table			List
> 	       ----+----------------------------
> 	Immutable  |  Mapping		Tuple
> 	           |
> 	Mutable    |  TableEditor		Vector
> 
> 
> (Btw, I'm *not* attached to these names.)

First, personal opinions about the individual names...

I have to say "TableEditor" sounds particularly awful to me;
not only is it clumsy and more than one word, it sounds more
like the thing editing the table rather than the table itself.
It sounds like the name of a UI component or something.

I am also leery of the use of "Vector" here.  I think "Vector"
ought to be left available for the kind of thing you can
multiply by a matrix and take cross products with.  For some
reason it also has the ring of a homogeneous collection to me,
which isn't the right meaning.

Let's see.  Python is the only other language i know of that
actually points out the distinction between mutable and
immutable collections, and its terminology is:

             |    mapping       sequence
  -----------+------------------------------
   immutable |     (none)         tuple
             |
    mutable  |   dictionary       list

Even though the only kind of built-in mapping in Python is
the dictionary, people still manage to be quite distinct in
their use of the two terms -- "dictionary" as the built-in
object type and "mapping" as the interface it supports
(which user-defined objects can provide by defining methods
named __getitem__, __setitem__, __len__, keys, values,
has_key, and items).

Similarly "tuple" and "list" are used to refer to the types
while "sequence" is used when either one is acceptable or
when talking about the interface (which provides the methods
__getitem__, __setitem__, and __len__).

I like these names because "sequence" highlights the
ordered-ness of tuples and lists that mappings don't have.

So, one possibility I would like to propose is the following,
filling in the empty spot in Python with "table" (the one
remaining available word from our collection so far):

             |    mapping       sequence
  -----------+------------------------------
   immutable |     table          tuple
             |
    mutable  |   dictionary       list

If "dictionary" seems too long, "dict" is also a reasonable
and common abbreviation.

A shorter name which Perl hackers use for "dictionary" is
"hash" (short for "hash table"), but i suspect that may become
too easily confused with a real hash value or hash function.

This sits okay with me, since a "table" sounds like more of
a permanent thing to me than a "dictionary".  The only possible
problem is that it may yield collisions when people want to
talk about "tables" in the UI layout sense or database sense
of the word.  (This may turn out to be as dangerous as the
collision with "vector".)  There is a certain expectation that
"tables" are things that have "rows" and "columns".


In that case, something like the following might be better:

             |    ********       sequence
  -----------+------------------------------
   immutable |    mapping         tuple
             |
    mutable  |   dictionary       list

... where the general term for ******** might be "relation"
or "association" or "associative array" or "lookup table" or
"set of pairs" etc.

Even if a relatively clumsy term gets chosen for ******** in
this taxonomy, it would still be preferable to all the previous
ones because the actual type names are simple and unconfusable.


Finally, another possibility is to consider "dictionary"
and "list" just a "mutable mapping" and "mutable tuple",
with default interpretations being immutable:

             |    mapping         tuple 
  -----------+------------------------------
   immutable |    mapping         tuple
             |
    mutable  |   dictionary       list

I'm not as hot on this one since one would have to guess
whether you meant only immutable mappings or both kinds
when you said "mapping", but it does mean fewer terms to
learn.


My favourite of these is the penultimate one.



Ping                                            Talk back to the Web!
<ping@lfw.org>                                       http://crit.org/