Semi-Persistent Arrays🔗 i

Jason Hemann,
Dan Friedman,
and Sam Tobin-Hochstadt <samth@ccs.neu.edu>

(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
( p-array? v)→boolean?
v:any/c

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

procedure
( make-p-array sizebuild-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)(* i10)))

'#&#<extendable-arr>

procedure
( p-array-ref parri)→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 5values )2)

2

procedure
( p-array-set parriv)→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 5values )4'foo))
> (p-array-ref changed-arr4)

'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 5values )))
> resized

'#&#<extendable-arr>
> (p-array-ref resized7)

7

top ← prev up next →