The type of persistent arrays

init n f creates the array [|f 0; f 1; ...; f (n-1)|]. O(n) complexity.

make n x creates the array [|x; x; ...; x|] with length n. O(n) complexity.

of_array arr creates the persistent array containing the same elements as arr This copies the array, so future modifications to arr will not corrupt the persistent array. O(Array.length arr) complexity.

of_list l creates a persistent array with the same elements as l. O(List.length l) complexity.

size t is the size (number of elements) of the array t

get t i returns the i-th element of the array. O(1) complexity (after reroot).

• raises Invalid_argument

  if i is not in 0 .. (size t - 1)

set t i v returns a new array whose values are the same as t except at position i, where the value is v. O(1) complexity (after reroot).

• raises Invalid_argument

  if i is not in 0 .. (size t - 1)

pretty ~pp_sep pp_elt t prints the array at t, using pp_elt to print elements and pp_sep to separate them. pp_sep defaults to printing a semicolon and a space).

diff a b create a table of differences i -> (a.(i), b.(i)) between a and b Requires a and b to share a common root (i.e. derive from the same init or make).

The diff table may include identical values i -> (v,v), these correspond to changes that are reverted on the chain from a to b. For example: let b = set (set a i x) i a.(i).

For performance: have a be the one closest to reroot (i.e. the last modified value).

O(d) complexity (after reroot at a), where d is the number of updates (set operations) between a and b.

Versioned persistent arrays also return the element with the lowest version tag.

diff_key a b is the same as diff a b, but only returns the keys i such that a.(i) and b.(i) may be different.

Versioned persistent arrays also return the element with the lowest version tag.

append t arr extends t by adding the values from arr at the end. This modifies t and all previous versions of t. O(size t + Array.length arr) complexity (after reroot).

• raises Invalid_argument

  if size t + Array.length arr > Sys.max_array_length

extend t n x extends t by appending n times the value x: [|t.(0); ...; t.(size t - 1); x; ...; x|]. This modifies t and all previous versions of t. O(size t + n) complexity.

• raises Invalid_argument

  if n is negative or if size t + n > Sys.max_array_length.

map f t creates a new persistent array, initialized by [|f (get t 0); ...; f (get t (size t) - 1)|]

iter f t calls f on every element in order: f (get t 0); ...; f (get t (size t - 1))

fold f init t is f (... f init (get t 0) ...) (get t (size t - 1))