Array

Array module: persistent vector backed by a 32-way trie.

PersistentVector(a) is an immutable, indexed sequential collection. The trie has branching factor 32 (5-bit chunks of the index path).

A tail buffer holds the rightmost (up to 32) elements outside the trie. Appending to the tail is O(1); when it fills to 32 it is flushed into the trie (O(log₃₂ n)).

Complexity (n elements): get / set O(log₃₂ n) ≈ O(1) push O(1) amortized pop O(1) amortized length O(1) from_list / fold O(n)

Types

ptypeTrieNodeTrieNode(a) =#

ptypePVecPVec(a) = PVec(Int, Int, TrieNode(a), List(a))#

Functions

fnemptyempty()#

Returns an empty persistent vector.

fnlengthlength(v)#

Returns the number of elements. O(1).

fnis_emptyis_empty(v)#

Returns true if the vector is empty.

fngetget(v, idx)#

Returns the element at index idx (0-based). O(log₃₂ n). Panics if idx is out of range.

fnsetset(v, idx, val)#

Returns a new vector with element at idx replaced by val. O(log₃₂ n). Panics if idx is out of range.

fnpushpush(v, elem)#

Appends an element at the end. O(1) amortized.

fnpoppop(v)#

Removes the last element. Returns (new_vector, last_element). Panics if the vector is empty.

fnmapmap(v, f)#

Applies f to each element, returning a new vector with the results. O(n).

fnfold_leftfold_left(acc, v, f)#

Left fold over all elements in index order. f(acc, elem) = new_acc.

fnto_listto_list(v)#

Returns all elements as a list in index order. O(n).

fnfrom_listfrom_list(xs)#

Builds a persistent vector from a list. O(n).