Dictionary
Import Dictionary for an insertion-ordered association structure whose keys
require equality but not ordering. The representation and constructor are
private; every update returns a new dictionary. Basic shape operations are
O(1); key lookup and update are O(n) worst case.
Type
Dictionary
Dictionary(k, v) associates keys of type k with values of type v and
preserves the insertion position of each key.
Construction
empty
singleton
fromList
Inserts pairs from left to right. A duplicate key keeps its first position and
its last value. Construction is O(n²) worst case.
toList
Returns key-value pairs in insertion order. This is O(1) at the API boundary.
Size and lookup
size
isEmpty
lookup
Returns the associated value as Just, or Nothing when the key is absent.
Lookup is O(n) worst case.
getOr
Returns the associated value, or the final fallback argument when the key is
absent. Lookup is O(n) worst case.
containsKey
Updating
insert
Adds a new key at the end or replaces an existing value without moving its key.
replace
Replaces an existing value without moving its key. Returns Nothing when the
key is absent. The update is O(n).
remove
Removes the key and its value. An absent key returns an equivalent dictionary.
Remaining keys retain their order. The update is O(n).
update
update :: @{Equatable(k)}: Dictionary(k, v) -> k -> (Maybe::Maybe(v) -> Maybe::Maybe(v)) -> Dictionary(k, v).
Calls the function with the current value as Just, or Nothing when absent.
Returning Nothing removes an existing key; returning Just replaces it or
appends a new key. The update is O(n) plus callback work.
Views and traversal
keys
Returns keys in insertion order in O(n).
values
Returns values in their keys' insertion order in O(n).
mapValues
Transforms every value in insertion order while preserving keys and their
positions. This is O(n) plus callback work.
filter
Keeps pairs whose predicate returns True, preserving their relative insertion
order. This is O(n) plus callback work.
foldLeft
Folds pairs from earliest to latest insertion, starting with the supplied
accumulator. This is O(n) plus callback work.
foldRight
Folds pairs from latest to earliest insertion, starting with the supplied
terminal value. This is O(n) plus callback work.
Use Map when ascending key order and logarithmic lookup matter more
than insertion order and Equatable-only keys.
Generic methods
Importing Dictionary supplies Mappable and Reducible for Dictionary(key). Generic callbacks see values, preserve keys, and traverse in insertion order. These instances need no key equality evidence.