[racket] Should immutable lists be implemented as over-allocated arrays?

What do you do when two lists share a tail?

Using your example:
(define l (list 1 2 3 4 5))   [___gap____12345]
(cons 0 l)                    [___gap___012345]
(cons 6 l)                    ?

With cons cells, sharing a tail is trivial, but with your scheme, it
would require copying. (Unless you want to have a mixed
representation, when you can start with cons cells and then point into
one of these arrays, but that can get complicated.)

These extensible arrays are an interesting data structure, and would
make a great PLaneT package, but they're quite different from Racket's
lists.

Vincent


At Tue, 2 Aug 2011 14:54:20 -0400,
Greg Hendershott wrote:
> 
> Should immutable lists be implemented as over-allocated arrays,
> instead of as linked lists?
> 
> Seems like immutable lists don't need the pointer-like, linked-list
> semantics of mutable lists.
> 
> Pros:
> 1. Contiguous items means better locality of reference (for various
> levels of cache, from CPU on up to OS virtual memory).
> 2. Requires less memory. (See also 1. The happy case of speed and
> space, not speed vs. space.)
> 3. Nearly all operations will be as fast (e.g. `car', `cdr') or faster
> (e.g. `length', `list-ref').
> 
> Cons: (pun warning)
> 1. One operation should be slower: `cons'. But `cons' simply prepends
> an element to the front of the array. The array could be
> over-allocated so only every N `cons' ops actually expand the array
> space. (This is a simplified case of a
> keep-the-gap-near-the-insertion-point array, but where the "gap" is
> always on the front, and there are no memcpy shifts at all.)
> 
> This:                       is:
> (list 1 2 3 4 5)            [___gap____12345]
> (cons 0 (list 1 2 3 4 5))   [___gap___012345]
> 
> But I'm assuming that the array holds objects themselves. If instead
> the array must contain pointers to objects, then goodbye locality of
> reference and this wouldn't be as big a win after all.
> 
> The more I think about it, Racket vectors need to be of pointers to
> things, not the things themselves. And so would need to be an array
> implementation of mutable lists. Hmm.
> 
> I'm guessing only flvector is a simple array of things (floats) themselves?
> _________________________________________________
>   For list-related administrative tasks:
>   http://lists.racket-lang.org/listinfo/users