Semi-persistent Vectors

Jay McCarthy <jay at plt-scheme dot org>

(require (planet jaymccarthy/spvector:1:0))

This package defines semi-persistent vectors. These vectors allow persistent (functional) reads, but not persistent writes. This means that you can always write to the most recent version of the vector and always read from past versions, but you cannot write to past versions.

(spvector? v) → boolean?

v : any/c

Determines if v is a semi-persistent vector.

(build-spvector n f) → spvector?

n : exact-positive-integer?

f : (exact-nonnegative-integer? . -> . any/c)

Like build-vector, but builds a semi-persistent vector.

(make-spvector e ...) → spvector?

e : any/c

Like vector, but builds a semi-persistent vector.

(spvector-length vec) → exact-positive-integer?

vec : spvector?

Returns the length of vec.

(spvector-ref vec i) → any/c

vec : spvector?

i : exact-nonnegative-integer?

Returns the value at i of vec, if it is a valid reference.

(spvector-set vec i v) → spvector?

vec : spvector?

i : exact-nonnegative-integer?

v : any/c

Returns a new semi-persistent vector where (spvector-ref new-vec i) returns v.

(spvector-set! vec i v) → void

vec : spvector?

i : exact-nonnegative-integer?

v : any/c

Destructively modifies vec, like vector-set!.

1 Implementation notes

Semi-persistent vectors may be used as sequences.

Semi-persistent vectors are implemented using a weak hash table to log undo information for modifications. These are indexed by uninterned symbols that are stored in the spvector? struct. This means that the garbage collector reclaims space in the log when the old version symbols are no longer reachable. Thus, if you use this structure in a purely linear way, it will behavior exactly like normal vectors asymptotically.