Axle v0.22.0

Collections

std/collections ships three generic containers:

  • ArrayList<T>: a growable array. Positions are dense, 0 to size() - 1, so it is the right choice for an ordered sequence you read by index.
  • HashMap<K, V>: a key-to-value table. A lookup costs one probe into a SwissTable-style open-addressing table, not a scan.
  • HashSet<T>: a set of distinct values. Its add answers “was this new?” in one probe, which makes deduplication a one-liner.

Each container is generic, but the generic is resolved at compile time. The compiler generates one specialised body per element type you use, so an ArrayList<i32> and an ArrayList<string> never share code that has to check types at run time.

  ArrayList<i32>  ──▶  body compiled for i32 slots
  ArrayList<string> ─▶  body compiled for string slots (owned copies)
  HashMap<string, i32> ─▶ probes by string hash, values as i32

Note The element type decides what a container can hold. Keys of a HashMap and elements of a HashSet must be hashable: i32, i64, string, or a class instance (hashed by identity). f64 is refused for both, because NaN and float precision make equality unreliable. Collect floats in an ArrayList<f64> instead.

ArrayList<T>: dynamic array

use std::collections::ArrayList;

fn main() : i32 ! IndexOutOfBoundsException {
    let list : ArrayList<i32> = new ArrayList<i32>();
    list.add(10);
    list.add(20);
    list.add(30);

    if (list.size() != 3)       { return 1; }
    if (list.get(0) != 10)      { return 2; }
    if (!list.contains(20))     { return 3; }

    list.set(1, 200);                           // bool: false, nothing written, past the end
    let removed : i32 = list.removeAt(0);       // returns 10; removeAt throws on a bad index
    if (removed != 10)          { return 4; }
    if (list.size() != 2)       { return 5; }

    list.clear();
    if (!list.isEmpty())        { return 6; }
    return 0;
}

Method reference

MethodReturnsEffect
add(v)boolappend; always true (an append always changes the list)
reserve(capacity)voidgrow the backing buffer to at least capacity slots
get(i)T \| nullindexed read; null when i is out of range; never throws
getOrDefault(i, default)Tindexed read; default past the end
getUnchecked(i)Tthe same read with the bounds guard removed; the caller guarantees 0 <= i < size()
set(i, v)boolindexed write; false, nothing written, when i is outside [0, size)
setUnchecked(i, v)voidthe same write with the bounds guard removed
replace(i, v)Tindexed write; returns the value it displaced; throws IndexOutOfBoundsException
removeAt(i)Tdelete at i and return the removed value; throws IndexOutOfBoundsException
pop()T \| nulldelete and return the last element; null when empty; constant time, no allocation
indexOf(v)i64first index of v, or -1
contains(v)boolmembership test
size()i64element count
isEmpty()booltrue when size() is 0
clear()voidremove every element
sort()voidascending, in place (see Sorting and searching)
sortDescending()voiddescending, in place

reserve(n) makes a bulk load pay one allocation instead of the doubling sequence. Call it when you know the final size, then add n times without a reallocation in between.

Why removeAt is not a pop

  removeAt(0) on [A, B, C, D]

  before:  [A][B][C][D]
  after:      [B][C][D]        every survivor shifts left: O(n)
              └── copied into a fresh buffer: one malloc per call

removeAt(i) is O(n) and reallocates: it copies the surviving elements into a fresh backing buffer to keep exactly one live reference per element. To take from the end, use pop(). It is the constant-time, allocation-free member, the right tool when the list is a stack. Reach for removeAt only when the position itself is what you care about.

Throwing and non-throwing access

replace and removeAt throw IndexOutOfBoundsException on a bad index. set is the non-throwing twin: past the end it answers false and writes nothing. get never throws; it returns T | null, so it needs neither a ! clause nor a catch.

The example above lists the exception in main’s ! set, so it propagates. To handle it at the call site, the try statement covers a call whose value you drop:

use std::collections::ArrayList;

fn demo(list : ArrayList<i32>) : i32 {
    try {
        list.replace(1, 200);
    } catch e : IndexOutOfBoundsException {
        println("replace: index out of range");
    }
    let removed : i32 = list.removeAt(0) catch e {
        return -1;                    // the catch block supplies the value on the throw path
    };
    return removed;
}

When the call does produce the value you want, expr catch e { … } folds the handler into the expression.

The trailing ; is required: expr catch e { … } is an expression, and the statement still needs its terminator.

The handler must either end on a value of the guarded type or leave with return or throw. It cannot fall through, because the value it would have produced is the one the binding reads.

Iteration

for (x of collection) walks an ArrayList, a HashSet or a HashMap (over its keys). x is each element in turn, and break, continue and return leave the loop as they do in any other:

use std::collections::ArrayList;
use std::collections::HashMap;

fn sum(list : ArrayList<i64>) : i64 {
    let mut total : i64 = 0;
    for (x of list) {
        total = total + x;
    }
    return total;
}

fn describe(ages : HashMap<string, i32>, names : ArrayList<string>) : void {
    for (name of names) {
        println(name);
    }
    for (key of ages) {                  // a map yields its keys…
        println(key);
        println((ages.get(key) ?? 0).toString());   // …and `get` reads the value
    }
}

fn main() : i32 {
    let list : ArrayList<i64> = new ArrayList<i64>();
    list.add(1);
    list.add(2);
    if (sum(list) != 3) { return 1; }

    let ages : HashMap<string, i32> = new HashMap<string, i32>();
    ages.put("alice", 30);
    let names : ArrayList<string> = new ArrayList<string>();
    names.add("alice");
    describe(ages, names);
    return 0;
}

What the loop does

The loop is the while you would otherwise write over the collection’s own nextSlot / elementAt methods. Three things follow from that:

  • Independent loops. The cursor lives in the loop, so two loops over the same list do not affect each other.
  • Empty collections. An empty collection never runs its body.
  • Order. A list is walked in its own order. A set or a map is walked in the table’s order, not in insertion order.

Adding or removing elements from inside a loop over the collection does not corrupt memory, but which elements the loop then visits is unspecified. The loop variable borrows the element: do not read it after the body removed or overwrote that element (take what you need, such as its length, first).

Iterating your own class

A class of your own is iterable the same way. Declare either pair of methods:

  • hasNext() : bool with next() : T;
  • nextSlot(start : i64) : i64 with elementAt(slot : i64) : T.

Then for (x of it) works over it, with x typed by what the second method returns.

Listing : Iterator<T> or : Iterable<T> (from std::collections) is optional. It only has the compiler check your methods against the contract.

See Iterating your own types.

Reading by position

When you need the position as well, or a different order, index with a while and get(i) ?? fallback. list.get(i) returns T | null, and ?? 0 unwraps it.

Read as written, each access is a bounds check plus a nullable. The compiler removes both when its value-range analysis can prove the index is in range. That happens for the two shapes you actually write:

  • a i < list.size() loop guard;
  • an index it can bound on its own, such as (seed % list.size()).

The read then compiles to a plain indexed load, with no branch and no tag.

When the index cannot be proven safe, the check and the ?? fallback stay exactly as written. You never lose the safety, only the cost when the check is provably redundant.

size() returns the exact element count as an i64. A slot nextSlot returned is read with elementAt (the loop protocol’s unguarded read); a slot from anywhere else is read with elementAtChecked, which raises IndexOutOfBoundsException for a position the collection does not hold.

Building from a range

use std::collections::ArrayList;

fn fibs(n : i32) : ArrayList<i64> {
    let out : ArrayList<i64> = new ArrayList<i64>();
    let mut a : i64 = 0;
    let mut b : i64 = 1;
    for (i of 0..n) {
        out.add(a);
        let next : i64 = a + b;
        a = b;
        b = next;
    }
    return out;
}

Filtering and mapping

There is no combinator API. Write the loop:

use std::collections::ArrayList;

fn evens(list : ArrayList<i32>) : ArrayList<i32> {
    let out : ArrayList<i32> = new ArrayList<i32>();
    let mut i : i32 = 0;
    while (i < list.size()) {
        let v : i32 = list.get(i) ?? 0;
        if (v % 2 == 0) {
            out.add(v);
        }
        i = i + 1;
    }
    return out;
}

fn squared(list : ArrayList<i32>) : ArrayList<i32> {
    let out : ArrayList<i32> = new ArrayList<i32>();
    let mut i : i32 = 0;
    while (i < list.size()) {
        let v : i32 = list.get(i) ?? 0;
        out.add(v * v);
        i = i + 1;
    }
    return out;
}

Sorting and searching

ArrayList<T> sorts in place with sort() (ascending) or sortDescending(). Both order any element type the built-in compare(a, b) handles: numbers by value, string lexicographically. You write no comparison of your own:

use std::collections::ArrayList;

fn main() : i32 {
    let xs : ArrayList<i32> = new ArrayList<i32>();
    xs.add(5); xs.add(1); xs.add(4); xs.add(2); xs.add(3);
    xs.sort();                              // [1, 2, 3, 4, 5]
    println(xs.get(0) ?? -1);               // 1

    let names : ArrayList<string> = new ArrayList<string>();
    names.add("cherry"); names.add("apple"); names.add("banana");
    names.sort();                           // apple, banana, cherry
    println(names.get(0) ?? "?");           // apple

    let desc : ArrayList<i32> = new ArrayList<i32>();
    desc.add(1); desc.add(3); desc.add(2);
    desc.sortDescending();                  // [3, 2, 1]
    println(desc.get(0) ?? -1);             // 3
    return 0;
}

The algorithm depends on the element type:

Element typeAlgorithmWorst case
i8, i16, i32, i64, bool, char, f32, f64LSD radix sort: one counting pass per key byte that varieslinear in the key bytes
u8, u16, u32, u64, string, and class instancesintrosort: median-of-3 quicksort, heapsort past a 2 * floor(log2 n) depth budget, insertion sort on small ranges (up to 17 elements)O(n log n)

Neither path indexes out of range, so neither carries a ! error set.

A string sorts by its characters, never by pointer identity. A class instance sorts by an unspecified but stable identity order, so sort by a projected key when you need a meaningful order for objects.

Note sort() orders string elements lexicographically. A bare > on two strings would compare identity, which is why the collection never uses it (see Strings and text).

Once a list is sorted, a binary search finds an element in O(log n). Halve the [lo, hi] window each step, and compute the midpoint as lo + (hi - lo) / 2 so that the sum cannot overflow an i32:

use std::collections::ArrayList;

fn binarySearch(xs : ArrayList<i32>, target : i32) : i64 {
    let mut lo : i64 = 0;
    let mut hi : i64 = xs.size() - 1;
    while (lo <= hi) {
        let mid : i64 = lo + (hi - lo) / 2;
        let v : i32 = xs.get(mid) ?? 0;
        if (v == target) { return mid; }
        if (v < target)  { lo = mid + 1; }
        else             { hi = mid - 1; }
    }
    return -1;                                   // absent
}

indexOf is the O(n) linear alternative: no sort needed, but it scans the whole list. Sort once and binary-search when you probe the same list many times; use indexOf for a one-off lookup.

HashMap<K, V>: key to value

use std::collections::HashMap;

fn main() : i32 {
    let scores : HashMap<string, i32> = new HashMap<string, i32>();
    scores.put("alice", 90);
    scores.put("bob", 85);
    scores.put("carol", 92);

    if (scores.size() != 3)              { return 1; }
    if (!scores.containsKey("alice"))    { return 2; }
    if (scores.get("alice") != 90)       { return 3; }

    scores.put("alice", 95);                    // overwrite
    if (scores.get("alice") != 95)       { return 4; }

    let existed : bool = scores.remove("bob");
    if (!existed)                         { return 5; }
    if (scores.containsKey("bob"))        { return 6; }

    return 0;
}

Method reference

MethodReturnsEffect
put(k, v)voidinsert, or overwrite the value of an existing key
get(k)V \| nulllookup; null when absent; never throws
getOrDefault(k, default)Vlookup; default on a miss
containsKey(k)boolmembership test
remove(k)booldelete; true if the key existed
size()i64entry count
isEmpty()booltrue when size() is 0
clear()voidremove every entry

remove answers whether a binding was present; it does not return the old value. Read the value first with get if you need it.

Lookups and the missing key

get(k) returns V | null: null on a miss, never a throw. null is a distinct type, not a falsy 0, so a stored 0 is always told apart from an absent key. Two idioms:

use std::collections::HashMap;

fn lookup(map : HashMap<string, i32>, key : string) : i32 {
    return map.get(key) ?? -1;                 // sentinel on miss
}
use std::collections::HashMap;

fn describe(map : HashMap<string, i32>, key : string) : string {
    if (map.get(key) == null) { return "absent"; }
    return "present";
}

A V | null compares directly against a concrete value, so the common assertions need no ??. null != 90 is true, and an absent key never equals the value:

use std::collections::HashMap;

fn isNinety(map : HashMap<string, i32>, key : string) : bool {
    return map.get(key) == 90;                 // false when the key is absent
}

getOrDefault(key, default) is the same single-probe miss-with-default as get(key) ?? default. Prefer it on hot paths for readability.

Counting word frequencies

use std::collections::ArrayList;
use std::collections::HashMap;

fn wordCount(words : ArrayList<string>) : HashMap<string, i32> {
    let counts : HashMap<string, i32> = new HashMap<string, i32>();
    let mut i : i32 = 0;
    while (i < words.size()) {
        let w : string = words.get(i) ?? "";
        counts.put(w, counts.getOrDefault(w, 0) + 1);
        i = i + 1;
    }
    return counts;
}

Each put copies the key, so the map keeps its own string. The caller’s w stays valid for the next iteration.

Integer keys for caches

use std::collections::HashMap;

class Session {
    token : string;
    constructor(token : string) {
        self.token = token;
    }
}

fn main() : i32 {
    let cache : HashMap<i64, Shared<Session>> = new HashMap<i64, Shared<Session>>();
    cache.put(7, share new Session("abc"));
    if (cache.containsKey(7)) { return 0; }
    return 1;
}

Session owns a heap string, so HashMap<i64, Session> is refused with E0604: a by-value owned element has no per-element store increment, and the map would leak it.

Wrapping the element in Shared<U> makes the co-ownership explicit. The map increments the count on every store, and its destructor decrements every live slot.

HashSet<T>: unique values

use std::collections::HashSet;

fn main() : i32 {
    let seen : HashSet<string> = new HashSet<string>();
    let added1 : bool = seen.add("alpha");      // true: new entry
    let added2 : bool = seen.add("alpha");      // false: duplicate
    let added3 : bool = seen.add("beta");       // true

    if (seen.size() != 2)               { return 1; }
    if (!seen.contains("alpha"))        { return 2; }
    if (seen.contains("gamma"))         { return 3; }

    let removed : bool = seen.remove("alpha");
    if (!removed)                        { return 4; }
    if (seen.size() != 1)               { return 5; }

    return 0;
}

Method reference

MethodReturnsEffect
add(v)boolinsert; true if the value was new
remove(v)booldelete; true if the value existed
contains(v)boolmembership test
size()i64element count
isEmpty()booltrue when size() is 0
clear()voidremove every element

Deduplicating an ArrayList

use std::collections::ArrayList;
use std::collections::HashSet;

fn unique(list : ArrayList<string>) : ArrayList<string> {
    let seen : HashSet<string> = new HashSet<string>();
    let out  : ArrayList<string> = new ArrayList<string>();
    let mut i : i32 = 0;
    while (i < list.size()) {
        let v : string = list.get(i) ?? "";
        if (seen.add(v)) {         // true the first time v is seen
            out.add(v);            // both containers copied the string
        }
        i = i + 1;
    }
    return out;
}

seen.add(v) returns true exactly when v is new. Combined with an ArrayList, it keeps first-seen order.

Strings are copied on store

A collection copies a string element on store: ArrayList.add and HashMap.put take their own copy of the payload.

The caller keeps its binding, so the same v above can go into the set and the list on one path without any v + "". Mutating your binding afterwards does not change what was stored.

A Shared<U> element is the exception. It is referenced, not copied, so the container only increments its count.

Collections of user classes

A collection of a user class stores each element as a reference to the instance. The element must be Shared<T>: a by-value owned element declares a destructor, and a collection has no per-element store increment for it. So ArrayList<Job> is refused with E0604, and ArrayList<Shared<Job>> is what compiles.

use std::collections::ArrayList;

class Job {
    pub id   : i32;
    pub body : string;
    constructor(id : i32, body : string) {
        self.id = id;
        self.body = body;
    }
}

fn main() : i32 {
    let jobs : ArrayList<Shared<Job>> = new ArrayList<Shared<Job>>();
    jobs.add(share new Job(1, "first"));
    jobs.add(share new Job(2, "second"));

    let j : Shared<Job> | null = jobs.get(0);
    if (j != null) { return j.id; }              // narrowed to Shared<Job> here
    return -1;                                    // absent
}

Lifetime: the ArrayList co-owns each element. The store increments the count, and the list’s destructor decrements every live slot.

An entry stays alive while the list holds it. It is freed at the last release, whether that is the list or a handle you kept.

Collections of structs

A struct is not a collection element today, for one of two reasons:

The structArrayList<S>Why
holds only plain dataE0761the collection compares its elements, and a struct has no equality
holds an array, an object or a Shared<T>E0604such a struct has one owner, and moving it asks you to write copy or own; a collection is written once for every T and cannot ask

Two shapes work instead:

Building a small index

use std::collections::HashMap;

class Index {
    byId   : HashMap<i64, string>,
    byName : HashMap<string, i64>,

    constructor() {
        self.byId   = new HashMap<i64, string>();
        self.byName = new HashMap<string, i64>();
    }

    pub fn add(self, id : i64, name : string) : void {
        self.byId.put(id, name);        // put copies the value …
        self.byName.put(name, id);      // … and copies the key
    }

    pub fn lookupById(self, id : i64) : string | null {
        return self.byId.get(id);
    }

    pub fn lookupByName(self, name : string) : i64 | null {
        return self.byName.get(name);
    }
}

Keep the two maps in sync on every add. The type system cannot enforce that invariant, so route every mutation through one helper, as add does here.

Choosing the right container

PatternContainer
ordered list, access by positionArrayList<T>
set membership, deduplicationHashSet<T>
key to value lookupHashMap<K, V>
ordered list and set semantics togetherArrayList<T> plus HashSet<T> side by side
fixed compile-time sizeT[N] (built-in fixed array)
count occurrencesHashMap<T, i32>

Fixed arrays: built-in, no use needed

fn main() : i32 {
    let mut buf : i32[16] = i32[16](0);          // 16 zeros
    buf[0] = 7;
    buf[15] = 42;
    return buf[0] + buf[15];                     // 49
}

The a[i] operator does not raise a catchable exception. An out-of-bounds index aborts the process with a message on stderr and a non-zero exit, so it can never be listed in a ! set or caught as IndexOutOfBoundsException.

Fixed arrays live on the stack when they are small, and on the heap through the same escape rules as classes when they are large. Use them when the size is known at compile time. Reach for ArrayList<T> when the size grows at run time.

Limits / Uncabled

FeatureStateDetail or workaround
for (entry of map) over key and value togetherA map yields its keysRead the value with map.get(key)
list.iterator() returning an iterator objectNot provided: a collection is walked by the loop itselffor (x of list), or write your own Iterator<T> class
Collection, List, Set, Map contractsDeclared in the stdlib, not adopted by ArrayList, HashMap or HashSet (no : Trait clause on them)Use the concrete methods listed above
Map and filter combinatorsNot providedWrite the loop, as in Filtering and mapping
sort(dir : Sort)The Sort enum (Sort::Up, Sort::Down) names the direction; no sample exercises itUse sort() and sortDescending()
f64 elements of a HashSet, keys of a HashMapRefused by hash_keyUse an ArrayList<f64>, or key by a string or i64 form of the value
getUnchecked / setUncheckedNo bounds check: the caller guarantees 0 <= i < size()Use get and set unless the index is provably in range; the stdlib calls them inside unsafe blocks
removeAt in a hot loopO(n) and one allocation per callUse pop() for stacks, or rebuild the list in one pass

See also

collectionsarraylisthashmaphashset