hanki

map

stdlib/core/map.hk: immutable Map<K, V> keyed by Hash.

Representation: a hash array mapped trie (HAMT). Each interior node (MBranch) is a sparse 16-way node, a u32 bitmap of occupied slots plus a list of those children alone, indexed by 4 bits of the key's hash per level; leaves hold a single entry, and same-hash keys collapse into a MCollision bucket scanned by Eq. Lookup / insert / remove are O(log16 n) and near constant for any realistic map. The trie is persistent (structural sharing): every update returns a fresh map and leaves the original intact.

Keys are bounded by Hash, whose Eq supertrait leaves == working; a key type must therefore be hashable. Iteration order (keys/values/ to_list, fold, each!, Display) is hash order, unspecified and unstable, and never insertion order. Encoding remains canonical regardless: Encode emits entries sorted by key bytes, and two ==-equal maps encode to identical bytes.

The struct is opaque: the representation is private and can change without breaking callers. Entry<K, V> is a plain public key/value pair, used by from_list / to_list.

Entry

struct Entry<K, V>
  k: K
  v: V
end

_MapNode

type _MapNode<K, V>
  MEmpty
  MLeaf(u64, K, V)
  MCollision(List<Entry<K, V>>)
  MBranch(u32, List<_MapNode<K, V>>)
end

A trie node. MLeaf records the key's remaining hash, the bits not yet consumed by the branches above it, and a leaf can therefore be re-placed on a split without rehashing. MBranch is sparse: a u32 bitmap marks which of the 16 slots are occupied, alongside a list of just the occupied children in slot order. MCollision groups keys whose full 64-bit hashes are equal.

Map

opaque Map<K, V>
  root: _MapNode<K, V>
  count: int
end

slotbit

def _slot_bit(rem: u64) -> u32

The single bit marking rem's 4-bit branch slot (slot 0..15).

branchindex

def _branch_index(bitmap: u32, slotbit: u32) -> int

The child-list index for slotbit: the population count of the occupied slots below it (bitmap & (slotbit - 1)).

_at

def _at<K, V>(kids: List<_MapNode<K, V>>, i: int) -> _MapNode<K, V>

branchkid

def _branch_kid<K, V>(bitmap: u32, kids: List<_MapNode<K, V>>, slotbit: u32) -> _MapNode<K, V>

The child stored at slotbit, or MEmpty when the slot is unoccupied.

branchset

def _branch_set<K, V>(bitmap: u32, kids: List<_MapNode<K, V>>, slotbit: u32, val: _MapNode<K, V>) -> _MapNode<K, V>

A fresh branch with slotbit's child set to val. MEmpty clears the slot, dropping the child and its bit; any other node sets it, replacing an existing child, or inserting and marking the bit when newly occupied.

putat

def _put_at<K, V>(kids: List<_MapNode<K, V>>, i: int, val: _MapNode<K, V>) -> List<_MapNode<K, V>>

kids with the child at i replaced by val. One persistent-list update (FBIP-reused when the spine is unshared) - never an element-by-element rebuild, which cost a call per child per level.

insertat

def _insert_at<K, V>(kids: List<_MapNode<K, V>>, i: int, val: _MapNode<K, V>) -> List<_MapNode<K, V>>

kids with val inserted before index i, shifting the rest right.

dropat

def _drop_at<K, V>(kids: List<_MapNode<K, V>>, i: int) -> List<_MapNode<K, V>>

kids with the child at i dropped, closing the gap.

nodeget

def _node_get<K: Hash, V>(n: _MapNode<K, V>, key: K, rem: u64) -> Option<V>

-- trie get ------------------------------------------------------------

_scan

def _scan<K: Hash, V>(es: List<Entry<K, V>>, key: K, i: int) -> Option<V>

nodecontains?

def _node_contains?<K: Hash, V>(n: _MapNode<K, V>, key: K, rem: u64) -> bool

Presence probe without the Option cell _node_get allocates. The insert/remove count bookkeeping only needs the bit.

scancontains?

def _scan_contains?<K: Hash, V>(es: List<Entry<K, V>>, key: K, i: int) -> bool

nodeinsert

def _node_insert<K: Hash, V>(n: _MapNode<K, V>, key: K, value: V, rem: u64, depth: int) -> _MapNode<K, V>

-- trie insert --------------------------------------------------------- depth counts branches descended; at depth 16 the 64-bit hash is fully consumed, and distinct keys that reach it are a true collision.

_split

def _split<K: Hash, V>(lrem: u64, lk: K, lv: V, key: K, value: V, rem: u64, depth: int) -> _MapNode<K, V>

Turn a single leaf into a branch and insert the new entry. The existing leaf moves down one level, and its remaining hash shifts by 4.

_upsert

def _upsert<K: Hash, V>(es: List<Entry<K, V>>, key: K, value: V, i: int, acc: List<Entry<K, V>>, found: bool) -> List<Entry<K, V>>

Replace key's entry in a collision bucket, or append it.

noderemove

def _node_remove<K: Hash, V>(n: _MapNode<K, V>, key: K, rem: u64) -> _MapNode<K, V>

-- trie remove --------------------------------------------------------- Removal clears the slot's bit and drops its child, but never collapses a branch back into a leaf: a branch may shrink to one child or to none. Correct and persistent; collapsing single-child branches is a later space optimisation and no behaviour change (encoding and equality are by content, never structure).

_drop

def _drop<K: Hash, V>(es: List<Entry<K, V>>, key: K, i: int, acc: List<Entry<K, V>>) -> List<Entry<K, V>>

nodekeys

def _node_keys<K, V>(n: _MapNode<K, V>, acc: List<K>) -> List<K>

-- trie walks (keys / values / to_list; all hash order) ----------------

eskeys

def _es_keys<K, V>(es: List<Entry<K, V>>, i: int, acc: List<K>) -> List<K>

kidskeys

def _kids_keys<K, V>(kids: List<_MapNode<K, V>>, i: int, acc: List<K>) -> List<K>

nodevalues

def _node_values<K, V>(n: _MapNode<K, V>, acc: List<V>) -> List<V>

esvalues

def _es_values<K, V>(es: List<Entry<K, V>>, i: int, acc: List<V>) -> List<V>

kidsvalues

def _kids_values<K, V>(kids: List<_MapNode<K, V>>, i: int, acc: List<V>) -> List<V>

nodeto_list

def _node_to_list<K, V>(n: _MapNode<K, V>, acc: List<Entry<K, V>>) -> List<Entry<K, V>>

esto_list

def _es_to_list<K, V>(es: List<Entry<K, V>>, i: int, acc: List<Entry<K, V>>) -> List<Entry<K, V>>

kidsto_list

def _kids_to_list<K, V>(kids: List<_MapNode<K, V>>, i: int, acc: List<Entry<K, V>>) -> List<Entry<K, V>>

nodefold

def _node_fold<K, V, U>(n: _MapNode<K, V>, acc: U, f: (U, K, V) -> U) -> U

-- trie fold (hash order; the public fold uses it) -------------------

esfold

def _es_fold<K, V, U>(es: List<Entry<K, V>>, acc: U, f: (U, K, V) -> U, i: int) -> U

kidsfold

def _kids_fold<K, V, U>(kids: List<_MapNode<K, V>>, acc: U, f: (U, K, V) -> U, i: int) -> U

nodeeach!

def _node_each!<K, V>(n: _MapNode<K, V>, f: (K, V) -> () [e]) -> () [e]

-- trie each! (effectful, hash order) ----------------------------------

eseach!

def _es_each!<K, V>(es: List<Entry<K, V>>, f: (K, V) -> () [e], i: int) -> () [e]

kidseach!

def _kids_each!<K, V>(kids: List<_MapNode<K, V>>, f: (K, V) -> () [e], i: int) -> () [e]

nodemap_values

def _node_map_values<K, V, W>(n: _MapNode<K, V>, f: (V) -> W) -> _MapNode<K, W>

-- trie map_values (rebuild, keys/structure preserved) -----------------

esmv

def _es_mv<K, V, W>(es: List<Entry<K, V>>, f: (V) -> W, i: int, acc: List<Entry<K, W>>) -> List<Entry<K, W>>

kidsmv

def _kids_mv<K, V, W>(kids: List<_MapNode<K, V>>, f: (V) -> W, i: int, acc: List<_MapNode<K, W>>) -> List<_MapNode<K, W>>

nodeeq?

def _node_eq?<K: Hash, V: Eq>(n: _MapNode<K, V>, other: Map<K, V>) -> bool

-- trie equality (every entry of self present-and-equal in other) --

entryeq?

def _entry_eq?<K: Hash, V: Eq>(other: Map<K, V>, k: K, v: V) -> bool

eseq?

def _es_eq?<K: Hash, V: Eq>(es: List<Entry<K, V>>, other: Map<K, V>, i: int) -> bool

kidseq?

def _kids_eq?<K: Hash, V: Eq>(kids: List<_MapNode<K, V>>, other: Map<K, V>, i: int) -> bool

insertlist

def _insert_list<K: Hash, V>(m: Map<K, V>, es: List<Entry<K, V>>) -> Map<K, V>

Inserts every entry of es into m (last write wins). Shared by from_list and merge. A counting loop (per-entry recursion would consume call stack proportional to the entry count on the AOT tier).

impl<K: Hash, V> Map<K, V>

empty

def empty() -> Map<K, V>

The empty map. Key and value types are fixed by the binding it flows into, or by the first insert.

m: Map<string, i32> = Map.empty()
m.length => 0

from_list

def from_list(entries: List<Entry<K, V>>) -> Map<K, V>

Builds a map from a list of entries; on a duplicated key the last wins.

es: List<Entry<string, i32>> = List.empty().append(Entry(k="x", v=1i32)).append(Entry(k="y", v=2i32))
m = Map.from_list(es)
m.get("y") => Some(2i32)

length

prop length(self) -> int

The number of entries.

m = Map.empty().insert("a", 1i32).insert("b", 2i32)
m.length => 2

empty?

prop empty?(self) -> bool

True when the map has no entries.

empty: Map<string, i32> = Map.empty()
empty.empty?                  => true
Map.empty().insert("a", 1i32).empty? => false

get

def get(self, key: K) -> Option<V>

The value bound to key, or None when the key is absent.

m = Map.empty().insert("a", 1i32)
m.get("a") => Some(1i32)
m.get("b") => None

contains_key?

def contains_key?(self, key: K) -> bool

True when key is present.

m = Map.empty().insert("a", 1i32)
m.contains_key?("a") => true
m.contains_key?("b") => false

keys

prop keys(self) -> List<K>

Every key, in hash order.

m = Map.empty().insert("a", 1i32).insert("b", 2i32)
m.keys.length => 2

values

prop values(self) -> List<V>

Every value, in hash order.

m = Map.empty().insert("a", 1i32).insert("b", 2i32)
m.values.length => 2

insert

def insert(self, key: K, value: V) -> Map<K, V>

A fresh map with key bound to value, replacing any existing entry; the original is unchanged.

m = Map.empty().insert("a", 1i32).insert("a", 2i32)
m.length    => 1
m.get("a") => Some(2i32)

remove

def remove(self, key: K) -> Map<K, V>

A fresh map without key (a no-op if absent); the original is unchanged.

m = Map.empty().insert("a", 1i32).insert("b", 2i32).remove("a")
m.length             => 1
m.contains_key?("a") => false

merge

def merge(self, other: Map<K, V>) -> Map<K, V>

A fresh map with other's entries laid over self's; other wins on key conflicts (right-biased).

a = Map.empty().insert("k", 1i32)
b = Map.empty().insert("k", 2i32)
a.merge(b).get("k") => Some(2i32)

each!

def each!(self, f: (K, V) -> () [e]) -> () [e]

Applies the effectful f to every key/value pair, in hash order. @no-doctest: effectful iteration returning unit

fold

def fold(self, init: U, f: (U, K, V) -> U) -> U

The left fold of f over the entries, in the same (hash) order keys() and values() walk. An empty map folds to init.

m = Map.empty().insert("a", 1i32).insert("b", 2i32)
m.fold(0i32, |acc: i32, k: string, v: i32| acc + v) => 3i32

map_values

def map_values(self, f: (V) -> W) -> Map<K, W>

A fresh map with the same keys and f applied to every value.

m = Map.empty().insert("a", 2i32)
m.map_values(|v: i32| v * 10i32).get("a") => Some(20i32)

to_list

def to_list(self) -> List<Entry<K, V>>

The entries as a list, in hash order. The inverse of Map.from_list.

m = Map.empty().insert("a", 1i32)
m.to_list().length                  => 1
Map.from_list(m.to_list()).get("a") => Some(1i32)

entrystr

def _entry_str<K: Display, V: Display>(e: Entry<K, V>) -> string

renderentries

def _render_entries<K: Display, V: Display>(es: List<Entry<K, V>>) -> string

impl<K: Hash + Display, V: Display> Display<Map<K, V>>

to_string

def to_string(self) -> string

Renders the map as {key: value, …} in key order.

@no-doctest: hash-order rendering is unspecified

impl<K: Hash, V: Eq> Eq<Map<K, V>>

eq?

def eq?(self, other: Self) -> bool

Equal where both maps have the same key-value pairs.

a = Map.empty().insert("a", 1i32).insert("b", 2i32)
b = Map.empty().insert("b", 2i32).insert("a", 1i32)
a.eq?(b) => true

entryencode!

def _entry_encode!<K: Encode, V: Encode, S: Serializer>(e: Entry<K, V>, s: S) -> ()

_KeyedEntry

struct _KeyedEntry<K, V>
  kb: bytes
  e: Entry<K, V>
end

impl<K, V> Ord<_KeyedEntry<K, V>>

cmp

def cmp(self, other: Self) -> Ordering

Total numeric order on _KeyedEntry<K.

@no-doctest: internal ordering helper for canonical Map encoding

keybytes!

def _key_bytes!<K: Encode>(k: K) -> bytes

_keyed!

def _keyed!<K: Encode, V>(entries: List<Entry<K, V>>) -> List<_KeyedEntry<K, V>>

emitsorted!

def _emit_sorted!<K: Encode, V: Encode, S: Serializer>(sorted: List<_KeyedEntry<K, V>>, s: S) -> ()

impl<K: Hash + Encode, V: Encode> Encode<Map<K, V>>

encode!

def encode!<S: Serializer>(self, s: S) -> ()

Encodes the map as its key-value entries.

@no-doctest: see the trait method in core/encode

mapdecode!

def _map_decode!<K: Hash + Decode, V: Decode, D: Deserializer>(d: D, remaining: int, acc: Map<K, V>, depth: int) -> Result<Map<K, V>, DecodeError>

impl<K: Hash + Decode, V: Decode> Decode<Map<K, V>>

decode!

def decode!<D: Deserializer>(d: D, depth: int) -> Result<Map<K, V>, DecodeError>

Decodes key-value entries back into a map.

@no-doctest: see the trait method in core/decode

_seed

def _seed(m: Map<string, int>, i: int) -> Map<string, int>

holdsseeded_pairs?

def _holds_seeded_pairs?(m: Map<string, int>, i: int) -> bool