March Docs

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) =#

Each node in the 32-way trie. TrieLeaf holds a fixed 32-element list (a full leaf). TrieBranch holds a list of up to 32 child nodes (dense, no empties). TrieEmpty represents an absent node (used as a sentinel).

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

PVec(size, shift, root, tail) size = total elements shift = trie depth * 5 (0 means no levels above leaves) root = trie holding elements 0 .. (size - tail_len - 1) tail = up to 32 rightmost elements (dense list)

Functions

fndebug_from_list_by_pushdebug_from_list_by_push(xs : List(a)) : PVec(a)#

Test hook: builds the vector by pushing one element at a time, the construction from_list replaced. Compare the two with debug_same_shape (test/native/array_sort_by.march does).

Examples

march> Array.debug_same_shape(Array.from_list(List.range(0, 100)), Array.debug_from_list_by_push(List.range(0, 100)))
true
fndebug_same_shapedebug_same_shape(a : PVec(a), b : PVec(a)) : Bool#

Test hook: true when two vectors have the same trie shape -- size, shift, tail length, and the same branch fan-out and leaf lengths all the way down. Elements are not compared.

Examples

march> Array.debug_same_shape(Array.from_list([1, 2]), Array.from_list([3, 4]))
true
march> Array.debug_same_shape(Array.from_list([1, 2]), Array.from_list([1, 2, 3]))
false
fnemptyempty() : {PVec(a) | pvec_length(_) == 0}#

Returns an empty persistent vector.

Examples

march> Array.length(Array.empty())
0
march> Array.to_list(Array.empty())
[]
fnfold_leftfold_left(v : PVec(a), acc : b, f : b -> a -> b) : b#

Left fold over all elements in index order: collection first, init second, callback last (uncurried). f(acc, elem) = new_acc. O(n). Generic in the accumulator b, so a refinement demanded of the result is checked as an invariant of acc (see docs/refinement-types.md, "Folds").

Examples

march> Array.fold_left(Array.from_list([1, 2, 3]), 0, fn (acc, x) -> acc * 10 + x)
123
march> Array.fold_left(Array.from_list(List.range(1, 101)), 0, fn (acc, x) -> acc + x)
5050
fnfrom_listfrom_list(xs : List(a)) : {PVec(a) | pvec_length(_) == len(xs)}#

Builds a persistent vector from a list, preserving order. O(n): the trie is built in bulk, with the same shape repeated push would produce.

Examples

march> Array.to_list(Array.from_list([3, 1, 2]))
[3, 1, 2]
march> Array.get(Array.from_list(List.range(0, 1000)), 999)
999
fngetget(v : PVec(a), idx : {Int | _ >= 0 && _ < pvec_length(v)})#

Returns the element at index idx (0-based). O(log₃₂ n). Panics if idx is negative or >= length(v) (also a refinement precondition).

Examples

march> Array.get(Array.from_list([10, 20, 30]), 0)
10
march> Array.get(Array.from_list(List.range(0, 100)), 70)
70
fnis_emptyis_empty(v)#

Returns true if the vector has no elements. O(1).

Examples

march> Array.is_empty(Array.empty())
true
march> Array.is_empty(Array.push(Array.empty(), 1))
false
fnlengthlength(v)#

Returns the number of elements. O(1): the size is stored.

Examples

march> Array.length(Array.from_list([1, 2, 3]))
3
march> Array.length(Array.from_list(List.range(0, 100)))
100
fnmapmap(v : PVec(a), f) : {PVec(b) | pvec_length(_) == pvec_length(v)}#

Applies f to each element, returning a new vector of the results in the same order. O(n).

Examples

march> Array.to_list(Array.map(Array.from_list([1, 2, 3]), fn x -> x * 2))
[2, 4, 6]
march> Array.length(Array.map(Array.empty(), fn x -> x + 1))
0
fnpoppop(v : {PVec(a) | pvec_length(_) > 0})#

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

Examples

march> match Array.pop(Array.from_list([1, 2, 3])) do (rest, x) -> (Array.to_list(rest), x) end
([1, 2], 3)
march> match Array.pop(Array.from_list(List.range(0, 33))) do (rest, x) -> (Array.length(rest), x) end
(32, 32)
fnpushpush(v : PVec(a), elem) : {PVec(a) | pvec_length(_) == pvec_length(v) + 1}#

Appends an element at the end, returning a new vector. O(1) amortized (O(log₃₂ n) when the 32-element tail buffer is full and is flushed into the trie).

Examples

march> Array.to_list(Array.push(Array.from_list([1, 2]), 3))
[1, 2, 3]
march> Array.length(Array.push(Array.from_list(List.range(0, 32)), 32))
33
fnsetset(v : PVec(a), idx : {Int | _ >= 0 && _ < pvec_length(v)}, val) : {PVec(a) | pvec_length(_) == pvec_length(v)}#

Returns a new vector with the element at idx replaced by val; the original is unchanged. O(log₃₂ n). Panics if idx is negative or >= length(v) (also a refinement precondition): set never grows the vector, use push for that.

Examples

march> Array.to_list(Array.set(Array.from_list([1, 2, 3]), 1, 20))
[1, 20, 3]
march> Array.get(Array.set(Array.from_list(List.range(0, 100)), 50, -1), 50)
-1
fnsort_bysort_by(v : PVec(a), le : a -> a -> Bool) : {PVec(a) | pvec_length(_) == pvec_length(v)}#

Sorts by a comparator, stably: le(a, b) is true when a may come before b, as for List.sort_by. With a <=-style comparator, elements that compare equal keep their original order. O(n log n) comparisons, n - 1 on input that is already sorted or reversed.

Examples

march> Array.to_list(Array.sort_by(Array.from_list([3, 1, 2]), fn (a, b) -> a <= b))
[1, 2, 3]

march> Array.to_list(Array.sort_by(Array.from_list([(2, "a"), (1, "b"), (2, "c")]), fn (x, y) -> Tuple.first(x) <= Tuple.first(y)))
[(1, "b"), (2, "a"), (2, "c")]
fnsort_by_keysort_by_key(v : PVec(a), key : a -> Int) : {PVec(a) | pvec_length(_) == pvec_length(v)}#

Sorts by an Int key, stably: key is called once per element (not once per comparison), and elements with equal keys keep their original order.

Examples

march> Array.to_list(Array.sort_by_key(Array.from_list(["ccc", "a", "bb", "d"]), fn s -> String.byte_size(s)))
["a", "d", "bb", "ccc"]
fnto_listto_list(v)#

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

Examples

march> Array.to_list(Array.push(Array.push(Array.empty(), "a"), "b"))
["a", "b"]
march> Array.to_list(Array.empty())
[]