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

From: Eli Barzilay (eli at barzilay.org)
Date: Tue Aug 2 16:32:18 EDT 2011

40 minutes ago, Vincent St-Amour wrote:
> 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.)

There's an even simpler problem:

  (define l (list (make-vector 100000) 1 2 3))
  (set! l (cdr l))

and that vector should be GC-able now.

-- 
          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                    http://barzilay.org/                   Maze is Life!


Posted on the users mailing list.