Semi-Persistent Arrays
p-array?
make-p-array
p-array-ref
p-array-set
p-array-resize
7.0

Semi-Persistent Arrays

Jason Hemann,
Dan Friedman,
and Sam Tobin-Hochstadt <[email protected]>

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

(p-array? v)  boolean?

  v : any/c
Returns #t if v is a semi-persistent array, returns #f otherwise.

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:

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