Collections in the standard library

Sets, deques, stacks, queues, ordered maps and priority queues, all built around a prototype value.

vlatest

The language gives you List<T> and Map<K, V>. The standard library adds the data structures those two cannot express.

Every one of these classes takes a prototype value in its constructor, which is how an empty typed collection is created, the language has no empty literal and no List<T>() call. See Standard library overview.

Set<T>

An unordered collection of unique values.

import { Set } from std.collections.set

fn main() {
    let s = Set<int>(0)
    s.add(3)
    s.add(3)
    s.add(4)
    println(s.size())            // 2
    println(s.contains(3))       // true
    println(s.remove(3))         // true
    println(s.size())            // 1
    s.clear()
    println(s.size())            // 0
}
Member Signature
add add(v: T)
contains contains(v: T) -> bool
size size() -> int
remove remove(v: T) -> bool
clear clear()
toList toList() -> List<T>

Set operations are free functions, because they take two sets and return a third:

import { Set, union, intersect, difference } from std.collections.set

fn main() {
    let a = Set<int>(0)
    a.add(1)
    a.add(2)

    let b = Set<int>(0)
    b.add(2)
    b.add(3)

    let u = union(a, b)
    let i = intersect(a, b)
    let d = difference(a, b)

    println("union {u.size()}")        // 3
    println("intersect {i.size()}")    // 1
    println("difference {d.size()}")   // 1
}
Function Signature
union union<K>(a: Set<K>, b: Set<K>) -> Set<K>
intersect intersect<K>(a: Set<K>, b: Set<K>) -> Set<K>
difference difference<K>(a: Set<K>, b: Set<K>) -> Set<K>

Stack<T> and Queue<T>

Both have the same shape. Queue is FIFO, Stack is LIFO.

import { Stack } from std.collections.stack
import { Queue } from std.collections.queue

fn main() {
    let s = Stack<int>(0)
    s.push(1)
    s.push(2)
    match (s.peek()) {
        case some(v) -> { println("stack top {v}") }   // 2
        case none -> { println("empty") }
    }
    match (s.pop()) {
        case some(v) -> { println("stack pop {v}") }   // 2
        case none -> { println("empty") }
    }

    let q = Queue<int>(0)
    q.push(1)
    q.push(2)
    match (q.pop()) {
        case some(v) -> { println("queue pop {v}") }  // 1
        case none -> { println("empty") }
    }
}
Member Signature
push push(v: T)
pop pop() -> T?
peek peek() -> T?
size size() -> int
clear clear()

Both pop and peek return T?, which is the important difference from the builtin List.pop(), which returns the element directly. Prefer these when you need a safe empty check.

Deque<T>

A double-ended queue, with a separate method per end.

import { Deque } from std.collections.deque

fn main() {
    let d = Deque<int>(0)
    d.pushBack(2)
    d.pushFront(1)
    println(d.size())            // 2

    match (d.front()) {
        case some(v) -> { println("front {v}") }   // 1
        case none -> { println("empty") }
    }
    match (d.back()) {
        case some(v) -> { println("back {v}") }    // 2
        case none -> { println("empty") }
    }
    match (d.popFront()) {
        case some(v) -> { println("popFront {v}") }  // 1
        case none -> { println("empty") }
    }
    match (d.popBack()) {
        case some(v) -> { println("popBack {v}") }   // 2
        case none -> { println("empty") }
    }
}
Member Signature
pushFront / pushBack (v: T)
popFront / popBack () -> T?
front / back () -> T?
size size() -> int
clear clear()

OrderedMap<K, V>

A map that remembers insertion order. Note the naming: it is set, not index assignment, and keyList / valueList, not keys / values.

import { OrderedMap } from std.collections.orderedmap

fn main() {
    let m = OrderedMap<string, int>("", 0)
    m.set("a", 1)
    m.set("b", 2)
    m.set("c", 3)

    println(m.size())            // 3
    println(m.has("a"))          // true

    let keys = m.keyList()
    for (k in keys) {
        print("{k} ")
    }
    println("")                  // a b c

    match (m.get("a")) {
        case some(v) -> { println("a = {v}") }
        case none -> { println("missing") }
    }

    m.remove("a")
    println(m.size())            // 2
}
Member Signature
set set(k: K, v: V) -> bool
get get(k: K) -> V?
has has(k: K) -> bool
remove remove(k: K) -> bool
keyList keyList() -> List<K>
valueList valueList() -> List<V>
size size() -> int
clear clear()

Reach for this over the builtin Map when output order matters.

PriorityQueue<T>

A binary heap. The constructor takes a prototype and a comparison function that returns true when its first argument has the higher priority.

import { PriorityQueue } from std.collections.priorityqueue

fn main() {
    let pq = PriorityQueue<int>(0, fn(a: int, b: int) -> bool { return a < b })
    pq.push(3)
    pq.push(1)
    pq.push(2)

    match (pq.pop()) {
        case some(v) -> { println("first {v}") }   // 1
        case none -> { println("empty") }
    }
    match (pq.pop()) {
        case some(v) -> { println("second {v}") }  // 2
        case none -> { println("empty") }
    }
    println("size {pq.size()}")
}
Member Signature
push push(v: T)
pop pop() -> T?
peek peek() -> T?
size size() -> int

Flip the comparison to get a max-heap: fn(a: int, b: int) -> bool { return a > b }.

std.collections.list: free functions

Helpers for the builtin List<T>:

import { sliceOf, filled, containsElem, indexOfElem } from std.collections.list

fn main() {
    let xs = [1, 2, 3, 4]

    let mid = sliceOf(xs, 1, 3, 0)
    println("slice len {len(mid)}")      // 2

    let f = filled(7, 3)
    println("first {f[0]} len {len(f)}") // 7 3

    println(containsElem(xs, 3))         // true
    println(indexOfElem(xs, 3))          // 2
}
Function Signature
sliceOf sliceOf<T>(xs: List<T>, lo: int, hi: int, proto: T) -> List<T>
filled filled<T>(proto: T, count: int) -> List<T>
containsElem containsElem<T>(xs: List<T>, v: T) -> bool
indexOfElem indexOfElem<T>(xs: List<T>, v: T) -> int

sliceOf and filled take a prototype for exactly the empty-result case, a zero-length slice, or filled with a count of zero.

Choosing a structure

Need Use
Ordered sequence, indexable List<T>
Key lookup Map<K, V>
Key lookup in insertion order OrderedMap<K, V>
Uniqueness Set<T>
Last in, first out Stack<T>
First in, first out Queue<T>
Both ends Deque<T>
Smallest / largest first PriorityQueue<T>

Next steps