8.16.0.2
Semi-Persistent Arrays
| (require data/p-array) | package: persistent-array |
This library provides an implementation of semi-persistent arrays. Semi-persistent arrays present functional get and set operations that return new arrays efficiently, but existing arrays may be modified under the covers during construction of new arrays. Thus the data structure is persistent, but neither thread safe nor implemented in a purely functional manner. See A Persistent Union-Find Data Structure by Sylvain Conchon and Jean-Christophe Filliâtre for more details.
procedure
(make-p-array size build-item) → p-array?
size : fixnum? build-item : (-> exact-nonnegative-integer? any/c)
Returns a semi-persistent array containing size items, where
each item is the result of applying build-item to its position in the
array (similarly to build-list and build-vector).
Example:
> (make-p-array 5 (λ (i) (* i 10))) '#&#<extendable-arr>
procedure
(p-array-ref parr i) → any/c
parr : p-array? i : fixnum?
Returns the element of parr at position i in amortized
constant space and time.
Example:
> (p-array-ref (make-p-array 5 values) 2) 2
procedure
(p-array-set parr i v) → p-array?
parr : p-array? i : fixnum? v : any/c
Returns a new semi-persistent array that is equivalent to parr
with v at position i. The new array is constructed in
amortized constant space and time.
Examples:
> (define changed-arr (p-array-set (make-p-array 5 values) 4 'foo)) > (p-array-ref changed-arr 4) 'foo
procedure
(p-array-resize parr) → p-array?
parr : p-array?
Returns a new semi-persistent array that is equivalent to parr
with its size doubled. New positions in the array are filled using the initial
build-item procedure provided during the construction of parr
with make-p-array.
Examples:
> (define resized (p-array-resize (make-p-array 5 values))) > resized '#&#<extendable-arr>
> (p-array-ref resized 7) 7