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)#

Returns true if key is present in the map.

fnemptyempty()#

Returns an empty map.

fnentriesentries(m)#

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

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).

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)#

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.

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.

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)#

Returns true if the map contains no entries.

fnkeyskeys(m)#

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

fnmap_valuesmap_values(m, f)#

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

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).

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.

fnsingletonsingleton(k, v)#

Returns a map containing exactly one key-value pair.

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).