Module imm/map
Persistent immutable hash map using a Hash Array Mapped Trie (HAMT).
Map(K, V) is an immutable hash map backed by atomic object nodes for
thread-safe structural sharing. All mutations return new maps, leaving the
original unchanged.
Keys must implement Eq, Hash, Send and Sync. Values must implement Send and Sync.
Cycle safety
Map nodes use ATOMIC reference counting, and the cycle collector does not
scan atomic objects (the Arc pattern) — so, like Arc(V), keys and
values must be Acyclic (plans/archive/STD_API_AUDIT.md O7, landed 2026-08-27).
Structurally-acyclic types satisfy the bound automatically; a
self-referential type is rejected at instantiation.
Examples
{ Map } :: import("std/imm/map");
m := Map(i32, i32).new();
m = m.insert(i32(1), i32(100));
m = m.insert(i32(2), i32(200));
assert(m.get(i32(1)).unwrap() == i32(100), "key 1 maps to 100");
assert(m.len() == usize(2), "two entries");
Insert, lookup and remove are O(log32 n) — five levels of 32-way branching
covers 33 million keys — and every mutation copies only the nodes on the
path it touched, so the original map and the new one share everything else.
Iteration (keys/values/entries, and the IntoIterator behind
for(map, ...)) MATERIALIZES an imm.List of the entries first: O(n) time
and O(n) allocation, in trie order, not a lazy cursor.
Stability
unstable — plans/archive/STD_API_STABILIZATION.md §4 keeps one shape open across
the imm containers, and this is its clearest case: remove(key) -> Self
cannot tell a caller whether the key was there, where the mutable
HashMap.remove answers Option(V). Deciding that (a second
remove_entry-style spelling, or a RemoveResult-shaped return) changes
this signature. The lazy-cursor iteration above is the other known gap,
but that one is an optimization rather than a surface change.
Types
Persistent immutable hash map.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
Trait Implementations
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash, Send, Sync, Acyclic), V <: (Send, Sync, Acyclic)), Map(K, V), Acyclic())
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash, Send, Sync, Acyclic), V <: (Send, Sync, Acyclic)), Map(K, V), ...)
new : (fn() -> Self)Create an empty map.
Returns: Self
len : (fn(self : Self) -> usize)Number of key-value entries.
Returns: usize
is_empty : (fn(self : Self) -> bool)Check if the map is empty.
Returns: bool
get : (fn(self : Self, key : K) -> Option(V))Look up the value associated with key.
Returns: Option(V)
contains_key : (fn(self : Self, key : K) -> bool)Check if the map contains key.
Returns: bool
insert : (fn(self : Self, key : K, value : V) -> Self)Return a new map with key mapped to value.
Returns: Self
remove : (fn(self : Self, key : K) -> Self)Return a new map without key — im's without. A key that is not
present gives back self itself, not a copy.
This deliberately does NOT report what it removed; extract is the form
that does.
Returns: Self
extract : (fn(self : Self, key : K) -> Option(Tuple(V, Self)))The value at key together with the map WITHOUT it, or .None when
the key is absent — im's extract.
This exists because remove answers only "the map afterwards", so a
caller who wants the removed value had to look it up first and could not
tell "absent" from "removed a value that happens to equal the default".
The .None arm carries no map, which is the point: on a miss the
caller's own self already IS the answer, so nothing is rebuilt.
TWO walks of the trie, not one. im's extract is one walk because
Rust can move the value out of the node it visits; threading the value
out of _node_remove here would make every remove — the common case —
carry and then drop a value it does not want. A HAMT walk is
⌈log₃₂ n⌉ levels (2 for a million entries), so the second walk is a
smaller cost than the refcount traffic on the first.
Returns: Option(Tuple(V, Self))
merge : (fn(self : Self, other : Self) -> Self)Merge another map into this one. Keys from other overwrite self.
Returns: Self
keys : (fn(self : Self) -> List(K))Collect all keys into a list.
Returns: List(K)
values : (fn(self : Self) -> List(V))Collect all values into a list.
Returns: List(V)
entries : (fn(self : Self) -> List(MapEntry(K, V)))map_values : (fn(generic(U : Type), self : Self, f : Impl(Fn(a : V) -> U), where(U <: (Send, Sync, Acyclic))) -> Map(K, U))Apply a function to each value, producing a new map.
Returns: Map(K, U)
filter : (fn(self : Self, f : Impl(Fn(k : K, v : V) -> bool)) -> Self)Keep only entries where the predicate returns true.
Returns: Self
from_entries : (fn(pairs : ArrayList(MapEntry(K, V))) -> Self)Create a map from a slice of key-value pairs.
Returns: Self
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash, Send, Sync, Acyclic), V <: (Send, Sync, Acyclic, Eq(V))), Map(K, V), Eq(Map(K, V))(...))
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash, Send, Sync, Acyclic), V <: (Send, Sync, Acyclic)), Map(K, V), IntoIterator(...))
Item : MapEntry(K, V)impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash, Send, Sync, Acyclic), V <: (Send, Sync, Acyclic)), Map(K, V), Default(...))
default : (fn() -> Self)The default value of the type.
Returns: Self