Map

Map module: persistent hash-array-mapped-trie map.

Map(k, v) is an immutable, hash-indexed key-value store backed by a HAMT (Hash Array Mapped Trie). Lookup, insert, and delete are O(log₃₂ n) ≈ O(1) amortized. The HAMT provides excellent structural sharing under Perceus reference counting (path-copy only touches 1–7 nodes per update).

Operations that need key identity take an explicit comparator: cmp : k -> k -> Bool where cmp(a)(b) = true means a < b

Equality between keys is derived from the comparator: eq(a, b) = not cmp(a)(b) and not cmp(b)(a)

Standard comparators: fn(a) -> fn(b) -> a < b for Int keys fn(a) -> fn(b) -> a < b for String keys (lexicographic)

Iteration order is hash-traversal order (not sorted by key). Use to_list then sort externally if sorted order is needed.

Performance (n entries): Lookup / insert / delete O(log₃₂ n) ≈ O(1) size O(n) Traversals (fold / keys) O(n)

Types

ptypeMapMap(k, v) = HamtMap(HEntry(k, v))#

ptypeHEntryHEntry(k, v) =#

Functions

fnemptyempty()#

Returns an empty map.

fnsingletonsingleton(k, v)#

Returns a map containing exactly one key-value pair.

fnis_emptyis_empty(m)#

Returns true if the map contains no entries.

fnsizesize(m)#

Returns the number of key-value pairs in the map. O(n).

fngetget(m, key, cmp)#

Returns Some(value) if key is present, or None. cmp : k -> k -> Bool where cmp(a)(b) = true means a < b.

fnget_orget_or(m, key, default, cmp)#

Returns the value for key, or default if the key is absent.

fncontains_keycontains_key(m, key, cmp)#

Returns true if key is present in the map.

fninsertinsert(m, key, val, cmp)#

Inserts or updates a key-value pair. Returns the new map. If the key is already present its value is replaced. cmp : k -> k -> Bool where cmp(a)(b) = true means a < b.

fnremoveremove(m, key, cmp)#

Removes a key from the map. Returns the map unchanged if the key is absent. cmp : k -> k -> Bool where cmp(a)(b) = true means a < b.

fnfoldfold(acc, m, f)#

Left fold over all entries. f is curried: fn acc -> fn key -> fn val -> new_acc

fnkeyskeys(m)#

Returns all keys as a list (hash-traversal order).

fnvaluesvalues(m)#

Returns all values as a list (hash-traversal order).

fnentriesentries(m)#

Returns all (key, value) pairs as a list (hash-traversal order).

fnfrom_listfrom_list(pairs, cmp)#

Builds a map from a list of (key, value) pairs. Later entries overwrite earlier ones for duplicate keys. cmp : k -> k -> Bool where cmp(a)(b) = true means a < b.

fnto_listto_list(m)#

Converts a map to a list of (key, value) pairs (hash-traversal order).

fnmap_valuesmap_values(m, f)#

Applies f to each value, returning a new map with the same keys.

fnfilterfilter(m, pred, cmp)#

Returns a map containing only entries where pred(key)(value) is true. cmp : k -> k -> Bool where cmp(a)(b) = true means a < b. pred : k -> v -> Bool (curried).

fnmergemerge(a, b, cmp)#

Merges two maps. When a key appears in both maps, the value from b takes precedence. O(n log n) in the size of b. cmp : k -> k -> Bool where cmp(a)(b) = true means a < b.

fnmerge_withmerge_with(a, b, f, cmp)#

Merges two maps with a combining function for conflicting keys. merge_with(a, b, f, cmp): when key exists in both, value = f(val_a)(val_b). cmp : k -> k -> Bool; f : v -> v -> v (curried).