Maps | Atoll Book

Map[K, V] is a hash map: an unordered association from keys to values with average constant-time lookup, insertion, and removal.

fn main(): void {
    mut ports: Map[string, int] = Map.new()
    ports.put("http", 80)
    ports.put("https", 443)

    println("${ports.size()} entries")
    println("https -> ${ports.get("https") ?? 0}")
}

Three things in that snippet are load-bearing and worth stating up front:

the binding is mut, because put takes mut self;
the annotation Map[string, int] is what tells Map.new() which map to build — Map.new() on its own has nothing to infer from;
get returns int?, not int, so it needs ?? 0 (or a match) to become a plain value.

Construction

Map.new(capacity) allocates an empty map; the capacity argument defaults to 0 and is only an allocation hint. Map.copy(other, capacity) produces an independent table with the same entries.

fn main(): void {
    // Element types from the annotation.
    mut a: Map[string, int] = Map.new()

    // Element types from explicit type arguments, plus a capacity hint.
    mut b := Map.new[string, int](64)
    b.put("x", 1)

    // An independent table — mutating `c` does not touch `b`.
    mut c := Map.copy(b)
    c.put("y", 2)

    println("${a.size()} ${b.size()} ${c.size()}")
}

Map[K, V] is a handle to heap storage. Assigning the handle to another binding or passing it to a function shares the same table; only Map.copy gives you a table you can mutate in isolation.

There is no map literal syntax. { "a": 1 } is not a map — braces at expression position build an anonymous record, and a colon there is a parse error:

fn main(): void {
    m := { "a": 1, "b": 2 }
    println("${m}")
}

Build maps with put in a loop, or with the List collectors described in Building a map from a list.

Lookup

get(key) returns V?. Every read is total: a missing key yields None rather than trapping.

fn main(): void {
    mut ports: Map[string, int] = Map.new()
    ports.put("http", 80)

    // Four ways to discharge the Option.
    a := ports.get("http") ?? 0
    b := ports.get("http").unwrap_or(0)
    c := ports.get_or_default("ftp", 21)
    d := ports.get_or_else("ssh", () => 22)

    println("${a} ${b} ${c} ${d}")

    match ports.get("gopher") {
        Some(port) => println("configured on ${port}")
        None => println("not configured")
    }
}

get_or_default evaluates its fallback eagerly; get_or_else calls the closure only when the key is absent. Use get_or_else when the fallback allocates or does real work.

Forgetting that get is optional is the most common mistake:

fn main(): void {
    mut ports: Map[string, int] = Map.new()
    ports.put("http", 80)
    port: int = ports.get("http")
    println("${port}")
}

That reports ATOLL2002: expected int, found int?.

Membership tests avoid the Option entirely. contains_key needs K: Hashable; contains_value scans and needs V: Equatable.

fn main(): void {
    mut ports: Map[string, int] = Map.new()
    ports.put("http", 80)

    println("${ports.contains_key("http")}")   // O(1)
    println("${ports.contains_value(80)}")     // O(n) — scans every value
    println("${ports.is_empty()} ${ports.is_not_empty()}")
    println("${ports.size()} ${ports.len()}")  // len() is an alias for size()
}

A map is not indexable. m[key] is rejected — use get:

fn main(): void {
    mut ports: Map[string, int] = Map.new()
    ports.put("http", 80)
    println("${ports["http"]}")
}

Mutation

put inserts or replaces, remove returns the removed V?, and clear empties the table while keeping its allocation.

fn main(): void {
    mut inventory: Map[string, int] = Map.new()
    inventory.put("bolt", 10)
    inventory.put("nut", 4)

    // Replacing a key does not grow the map.
    inventory.put("bolt", 12)
    println("${inventory.size()}")   // 2

    match inventory.remove("nut") {
        Some(count) => println("removed ${count} nuts")
        None => println("no nuts to remove")
    }

    inventory.clear()
    println("${inventory.is_empty()}")
}

Read-modify-write on one key is get_or_default plus put. This is the counting idiom:

fn tally(words: []string): Map[string, int] {
    mut counts: Map[string, int] = Map.new()
    for word in words {
        counts.put(word, counts.get_or_default(word, 0) + 1)
    }
    return counts
}

fn main(): void {
    counts := tally(["fig", "date", "fig", "fig", "date"])
    println("fig=${counts.get_or_default("fig", 0)}")
    println("date=${counts.get_or_default("date", 0)}")
    println("kiwi=${counts.get_or_default("kiwi", 0)}")
}

Non-mutating updates

plus, plus_all, minus, and merge leave the receiver untouched and return a new map. merge resolves a duplicate key with the supplied function and copies non-conflicting entries from both sides.

fn main(): void {
    mut defaults: Map[string, int] = Map.new()
    defaults.put("retries", 3)
    defaults.put("timeout_ms", 1000)

    mut overrides: Map[string, int] = Map.new()
    overrides.put("timeout_ms", 250)
    overrides.put("workers", 8)

    // Right side wins on a conflict.
    effective := defaults.merge(overrides, (mine, theirs) => theirs)
    println("timeout_ms=${effective.get_or_default("timeout_ms", 0)}")
    println("retries=${effective.get_or_default("retries", 0)}")
    println("workers=${effective.get_or_default("workers", 0)}")

    // `defaults` is unchanged.
    println("${defaults.size()} ${effective.size()}")

    with_extra := defaults.plus("verbose", 1)
    without := defaults.minus("retries")
    combined := defaults.plus_all(overrides)
    println("${with_extra.size()} ${without.size()} ${combined.size()}")
}

Iteration

for key, value in map destructures each entry.

fn main(): void {
    mut ports: Map[string, int] = Map.new()
    ports.put("http", 80)
    ports.put("https", 443)

    for name, port in ports {
        println("${name} -> ${port}")
    }
}

Iteration order is a property of the hash table and is not specified. Never let it drive user-visible output. When order matters, take a key list and sort it:

fn main(): void {
    mut ports: Map[string, int] = Map.new()
    ports.put("https", 443)
    ports.put("http", 80)
    ports.put("ssh", 22)

    for name in ports.keys().to_list().sorted() {
        println("${name} = ${ports.get_or_default(name, 0)}")
    }
}

Views versus iterators

keys(), values(), and entries() build complete collections — Set[K], []V, and Set[(K, V)] respectively. iter_keys(), iter_values(), and iter_entries() are one-pass cursors that allocate nothing.

fn main(): void {
    mut scores: Map[string, int] = Map.new()
    scores.put("ada", 91)
    scores.put("grace", 97)

    // Materialized views.
    names: Set[string] = scores.keys()
    points: []int = scores.values()
    println("${names.size()} names, ${points.len()} points")

    // Streaming cursors — no intermediate collection.
    mut running := 0
    for value in scores.iter_values() {
        running = running + value
    }
    println("total ${running}")

    for entry in scores.iter_entries() {
        println("${entry.0} scored ${entry.1}")
    }
}

An entry from entries() or iter_entries() is a (K, V) tuple; reach its parts with .0 and .1.

for_each_entry takes a callback, and try_for_each_entry stops early when the callback returns false:

fn main(): void {
    mut scores: Map[string, int] = Map.new()
    scores.put("ada", 91)
    scores.put("grace", 97)

    scores.for_each_entry((name, points) => println("${name}: ${points}"))

    all_passing := scores.try_for_each_entry((name, points) => points >= 60)
    println("everyone passing: ${all_passing}")
}

Transformation

Every transformation returns a fresh collection and leaves the receiver alone. The shapes differ, so the return type is what to memorise:

fn main(): void {
    mut prices: Map[string, int] = Map.new()
    prices.put("apple", 120)
    prices.put("pear", 240)

    lines: []string = prices.map((name, cents) => "${name}=${cents}")
    upper: Map[string, int] = prices.map_keys((name, cents) => name.to_upper_ascii())
    dollars: Map[string, float] = prices.map_values((name, cents) => cents.to_float() / 100.0)
    cheap: Map[string, int] = prices.filter((name, cents) => cents < 200)
    short: Map[string, int] = prices.filter_keys(name => name.len() <= 4)
    round: Map[string, int] = prices.filter_values(cents => cents % 100 == 0)
    spread: []string = prices.flat_map((name, cents) => [name, "${cents}"])
    total: int = prices.reduce(0, (acc, name, cents) => acc + cents)

    println("${lines.len()} ${upper.size()} ${dollars.size()}")
    println("${cheap.size()} ${short.size()} ${round.size()}")
    println("${spread.len()} ${total}")
}

map collapses each entry to one element of a []R — it does not produce a map. map_keys and map_values keep the map shape. If map_keys produces a duplicate key, the later entry replaces the earlier one and the result is smaller than the input.

Predicates and searches:

fn main(): void {
    mut stock: Map[string, int] = Map.new()
    stock.put("bolt", 10)
    stock.put("nut", 0)

    println("${stock.any((item, n) => n == 0)}")    // short-circuits
    println("${stock.all((item, n) => n >= 0)}")    // short-circuits
    println("${stock.none((item, n) => n < 0)}")    // short-circuits
    println("${stock.count((item, n) => n > 0)}")   // visits every entry

    match stock.find((item, n) => n == 0) {
        Some(entry) => println("out of stock: ${entry.0}")
        None => println("everything in stock")
    }
}

find returns (K, V)? and picks an arbitrary match under hash order — do not use it to choose between several matching entries.

Building a map from a list

associate_by(f) keys each element by the callback and is the shortest way to build an index. The other two shapes — an entry per element with both sides computed, and one bucket per key — are put loops:

struct Task { id: int, owner: string, done: bool }

fn main(): void {
    tasks := [
        Task { id: 1, owner: "ada", done: true },
        Task { id: 2, owner: "grace", done: false },
        Task { id: 3, owner: "ada", done: false },
    ]

    // One entry per element, keyed by the callback.
    by_id: Map[int, Task] = tasks.associate_by(t => t.id)
    println("${by_id.size()}")
    match by_id.get(2) {
        Some(t) => println("#2 belongs to ${t.owner}")
        None => println("no #2")
    }

    // Both sides of the entry.
    mut owner_of: Map[int, string] = Map.new()
    for t in tasks {
        owner_of.put(t.id, t.owner)
    }
    println("#3 belongs to ${owner_of.get_or_default(3, "?")}")

    // Buckets: one list per distinct key.
    empty: []Task = []
    mut by_owner: Map[string, []Task] = Map.new()
    for t in tasks {
        bucket := by_owner.get_or_default(t.owner, empty)
        by_owner.put(t.owner, bucket.plus(t))
    }
    println("ada has ${by_owner.get_or_default("ada", empty).len()} tasks")
}

List also declares associate(f) — returning (K, V) pairs — and group_by(f), which is exactly the bucket loop above. Both are prelude declarations with no implementation: they type-check and then fail to build with ATOLL2004. Use the loops until they land.

Keys

A key type needs Equatable and Hashable, and equal values must produce equal hash codes. @derive synthesizes both from the fields:

@derive(Equatable, Hashable)
struct Coord { x: int, y: int }

fn main(): void {
    mut grid: Map[Coord, string] = Map.new()
    grid.put(Coord { x: 0, y: 0 }, "origin")
    grid.put(Coord { x: 1, y: 0 }, "east")

    // A structurally equal key finds the same entry.
    println("${grid.get(Coord { x: 0, y: 0 }) ?? "?"}")
    println("${grid.contains_key(Coord { x: 9, y: 9 })}")
}

Write the impls by hand when the hash should ignore part of the value — for example a case-insensitive key:

struct Header { name: string, raw: string }

impl Equatable for Header {
    fn equals(self, other: Header): bool {
        return self.name.to_lower_ascii() == other.name.to_lower_ascii()
    }
}

impl Hashable for Header {
    fn hash_code(self): int {
        return self.name.to_lower_ascii().hash_code()
    }
}

fn main(): void {
    mut headers: Map[Header, string] = Map.new()
    headers.put(Header { name: "Content-Type", raw: "Content-Type" }, "text/plain")

    lookup := Header { name: "content-type", raw: "content-type" }
    println("${headers.get(lookup) ?? "missing"}")
}

equals and hash_code must agree: two values that compare equal must hash equal, or lookups will miss entries that are logically present.

Do not mutate a field that participates in a stored key’s hash. The entry stays in the table but lands in the wrong bucket and becomes unreachable by get. Immutable value types make the safest keys.

Sorted maps are declaration-only

The prelude declares SortedMap[K, V] — boundary queries (first_key, last_key), ranges (head_map, tail_map, sub_map), and nearest-key lookup (floor_key, ceiling_key) — plus Map.to_sorted_map() to build one. Every one of those methods is a bodyless declaration. Nothing constructs a SortedMap and nothing can run against one; a program that mentions it type-checks and then fails to build:

fn main(): void {
    mut releases: Map[int, string] = Map.new()
    releases.put(2019, "one")
    releases.put(2021, "two")

    // Type-checks, then fails to lower:
    //   ATOLL2004: builtin method `to_sorted_map` has no lowering path
    sorted := releases.to_sorted_map()
    println("${sorted.first_key() ?? 0}")
}

Ordered access today means sorting the keys yourself. keys().to_list() .sorted() gives a stable traversal, and boundary and nearest-key questions are a scan over that list:

fn main(): void {
    mut releases: Map[int, string] = Map.new()
    releases.put(2021, "two")
    releases.put(2019, "one")
    releases.put(2024, "three")

    years := releases.keys().to_list().sorted()
    println("first ${years.first() ?? 0}, last ${years.last() ?? 0}")

    // "At or before 2022" — the largest key that is <= 2022.
    mut floor := 0
    for y in years {
        if y <= 2022 { floor = y }
    }
    println("at or before 2022: ${floor}")

    for y in years {
        println("${y} = ${releases.get_or_default(y, "?")}")
    }
}

Equality and hashing of maps

Map equality is entry-based, not order-based: two maps holding the same entries compare equal regardless of insertion order, and their hash folds entries commutatively so a map can be a field of a derived-hashable value.

fn main(): void {
    mut left: Map[string, int] = Map.new()
    left.put("a", 1)
    left.put("b", 2)

    mut right: Map[string, int] = Map.new()
    right.put("b", 2)
    right.put("a", 1)

    println("${left.entries_match(right)}")
    println("${left.hash_code() == right.hash_code()}")
}

A worked example

An in-memory index that answers three questions about a set of documents: which tags exist, how many documents carry each one, and which documents carry a given tag.

struct Document { id: int, title: string, tags: []string }

struct DocIndex {
    by_id: Map[int, Document]
    tag_counts: Map[string, int]
    tag_members: Map[string, []int]
}

fn build_index(docs: []Document): DocIndex {
    mut by_id: Map[int, Document] = Map.new()
    mut tag_counts: Map[string, int] = Map.new()
    mut tag_members: Map[string, []int] = Map.new()

    empty: []int = []
    for doc in docs {
        by_id.put(doc.id, doc)
        for tag in doc.tags {
            tag_counts.put(tag, tag_counts.get_or_default(tag, 0) + 1)
            members := tag_members.get_or_default(tag, empty)
            tag_members.put(tag, members.plus(doc.id))
        }
    }

    return DocIndex { by_id: by_id, tag_counts: tag_counts, tag_members: tag_members }
}

fn report(index: DocIndex): void {
    empty: []int = []
    for tag in index.tag_counts.keys().to_list().sorted() {
        count := index.tag_counts.get_or_default(tag, 0)
        ids := index.tag_members.get_or_default(tag, empty)
        println("${tag}: ${count} document(s)")
        for id in ids {
            match index.by_id.get(id) {
                Some(doc) => println("  #${doc.id} ${doc.title}")
                None => println("  #${id} <missing>")
            }
        }
    }
}

fn main(): void {
    docs := [
        Document { id: 1, title: "Arena layout", tags: ["memory", "runtime"] },
        Document { id: 2, title: "Effect rows", tags: ["types"] },
        Document { id: 3, title: "Green threads", tags: ["runtime"] },
    ]
    report(build_index(docs))
}

Everything user-visible in that program is sorted before it is printed; the maps themselves are only ever asked for membership and counts.