[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Growable arrays?

From: David Kastrup
Subject: Growable arrays?
Date: Sat, 09 Jun 2012 14:32:28 +0200
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/24.1.50 (gnu/linux)


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

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.


David Kastrup

reply via email to

[Prev in Thread] Current Thread [Next in Thread]