std/dict
Dictionaries: maps from keys to values that may not be changed.
A Dict(k, v) is a hash trie. The key of every entry is hashed with
core.hash (§13), and the hash picks a path through a tree with four
branches at each level, two bits of the hash for each level. Keys are
compared with == (§11.4), so any value may be a key and no compare
function is needed. get, insert, and delete take O(log n) steps.
The tree of a set of keys has only one form, whatever order the keys
were put in. So two dicts with the same entries are ==. (The one
exception: keys with the same 32-bit hash are kept in the order they were
put in, so two such dicts may differ in that order.)
The order of keys, values, to_list, and fold comes from the
hashes. It is the same every time for the same compiled program, but
it is not sorted, and it is not fixed by this library. Sort the result
of to_list when an order is needed.
Dict
A map from keys of type k to values of type v.
Dict(K, V) = (Int, Node(K, V)) new
A dict with no entries.
new = <K, V>() -> Dict(K, V) { Dict(0, Empty) } size
The number of entries. This takes one step.
size = <K, V>(dict : Dict(K, V)) -> Int { is_empty
True when the dict has no entries.
is_empty = <K, V>(dict : Dict(K, V)) -> Bool { size(dict) == 0 } get
The value for a key, or None when the key is not in the dict.
dict.new() |> dict.insert(1, "a") |> dict.get(1) // Some("a") get = <K, V>(from : Dict(K, V), get : K) -> Option(V) { has
True when the key is in the dict.
has = <K, V>(dict : Dict(K, V), key : K) -> Bool { insert
The dict with the entry key → value. An entry with the same key is
replaced.
dict.new() |> dict.insert("a", 1) |> dict.to_list // [("a", 1)] insert = <K, V>(into : Dict(K, V), for : K, insert : V) -> Dict(K, V) { delete
The dict without the entry for a key. If the key is not there, the dict is the same.
delete = <K, V>(from : Dict(K, V), delete : K) -> Dict(K, V) { upsert
Changes the value for a key with a function, which gets Some(value)
when the key is there and None when not.
increment = (x) { x |> (Some(n)) { n + 1 } | (None) { 0 } }
dict.upsert(counts, "a", increment) upsert = <K, V, N>( update
Changes the value for a key with a function, when the key is there. If not, the dict is the same.
update = <K, V, N>(dict : Dict(K, V), in : K, with : (V) <- N -> V) -> Dict( from_list
A dict with the entries of a list of pairs. When a key is in the list more than one time, the last value is kept.
dict.from_list([("a", 1), ("b", 2)]) |> dict.get("b") // Some(2) from_list = <K, V>(list : List((K, V))) -> Dict(K, V) { to_list
The entries as a list of pairs, in the order of fold.
to_list = <K, V>(dict : Dict(K, V)) -> List((K, V)) { keys
The keys, in the order of fold.
keys = <K, V>(dict : Dict(K, V)) -> List(K) { values
The values, in the order of fold.
values = <K, V>(dict : Dict(K, V)) -> List(V) { fold
Combines every entry with an accumulator, as list.fold does. The order
of the entries is not fixed (see the module documentation).
fold = <K, V, Acc, N>( each
Calls a function with every entry, in the order of fold.
each = <K, V, A, N>(dict : Dict(K, V), with : (K, V) <- N -> A) -> Nil { map_values
Changes every value with a function of its key and value. The keys stay.
dict.from_list([(1, 2)]) |> dict.map_values((k, v) { k + v }) // {1 -> 3} map_values = <K, V, W, N>(in : Dict(K, V), with : (K, V) <- N -> W) -> Dict( filter
Keeps only the entries for which the function gives True.
filter = <K, V, N>(in : Dict(K, V), keeping : (K, V) <- N -> Bool) -> Dict( take
Keeps only the entries whose keys are in the list.
take = <K, V>(from : Dict(K, V), keeping : List(K)) -> Dict(K, V) { drop
Takes out the entries whose keys are in the list.
drop = <K, V>(from : Dict(K, V), drop : List(K)) -> Dict(K, V) { merge
All the entries of both dicts. For a key that is in both, the value of
from is kept.
dict.merge(dict.from_list([(1, "a")]), dict.from_list([(1, "b"), (2, "c")]))
// {1 -> "b", 2 -> "c"} merge = <K, V>(into : Dict(K, V), from : Dict(K, V)) -> Dict(K, V) { combine
All the entries of both dicts. For a key that is in both, the values are
put together with a function of the value of dict and the value of
other.
combine = <K, V, N>( group
Puts the values of a list into groups by a key function. Each group keeps the values in the order of the list.
dict.group([1, 2, 3, 4], (x) { x % 2 }) // {1 -> [1, 3], 0 -> [2, 4]} group = <V, K, N>(list : List(V), by : (V) <- N -> K) -> Dict(K, List(V)) {