Skip to main content

Map

Import Map for a persistent balanced search tree. Key lookup and update require Comparable(k); construction with empty or singleton and read-only traversal do not. Ordered views traverse keys in ascending order. The representation and constructor are private. Lookup and update are O(log n); full views and folds are O(n) before callback work.

Type​

Map​

Map(k, v) associates ordered keys of type k with values of type v.

Construction​

empty​

empty :: Map(k, v).

singleton​

singleton :: k -> v -> Map(k, v).

fromList​

fromList :: @{Comparable(k)}: [(k, v)] -> Map(k, v).

Inserts pairs from left to right. The last value for a duplicate key wins. Construction is O(n log n).

toList​

toList :: Map(k, v) -> [(k, v)].

Returns pairs in ascending key order in O(n).

Size and lookup​

size​

size :: Map(k, v) -> Int.

isEmpty​

isEmpty :: Map(k, v) -> Bool.

lookup​

lookup :: @{Comparable(k)}: Map(k, v) -> k -> Maybe::Maybe(v).

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

getOr​

getOr :: @{Comparable(k)}: Map(k, v) -> k -> v -> v.

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

containsKey​

containsKey :: @{Comparable(k)}: Map(k, v) -> k -> Bool.

Updating​

insert​

insert :: @{Comparable(k)}: Map(k, v) -> k -> v -> Map(k, v).

Adds a key or replaces its value.

replace​

replace :: @{Comparable(k)}: Map(k, v) -> k -> v -> Maybe::Maybe(Map(k, v)).

Replaces an existing value and returns the new map as Just. An absent key returns Nothing. This is O(log n).

remove​

remove :: @{Comparable(k)}: Map(k, v) -> k -> Map(k, v).

Removes a key when present. An absent key returns an equivalent map. This is O(log n).

update​

update :: @{Comparable(k)}: Map(k, v) -> k -> (Maybe::Maybe(v) -> Maybe::Maybe(v)) -> Map(k, v).

Calls the function with the current value as Just, or Nothing when absent. Returning Nothing removes a key; returning Just inserts or replaces it. This is O(log n) plus callback work.

Ordered boundaries​

minimum​

minimum :: Map(k, v) -> Maybe::Maybe((k, v)).

Returns the least key and its value, or Nothing for an empty map. This is O(log n).

maximum​

maximum :: Map(k, v) -> Maybe::Maybe((k, v)).

Returns the greatest key and its value, or Nothing for an empty map. This is O(log n).

popMinimum​

popMinimum :: Map(k, v) -> Maybe::Maybe(((k, v), Map(k, v))).

Returns the least pair and a map without it, or Nothing when empty. This is O(log n).

popMaximum​

popMaximum :: Map(k, v) -> Maybe::Maybe(((k, v), Map(k, v))).

Returns the greatest pair and a map without it, or Nothing when empty. This is O(log n).

Views and traversal​

keys​

keys :: Map(k, v) -> [k].

Returns keys in ascending order in O(n).

values​

values :: Map(k, v) -> [v].

Returns values in ascending key order in O(n).

mapValues​

mapValues :: Map(k, v) -> (v -> w) -> Map(k, w).

Transforms values in ascending key order while preserving keys and tree shape. This is O(n) plus callback work.

filter​

filter :: @{Comparable(k)}: Map(k, v) -> (k -> v -> Bool) -> Map(k, v).

Keeps pairs whose predicate returns True. Callbacks run in ascending key order. Rebuilding the result is O(n log n) worst case.

foldLeft​

foldLeft :: Map(k, v) -> a -> (a -> k -> v -> a) -> a.

Folds pairs from least to greatest key in O(n) plus callback work.

foldRight​

foldRight :: Map(k, v) -> a -> (k -> v -> a -> a) -> a.

Folds pairs from greatest to least key in O(n) plus callback work.

Use Dictionary when insertion order and Equatable-only keys matter more than sorted traversal and logarithmic lookup.

Generic methods​

Importing Map supplies Mappable and Reducible for Map(key). Generic callbacks see values, preserve keys, and traverse in key order. These instances need no key ordering evidence.