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

fncontains_keycontains_key(m, key, cmp) : {Bool | _ == member(key, keys(m))}#

fnemptyempty() : {Map(k, v) | keys(_) == empty}#

fnentriesentries(m)#

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

fnfilterfilter(m, pred, cmp) : {Map(k, v) | subset(keys(_), keys(m))}#

fnfoldfold(m, acc, f)#

Left fold over all entries. Argument order: collection first, init second, callback last (uncurried-collection convention). The callback f is called uncurried as f(acc, key, val) = new_acc.

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.

fnfrom_list_intfrom_list_int(pairs)#

Build a Map(Int, v) from a list of pairs using the default Int comparator. Equivalent to Map.from_list(pairs, Map.int_cmp).

fnfrom_list_stringfrom_list_string(pairs)#

Build a Map(String, v) from a list of pairs using the default String comparator. Equivalent to Map.from_list(pairs, Map.str_cmp).

fngetget(m, key, cmp) : {Option(v) | is_Some(_) == member(key, keys(m))}#

fnget_orget_or(m, key, default, cmp)#

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

fninsertinsert(m, key, val, cmp) : {Map(k, v) | keys(_) == union(keys(m), singleton(key))}#

fnint_cmpint_cmp(a) do fn b -> a < b end#

Curried less-than comparator for Int keys. Pass to Map.* functions.

fnis_emptyis_empty(m) : {Bool | _ == (keys(m) == empty)}#

fnkeyskeys(m) : {List(k) | elts(_) == keys(m)}#

fnmap_valuesmap_values(m, f) : {Map(k, w) | keys(_) == keys(m)}#

fnmergemerge(a, b, cmp) : {Map(k, v) | keys(_) == union(keys(a), keys(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).

fnremoveremove(m, key, cmp) : {Map(k, v) | keys(_) == diff(keys(m), singleton(key))}#

fnsingletonsingleton(k, v) : {Map(k, v) | keys(_) == singleton(k)}#

fnsizesize(m)#

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

fnstr_cmpstr_cmp(a) do fn b -> a < b end#

Curried less-than comparator for String keys. Pass to Map.* functions.

fnto_listto_list(m)#

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

fnvaluesvalues(m)#

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