Skip to main content

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​

dictionaryEmpty​

dictionaryEmpty :: Dictionary(k, v).

dictionarySingleton​

dictionarySingleton :: k -> v -> Dictionary(k, v).

dictionaryFromList​

dictionaryFromList :: @{Eq(k)}: [(k, v)] -> Dictionary(k, v).

Inserts pairs from left to right. A duplicate key keeps its first position and its last value. Construction is O(n²) worst case.

dictionaryToList​

dictionaryToList :: Dictionary(k, v) -> [(k, v)].

Returns key-value pairs in insertion order. This is O(1) at the API boundary.

Size and lookup​

dictionarySize​

dictionarySize :: Dictionary(k, v) -> Int.

dictionaryIsEmpty​

dictionaryIsEmpty :: Dictionary(k, v) -> Bool.

dictionaryLookup​

dictionaryLookup :: @{Eq(k)}: Dictionary(k, v) -> k -> Maybe(v).

Returns the associated value as Just, or Nothing when the key is absent. Lookup is O(n) worst case.

dictionaryGetOr​

dictionaryGetOr :: @{Eq(k)}: Dictionary(k, v) -> k -> v -> v.

Returns the associated value, or the final fallback argument when the key is absent. Lookup is O(n) worst case.

dictionaryContainsKey​

dictionaryContainsKey :: @{Eq(k)}: Dictionary(k, v) -> k -> Bool.

Updating​

dictionaryInsert​

dictionaryInsert :: @{Eq(k)}: Dictionary(k, v) -> k -> v -> Dictionary(k, v).

Adds a new key at the end or replaces an existing value without moving its key.

dictionaryReplace​

dictionaryReplace :: @{Eq(k)}: Dictionary(k, v) -> k -> v -> Maybe(Dictionary(k, v)).

Replaces an existing value without moving its key. Returns Nothing when the key is absent. The update is O(n).

dictionaryRemove​

dictionaryRemove :: @{Eq(k)}: Dictionary(k, v) -> k -> Dictionary(k, v).

Removes the key and its value. An absent key returns an equivalent dictionary. Remaining keys retain their order. The update is O(n).

dictionaryUpdate​

dictionaryUpdate :: @{Eq(k)}: Dictionary(k, v) -> k -> (Maybe(v) -> 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​

dictionaryKeys​

dictionaryKeys :: Dictionary(k, v) -> [k].

Returns keys in insertion order in O(n).

dictionaryValues​

dictionaryValues :: Dictionary(k, v) -> [v].

Returns values in their keys' insertion order in O(n).

dictionaryMapValues​

dictionaryMapValues :: Dictionary(k, v) -> (v -> w) -> Dictionary(k, w).

Transforms every value in insertion order while preserving keys and their positions. This is O(n) plus callback work.

dictionaryFilter​

dictionaryFilter :: Dictionary(k, v) -> (k -> v -> Bool) -> Dictionary(k, v).

Keeps pairs whose predicate returns True, preserving their relative insertion order. This is O(n) plus callback work.

dictionaryFoldLeft​

dictionaryFoldLeft :: Dictionary(k, v) -> a -> (a -> k -> v -> a) -> a.

Folds pairs from earliest to latest insertion, starting with the supplied accumulator. This is O(n) plus callback work.

dictionaryFoldRight​

dictionaryFoldRight :: Dictionary(k, v) -> a -> (k -> v -> a -> a) -> a.

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 Eq-only keys.