Skip to main content

Collections

Verum's standard collections — List, Map, Set, Deque, BinaryHeap, BTreeMap, BTreeSet — share a consistent semantic-honest naming scheme. Every collection implements Iterator, IntoIterator, Clone, Debug, Eq, and Default.

For the normative API surface of each type, see stdlib/collections.

Constructing​

// Empty
let xs: List<Int> = List.new();
let xs: List<Int> = [];

// Literal
let xs = [1, 2, 3, 4, 5];                    // list literal
let ys = [0; 10];                             // 10 copies of 0
let zs = [1, 2, 3];                      // legacy list macro

// From iter
let fibs: List<Int> = (0..10).map(|n| fib(n)).collect();

// Constructor with capacity
let big: List<Int> = List.with_capacity(1024);

// From range
let r: List<Int> = (0..100).collect();

Similarly for Map, Set, etc.:

let m = Map.new();
let m = Map.from([("a", 1), ("b", 2)]);
let m = Map.from([("a", 1), ("b", 2), ("c", 3)]);

let s = Set.new();
let s = Set.from([1, 2, 3]);

let d = Deque.new();
let d = Deque.from_list(list);

Access​

Call shapes below are API reference excerpts, not standalone programs.

xs[0]                                // panics on OOB
xs.get(i)                            // -> Maybe<&T>
xs.first() / xs.last()               // -> Maybe<&T>

map[key]                             // panics on missing
map.get(key)                         // -> Maybe<V>
map.get_mut(&key)                    // -> Maybe<&mut V>, K: Clone
map.contains_key(key) -> Bool

set.contains(&value) -> Bool

Prefer .get over [] when the key might be absent — .get returns Maybe and short-circuits elegantly with ?.

Map values and mutable access​

get takes its key by value. Its Maybe<V> result is not a borrow of the map's storage, although references inside V can still alias other objects. get_mut takes a borrowed key and returns a mutable reference to the existing value slot. Keep that borrow within the map's lifetime and end it before insertions, removals, clearing, capacity changes or other table rebuilding. Borrow syntax is not a guarantee that every invalidated reference is detected.

The complete example below contrasts a scalar value returned by get with a write through get_mut. It runs under the interpreter; native AOT and other Map operations have separate support limits.

mount core.collections.map.Map;
mount core.base.maybe.Maybe;

fn main() {
    let mut counts: Map<Text, Int> = Map.new();
    counts.insert("apple", 3);
    let before = counts.get("apple").unwrap();
    assert(counts.get("pear") is Maybe.None);
    assert(counts.get_mut(&"pear") is Maybe.None);

    match counts.get_mut(&"apple") {
        Maybe.Some(value) => { *value = *value + 1; },
        Maybe.None => panic("missing key"),
    }

    assert_eq(before, 3);
    assert_eq(counts.get("apple").unwrap(), 4);
    print("map-access: ok");
}
map-access: ok

Mutation​

xs.push(value)
xs.pop() -> Maybe<T>
xs.insert(index, value)
xs.remove(index) -> T
xs.swap_remove(index) -> T          // O(1); reorders

map.insert(key, value) -> Maybe<V>  // returns the old value
map.remove(key) -> Maybe<V>

set.insert(value) -> Bool           // true if newly inserted
set.remove(&value) -> Bool          // true if was present

The entry API​

The entry API is the shape the standard library declares for "insert or update":

let mut counts: Map<Text, Int> = Map.new();
for word in words.iter() {
    *counts.entry(word.clone()).or_insert(0) += 1;
}

One lookup instead of the .contains_key + .get + .insert dance.

warning

Known limitation: the interpreter's entry API is incomplete. It can fail on populated maps as well as empty ones. The interpreter carries a separate Map entry representation that source methods such as entry, get_key_value and remove_entry cannot reliably read. The entry snippets here describe the declared API; they are not supported recipes. See Map support for the current backend boundary.

Basic lookup and update operations are handled by the interpreter's runtime path; a successful lookup does not validate the entry API.

Use an explicit lookup followed by insertion:

mount core.collections.{Map, List};

fn main() {
    let words: List<Text> = List.from([ "a", "b", "a" ]);
    let mut counts: Map<Text, Int> = Map.new();
    for word in words.iter() {
        let n = counts.get_or(word.clone(), 0);
        counts.insert(word.clone(), n + 1);
    }
    print(f"a={counts.get_or(\"a\", 0)} b={counts.get_or(\"b\", 0)}");
}
a=2 b=1

This costs a second lookup and avoids the incomplete entry API.

// Or-insert, or-insert-with, or-default:
map.entry(key).or_insert(default_value);
map.entry(key).or_insert_with(|| compute_default());
map.entry(key).or_default();             // T: Default

// And-modify:
map.entry(key).and_modify(|v| *v += 1).or_insert(1);

// Pattern match on the entry:
match map.entry(key) {
    MapEntry.Occupied(mut entry) => {
        *entry.get_mut() = new_value;
    }
    MapEntry.Vacant(entry) => {
        entry.insert(default);
    }
}

Iteration​

Every collection iterates:

for x in &xs { ... }                  // iter()  - &T
for x in &mut xs { ... }              // iter_mut() - &mut T
for x in xs { ... }                   // into_iter() - owned T (consumes xs)

for (k, v) in &map { ... }            // declared Map iteration yields (K, V)
for (k, v) in &mut map { ... }        // &K, &mut V
for (k, v) in map { ... }             // owned K, V

For Map, iter_mut and values_mut yield borrowed values, whereas drain removes entries and yields owned (K, V) pairs. End iterators and outstanding borrows before changing the table's structure. See Map support for iterator limits.

Combinator stack​

let primes: List<Int> = (2..1000)
    .filter(|n| is_prime(*n))
    .take(100)
    .collect();

// Grouping is a method on the LIST, not an iterator adapter: there is
// no `into_group_map`. `group_by` answers a `Map<K, List<T>>` directly,
// so a count is `len()` over each group.
let groups: Map<Text, List<Email>> = emails.group_by(|e| e.domain());
let by_domain: Map<Text, Int> = groups
    .into_iter()
    .map(|(k, vs)| (k, vs.len()))
    .collect();

Counting​

let counts: Map<Text, Int> = words
    .iter()
    .fold(Map.new(), |mut acc, w| {
        *acc.entry(w.clone()).or_insert(0) += 1;
        acc
    });

This uses the entry API, so it carries the same limitation as The entry API above: it does not run today. get_or + insert inside the fold works.

Or with a comprehension:

let counts = {w: words.iter().filter(|x| *x == w).count()
              for w in set{x for x in &words}};

(See language/comprehensions.)

Grouping​

// `List.group_by(&self, key_fn)` — on the list itself, and it already
// answers the map. `into_group_map_by` does not exist.
let grouped: Map<Category, List<Item>> =
    items.group_by(|item| item.category.clone());

core.collections carries two free group_by functions besides the method, and they differ in what they answer: the one in map.vr takes an ITERATOR and answers Map<K, List<T>>, the one in list.vr takes a &List and answers List<(K, List<T>)> — an association list, not a map. Pick by the return type you want.

Or manually:

let mut groups: Map<Category, List<Item>> = Map.new();
for item in &items {
    groups.entry(item.category.clone())
          .or_insert_with(List.new)
          .push(item.clone());
}

Same limitation as The entry API. Read the group with get_or, push, then insert it back.

Sorting​

// List<T: Ord>
xs.sort();                            // stable, in place
xs.sort_unstable();                   // faster, not stable
xs.sort_by(|a, b| a.cmp(b));          // custom comparator
xs.sort_by_key(|x| key(x));           // T → K

// Produce a new sorted list:
let ys = xs.sorted();                 // clone + sort

// BTreeMap/BTreeSet are already ordered — iterate in key order.
for (k, v) in &btree_map { ... }

Top-K​

For the largest K items, BinaryHeap is O(n log k), not O(n log n):

// `BinaryHeap` already ships `top_k` and `bottom_k`; this is the shape
// they have, kept because writing it is how you learn the `Reverse`
// trick. Reach for `heap.top_k(k)` in real code.
fn top_k<T: Ord>(items: &List<T>, k: Int) -> List<T> {
    let mut heap: BinaryHeap<Reverse<T>> = BinaryHeap.with_capacity(k);
    for item in items.iter() {
        heap.push(Reverse(item.clone()));
        if heap.len() > k { heap.pop(); }
    }
    heap.into_sorted_list().into_iter().map(|Reverse(x)| x).collect()
}

Reverse<T> turns a max-heap into a min-heap. BinaryHeap (max by default) + Reverse is the idiomatic top-K.

Deduplication​

// Preserves order:
let deduped: List<_> = xs.iter().cloned().collect<Set<_>>().into_iter().collect();

// Sorted order:
xs.sort();
xs.dedup();                           // remove consecutive duplicates

// By key:
xs.dedup_by_key(|x| x.id);

Sliding windows and chunks​

xs.windows(3)                         // &[T; 3]... for each of size 3
  .map(|w| w.iter().sum<Int>())
  .collect<List<_>>()

xs.chunks(5)                          // &[T]... fixed chunks
  .for_each(|chunk| process(chunk))

Set operations​

let a: Set<Int> = Set.from([1, 2, 3]);
let b: Set<Int> = Set.of(2, 3, 4);

// All four return a `Set<T>` outright — built eagerly, not a lazy view.
// There is no iterator here to `.cloned().collect()`.
let union:        Set<Int> = a.union(&b);
let intersection: Set<Int> = a.intersection(&b);
let difference:   Set<Int> = a.difference(&b);
let symmetric:    Set<Int> = a.symmetric_difference(&b);

let is_subset   = a.is_subset(&b);
let is_superset = a.is_superset(&b);
let is_disjoint = a.is_disjoint(&b);

Deque — front and back​

let mut d: Deque<Int> = Deque.new();
d.push_back(1);
d.push_back(2);
d.push_front(0);                      // [0, 1, 2]
d.pop_front();                        // Maybe.Some(0)
d.pop_back();                         // Maybe.Some(2)
d.rotate_left(3);                     // rotate
d.rotate_right(3);

BTreeMap — ordered map​

let mut m: BTreeMap<Int, Text> = BTreeMap.new();
m.insert(3, "three");
m.insert(1, "one");
m.insert(2, "two");

for (k, v) in &m { ... }              // 1 → one, 2 → two, 3 → three

// Range queries:
for (k, v) in m.range(1..3) { ... }   // 1 and 2
for (k, v) in m.range(..=2) { ... }
for (k, v) in m.range(2..) { ... }

Use BTreeMap when you need ordered iteration or range queries. Map (hashed) is faster for plain key lookup but doesn't maintain order.

Capacity and reallocation​

let mut xs: List<Int> = List.with_capacity(1000);
xs.reserve(500);                      // ensure 500 more fit
xs.shrink_to_fit();                   // shrink unused
xs.shrink_to(100);                    // shrink to at least 100

let cap = xs.capacity();
let n = xs.len();

Pre-allocating avoids rehashing/regrowth overhead when you know the final size.

Memory layout notes​

Per semantic honesty:

  • List<T> might be a contiguous buffer, a ring buffer, or a rope — chosen by profile-guided optimisation. Don't rely on specific layout.
  • Map<K, V> might be Swiss-table, B-tree, or perfect hash.
  • Set<T> is Map<T, ()> under the hood.
  • Deque<T> and BinaryHeap<T> commit to their implementation by name.

The with [...] clause is capability attenuation — it narrows what a value may be used for (Read, Write, Network, FileSystem, or a capability you name yourself), not how it is laid out:

type ReadOnlyLog is List<Text> with [Read];

For a specific layout there is no knob on the semantic types. Use a packed byte-buffer construction for byte-oriented FFI: a type such as [Byte; 64] alone does not establish the storage layout of an arbitrary returned value. @repr(C) pins a record's field order for FFI. The supported array-to-list return conversion allocates list storage and copies elements; its result is not a promise of contiguous raw bytes.

Pitfalls​

xs.remove(i) is O(n)​

Shifts every later element. For O(1) removal that doesn't preserve order, use .swap_remove(i).

map[&k] panics on missing​

Use .get(&k) and match/? instead of map[&k] in production code.

Iterator invalidation​

Mutating a List/Map invalidates borrows into it:

let first = xs.first();               // &T
xs.push(value);                       // COMPILE ERROR: &xs active

Move the borrow out of scope, or restructure.

Don't clone() a collection to read​

// Wrong — clones the whole thing:
for x in xs.clone() { ... }

// Right:
for x in &xs { ... }

See also​