Growable arrays?

[David Kastrup <dak@gnu.org>]

Hi,

the main data structure of Lua is a "table", an associative array, and a
table t has a continguous numerically addressed part from 1..#t, with
all other indices going through a hashing mechanism.  One principal
distinguishing feature, like with a Scheme hashtable, is the ability to
grow on-demand.

Scheme/Guile vectors are fixed size.  Now I have a situation where I
have a basic type lattice with records stored in vectors, and this type
lattice may be extended dynamically (which typically happens at the
start of a whole file, for potentially multi-file runs).  Scheme does
not offer a suitable data structure for that.  It is a bit of a nuisance
that one can grow a hashtable efficiently and on-demand, but not so an
array.

Now it would be possible when the type lattice gets extended to store
the new entries in a hashtable and go from there.  Or put them into a
list, and reallocate on first access beyond the existing element.  That
seems rather contorted.  And since there is, if I remember, a project to
run Lua on top of Guile, having a fundamental and reasonably efficient
data structure corresponding to a Lua table, or at least the contiguous
part of a Lua table, would seem like a reasonably useful idea.  After
all, there already _is_ such a mechanism underlying hash tables so it
seems somewhat peculiar not to have it available for vectors as well.

Suggestions?

-- 
David Kastrup