HashMap

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

HashMap(k, v) is an immutable, hash-indexed key-value store. Unlike Map(k, v), no comparator is needed: key equality uses structural == and hashing uses the built-in polymorphic hash.

Performance (n entries): get / put / delete O(log₃₂ n) ≈ O(1) size / fold / keys O(n)

Key order is hash-traversal order (not insertion order, not sorted). Use OrderedMap if you need sorted iteration, or Map for comparator-derived key equality (Map is also hash-ordered).

Types

ptypeHEntryHEntry(k, v) =#

ptypeHashMapHashMap(k, v) = HamtHashMap(HEntry(k, v))#

Functions

fndeletedelete(m, key)#

Removes a key from the map. Returns the map unchanged if key is absent.

march> HashMap.has(HashMap.delete(HashMap.put(HashMap.new(), "a", 1), "a"), "a")
false

fnentriesentries(m)#

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

Examples

march> List.sort_by(HashMap.entries(HashMap.from_list([("b", 2), ("a", 1)])), fn (x, y) -> x < y)
[("a", 1), ("b", 2)]

fnfilterfilter(m : HashMap(k, v), pred : k -> v -> Bool[p]) : HashMap(k[p], v[p])#

Returns a map containing only entries where pred(key)(value) is true. pred : k -> v -> Bool (curried). Rebuilds the map by re-inserting the kept entries.

Examples

march> let fm = HashMap.from_list([("a", 1), ("b", 20), ("c", 30)])
march> List.sort_by(HashMap.keys(HashMap.filter(fm, fn k -> fn v -> v > 10)), fn (x, y) -> x < y)
["b", "c"]

The refinement checker ASSUMES that every entry of the result satisfies pred (an abstract refinement of two arguments, k -> v -> Bool[p]): a caller demanding HashMap(String, {Int | _ > 0}) of HashMap.filter(m, fn _k -> fn v -> v > 0) gets it. The body goes through entries (a list of tuples) and a curried call, which the checker cannot see into, so the fact is taken on faith and witnessed by a property test in test/stdlib/test_hash_map.march. See docs/refinement-types.md.

fnfoldfold(m : HashMap(k, v), acc : b, f : b -> k -> v -> b) : b#

Left fold over all entries. f is called as f(acc, key, value) -> new_acc. Iteration order is hash-traversal order (not sorted, not insertion order). Generic in the accumulator b, so a refinement demanded of the result is checked as an invariant of acc (see docs/refinement-types.md, "Folds").

Examples

march> HashMap.fold(HashMap.from_list([("a", 1), ("b", 2)]), 0, fn (acc, k, v) -> acc + v)
3
march> HashMap.fold(HashMap.new(), "init", fn (acc, k, v) -> acc ++ k)
"init"

fnfrom_listfrom_list(pairs)#

Builds a HashMap from a list of (key, value) pairs. Later entries overwrite earlier ones for duplicate keys.

march> HashMap.size(HashMap.from_list([("a",1),("b",2),("a",99)]))
2

fngetget(m, key)#

Returns Some(value) if key is present, or None.

march> HashMap.get(HashMap.new(), "missing")
None

fnget_orget_or(m, key, default)#

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

Examples

march> HashMap.get_or(HashMap.from_list([("a", 1)]), "a", 0)
1
march> HashMap.get_or(HashMap.from_list([("a", 1)]), "b", 0)
0

fnhashas(m, key)#

Returns true if key is present.

Examples

march> HashMap.has(HashMap.from_list([(1, "a")]), 1)
true
march> HashMap.has(HashMap.from_list([(1, "a")]), 2)
false

fnis_emptyis_empty(m)#

Returns true if the map contains no entries. O(1).

Examples

march> HashMap.is_empty(HashMap.put(HashMap.new(), "a", 1))
false
march> HashMap.is_empty(HashMap.delete(HashMap.put(HashMap.new(), "a", 1), "a"))
true

fnkeyskeys(m)#

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

Examples

march> List.sort_by(HashMap.keys(HashMap.from_list([("b", 2), ("a", 1)])), fn (x, y) -> x < y)
["a", "b"]

fnmap_valuesmap_values(m, f)#

Applies f to each value, returning a new map with the same keys. f takes the value only (not the key).

Examples

march> HashMap.get(HashMap.map_values(HashMap.from_list([("a", 2), ("b", 3)]), fn v -> v * 10), "b")
Some(30)

fnmergemerge(a, b)#

Merges two maps. When a key appears in both, the value from b takes precedence. O(n log n) in the size of b.

Examples

march> let ha = HashMap.from_list([(1, "a"), (2, "b")])
march> let hb = HashMap.from_list([(2, "B"), (3, "C")])
march> List.sort_by(HashMap.to_list(HashMap.merge(ha, hb)), fn (x, y) -> x < y)
[(1, "a"), (2, "B"), (3, "C")]

fnmerge_withmerge_with(a, b, f)#

Merges two maps with a combining function for conflicting keys. When key exists in both, value is f(val_from_a)(val_from_b); keys in only one map keep their value. f : v -> v -> v (curried).

Examples

march> let wa = HashMap.from_list([("x", 1), ("y", 2)])
march> let wb = HashMap.from_list([("y", 10), ("z", 5)])
march> List.sort_by(HashMap.to_list(HashMap.merge_with(wa, wb, fn a -> fn b -> a + b)), fn (x, y) -> x < y)
[("x", 1), ("y", 12), ("z", 5)]

fnnewnew()#

Returns an empty HashMap. No comparator needed.

march> HashMap.is_empty(HashMap.new())
true

fnputput(m, key, val)#

Inserts or replaces a key-value pair. Returns the new map.

march> HashMap.get(HashMap.put(HashMap.new(), "a", 1), "a")
Some(1)

fnsizesize(m)#

Returns the number of key-value pairs. O(n): the count is not cached, every call walks the trie.

Examples

march> HashMap.size(HashMap.new())
0
march> HashMap.size(HashMap.put(HashMap.from_list([("a", 1), ("b", 2)]), "a", 3))
2

fnto_listto_list(m)#

Converts a HashMap to a list of (key, value) pairs (hash-traversal order, not sorted; sort the result if order matters).

Examples

march> HashMap.to_list(HashMap.new())
[]
march> HashMap.to_list(HashMap.from_list([("k", 1), ("k", 2)]))
[("k", 2)]

fnupdateupdate(m, key, f)#

Updates a key using a function from Option(v) -> v. None is passed when the key is absent; Some(existing) when present. The function's return value becomes the new value for that key.

march> HashMap.get(HashMap.update(HashMap.new(), "k", fn _ -> 42), "k")
Some(42)

fnvaluesvalues(m)#

Returns all values as a list (hash-traversal order, the same order as keys).

Examples

march> List.sort_by(HashMap.values(HashMap.from_list([("b", 2), ("a", 1)])), fn (x, y) -> x < y)
[1, 2]