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, and Send. Values must implement Send.
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/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, Acyclic), V <: (Send, Acyclic)), Map(K, V), Acyclic())
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash, Send, Acyclic), V <: (Send, 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, 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, Acyclic), V <: (Send, Acyclic, Eq(V))), Map(K, V), Eq(Map(K, V))(...))
impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash, Send, Acyclic), V <: (Send, Acyclic)), Map(K, V), IntoIterator(...))
Item : MapEntry(K, V)impl(generic(K : Type, V : Type), where(K <: (Eq(K), Hash, Send, Acyclic), V <: (Send, Acyclic)), Map(K, V), Default(...))
default : (fn() -> Self)The default value of the type.
Returns: Self
Tagged union representing a single HAMT node.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
HAMT branch node -- bitmap + compact child array.
_children_ptr is *(void) to break the circular type dependency with
MapNode. It is cast to *(MapNode(K, V)) in methods.
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, Acyclic), V <: (Send, Acyclic)), MapBranch(K, V), Dispose(...))
dispose : (fn(self : Self) -> unit)Release the resources self owns — a file descriptor, a socket, a lock,
a buffer the allocator handed out. Called automatically when the last
reference to the value goes away, so an implementor never calls it
directly and must tolerate being the only one who ever does.
It must be safe to run exactly once: the runtime calls it at refcount
zero, and a type that also exposes an explicit close/release is
responsible for making the second call a no-op.
Returns: unit
HAMT leaf node -- single key-value entry.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
HAMT collision node -- multiple entries sharing the same hash.
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, Acyclic), V <: (Send, Acyclic)), MapCollision(K, V), Dispose(...))
dispose : (fn(self : Self) -> unit)Release the resources self owns — a file descriptor, a socket, a lock,
a buffer the allocator handed out. Called automatically when the last
reference to the value goes away, so an implementor never calls it
directly and must tolerate being the only one who ever does.
It must be safe to run exactly once: the runtime calls it at refcount
zero, and a type that also exposes an explicit close/release is
responsible for making the second call a no-op.
Returns: unit
A single key/value entry in a map.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
What one step of the trie insert walk returns: the rebuilt node, plus whether the key was NEW.
The flag is what lets insert maintain len without a second lookup —
replacing an existing key must not increment it. Internal to the HAMT
walk; it is not part of the map's public surface.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |
What one step of the trie remove walk returns: the rebuilt node —
.None when the subtree collapsed to nothing — plus whether a key was
actually removed.
The Option is the collapse signal: a branch whose last child went away
must disappear rather than stay as an empty node. Internal to the HAMT
walk; Map.remove returns only the new map.
Type Parameters
| Name | Type | Notes |
|---|---|---|
K | Type | comptime |
V | Type | comptime |