Re: Growable arrays?

[Daniel Hartwig]

On 11 June 2012 20:20, David Kastrup <address@hidden> wrote:
>> P.S.: I still need to look at vlists.  They might already address this
>>       issue, though I can't use them in Guile 1.8.
>
> No, the "immutable" angle would make them unsuitable again.

Note that vlists are only immutable in the sense that you can not
modify the value of a slot already allocated.  You can modify the
object that a slot points to and you can extend a vlist as much as you
like.

Multiple vlists can even share tails.

For example, this session modifies the object in slot 0 of the vlist:

> (use-modules (ice-9 vlist))
> (list->vlist '((a b) (c d) (e f)))
$1 = #<vlist ((a b) (c d) (e f))>
> (vlist-ref $1 0)
$2 = (a b)
> (set-cdr! $2 '(boo))
> $1
$3 = #<vlist ((a boo) (c d) (e f))>

> 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).

>From this I gather that your use case only appends to the lattice, if
so, vlist is suitable for that task.

> Cough, cough.  Standard vectors are not growable.  Which is the original
> problem of this thread, never mind Lua.

True, but a growable vector is a tiny step away from the standard vector.

> hashtables have additional indirection
> through hash buckets and coalescing lists

This is fairly standard for a hash table.  I would be quite surprised
if the hash table part of a Lua table did not also use buckets.

> Except that this one isn't.

Why not?

You take a vector and a hash table, store your values in them, and
grow either as needed.  This is not a complicated type.