std::array

std/src/array.mo

Standard library: Array A -- the O(1)-indexed sequence std/ did not have.

Why this exists. Nothing in std/ offered indexed access, so code that wants one routes around the gap: std/map.mo's HashMap carries a hand-written Buckets16 (sixteen named fields with get_bucket/set_bucket dispatching on an index) precisely because there was no array to hold buckets in, and the DWARF work's offset->line resolution could not use the obvious line-start index with binary search.

Representation. An Array A IS its backing constructor: one Array.mk whose fields are the elements. That is not an implementation detail this module hides for fun -- it is what makes the natives work on both runtimes without monomorphisation. The Rust host holds a value as Value::Con { tag, args: Vec<Value> } and the compiled backend as Constructor { header, tag, field_count, fields[] } (runtime/src/runtime.c); both are already GC-managed, indexable, boxed-element vectors with a runtime length, and neither records element types. So array_* is generic in A for free.

Persistent core, mutable builder. Array A is immutable: set must copy, which is O(n), so bulk construction goes through ArrayBuilder A (filled in place under IO, then frozen) and everything after the freeze is O(1) reads on a value pure code can hold.

One cost differs by runtime, deliberately. Array.set_in_place is O(1) compiled and O(n) interpreted. A Value::Con's fields are behind an Arc shared with the environment slot the builder was read from, so the host copies on write (Arc::make_mut) where monad_set_field writes the real object. Both are CORRECT; only the cost differs. Under the interpreter, prefer Array.from_list/set folds.

typeArray#
pub type Array A {
    mk,
}

The backing constructor. mk takes no declared fields: its arity is whatever array_new/array_freeze allocated it with, which is the array's length. Do not construct one directly -- Array.new is the entry point, and a hand-built Array.mk has length 0.

instance_#
pub instance {A : Type} Copy (Array A) {
    def copy (a : Array A) : Pair (Array A) (Array A) := Pair.pair a a
}

A frozen Array is immutable and its backing constructor is never mutated in place (Array.set copies; freeze copies the builder), so sharing one is a pointer duplicate -- the same reasoning as Copy Nat, not the silent deep copy a Copy List would be. ArrayBuilder is the mutable half and deliberately has NO instance.

The instance is unconditional because this module ALREADY assumes the element may be duplicated: Array.new n fill writes fill into n slots, and from_list/set copy elements. Arrays of non-Copy elements are the deferred feature (view-types.md); a conditional [Copy A] instance does not resolve today (copy_class.mo's conditional parametric instances), so the assumption is recorded here rather than enforced.

typeArrayBuilder#
pub type ArrayBuilder A {
    mk,
}

A partially-filled Array under construction. The same representation as Array -- a distinct type only so the type checker keeps the mutable and immutable halves apart, which is what makes freeze meaningful.

defArray.new#
pub def Array.new (n : I64) (fill : A) : Array A
defArray.length#
pub def Array.length (a : Array A) : I64
defArray.get#
pub def Array.get (a : Array A) (i : I64) : Option A

Option, not a panic: an out-of-range read must not be undefined behaviour in the compiled backend, and String.get (init/string.mo) already returns Option U8 for the same reason.

defArray.set#
pub def Array.set (a : Array A) (i : I64) (v : A) : Array A

The persistent set: copy-then-write, O(n), input untouched. An out-of-range index returns the array unchanged -- the total counterpart of get's Option.none.

defArray.set_in_place#
pub def Array.set_in_place (b : ArrayBuilder A) (i : I64) (v : A) : IO Unit

Builder fill. O(1) compiled, O(n) interpreted -- see this module's own doc comment.

defArray.freeze#
pub def Array.freeze (b : ArrayBuilder A) : IO (Array A)

COPIES rather than casting. A cast would leave the builder aliasing a value pure code believes is frozen, and a later set_in_place would mutate it -- the one way this design can produce a wrong answer rather than a slow one.

defArray.builder#
pub def Array.builder (n : I64) (fill : A) : ArrayBuilder A

A fresh ArrayBuilder of n slots, every one holding fill. Shares array_new's implementation -- the two types have the same representation, and the distinction exists so the type checker keeps the mutable and immutable halves apart (see this module's doc comment).

defArray.is_empty#
pub def Array.is_empty (a : Array A) : Bool
defArray.get_or#
pub def Array.get_or (a : Array A) (i : I64) (fallback : A) : A

get with a caller-supplied answer for an out-of-range index, for the common case where the bound is already known good. A native: the Option that Array.get would allocate is never materialized, which is what makes a read allocation-free in the compiled backend.

defArray.from_list#
pub def Array.from_list (xs : List A) : Array A

The empty list case cannot call Array.new 0 fill -- there is no element of A to hand it, and Array.new needs one even at length 0. array_new reads its fill only when the length is positive, so the head element is available in exactly the case it is needed.

defArray.empty#
pub def Array.empty : Array A

The length-0 array. Nullary, so it needs no element of A at all -- Array.mk with zero fields IS the empty array, which is why the constructor is declared with none.

defArray.to_list#
pub def Array.to_list (a : Array A) : List A
defArray.map#
pub def Array.map (f : A -> B) (a : Array A) : Array B
defArray.foldl#
pub def Array.foldl (f : B -> A -> B) (init : B) (a : Array A) : B

Its own recursion rather than Foldable.foldl over to_list: the class method needs its instance in scope at the call site, and indexing directly is both simpler and avoids building the intermediate list.

defArray.push#
pub def Array.push (a : Array A) (v : A) : Array A

One element longer, with v at the end. O(n) -- an array is not a growable buffer; build with from_list where the whole contents are known.