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.
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.
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.
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.
pub def Array.new (n : I64) (fill : A) : Array Apub def Array.length (a : Array A) : I64pub def Array.get (a : Array A) (i : I64) : Option AOption, 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.
pub def Array.set (a : Array A) (i : I64) (v : A) : Array AThe 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.
pub def Array.set_in_place (b : ArrayBuilder A) (i : I64) (v : A) : IO UnitBuilder fill. O(1) compiled, O(n) interpreted -- see this module's own doc comment.
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.
pub def Array.builder (n : I64) (fill : A) : ArrayBuilder AA 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).
pub def Array.is_empty (a : Array A) : Boolpub def Array.get_or (a : Array A) (i : I64) (fallback : A) : Aget 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.
pub def Array.from_list (xs : List A) : Array AThe 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.
pub def Array.empty : Array AThe 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.
pub def Array.to_list (a : Array A) : List Apub def Array.map (f : A -> B) (a : Array A) : Array Bpub def Array.foldl (f : B -> A -> B) (init : B) (a : Array A) : BIts 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.
pub def Array.push (a : Array A) (v : A) : Array AOne 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.