Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!iuvax!uxc!uxc.cso.uiuc.edu!m.cs.uiuc.edu!robison
From: robison@m.cs.uiuc.edu
Newsgroups: comp.lang.misc
Subject: Re: flexible arrays
Message-ID: <5200039@m.cs.uiuc.edu>
Date: 1 Feb 89 04:52:00 GMT
References: <21@euteal.UUCP>
Lines: 28
Nf-ID: #R:euteal.UUCP:21:m.cs.uiuc.edu:5200039:000:1266
Nf-From: m.cs.uiuc.edu!robison    Jan 31 22:52:00 1989


>My main point is: I REALLY HATE LISTS.

Anyone prejudiced towards arrays and lists should look at
the Smalltalk language and its `collection' class.  The internal
representation (array vs. links) should be separate from what
it's representing (set vs. indexed tuple vs. linear sequence).
The programmer should first decide what operations are necessary
and then pick an implementation.  Smalltalk provides quite a
few kinds of collections, such as : sets, multisets, indexed collections,
linear lists, and hash tables to name a few.  Corresponding operations
in different kinds of collections have the same name, 
so the implementation can be changed easily.

> Instead we should use flexible arrays or sparse arrays.

A language should not provide any arrays or lists, except
that provided by common hardware.  All other data-structures
should be defined by libraries.  Why limit the user to
two particular representations of a collection, when there 
are lots out there, each with its own efficiency niche.  
E.g. balanced trees, 2-3 trees, red-black trees, tries, 
arrays, hash tables, B-trees, linked-lists, and bit-vectors.

To summarize, languages should let the user make the list vs. array
decision last, and not limit the choice to just those two.

- Arch