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
singleton
fromList
Inserts pairs from left to right. The last value for a duplicate key wins.
Construction is O(n log n).
toList
Returns pairs in ascending key order in O(n).
Size and lookup
size
isEmpty
lookup
Returns the associated value as Just, or Nothing when absent. Lookup is
O(log n).
getOr
Returns the associated value, or the final fallback argument when absent.
Lookup is O(log n).
containsKey
Updating
insert
Adds a key or replaces its value.
replace
Replaces an existing value and returns the new map as Just. An absent key
returns Nothing. This is O(log n).
remove
Removes a key when present. An absent key returns an equivalent map. This is
O(log n).
update
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
Returns the least key and its value, or Nothing for an empty map. This is
O(log n).
maximum
Returns the greatest key and its value, or Nothing for an empty map. This is
O(log n).
popMinimum
Returns the least pair and a map without it, or Nothing when empty. This is
O(log n).
popMaximum
Returns the greatest pair and a map without it, or Nothing when empty. This
is O(log n).
Views and traversal
keys
Returns keys in ascending order in O(n).
values
Returns values in ascending key order in O(n).
mapValues
Transforms values in ascending key order while preserving keys and tree shape.
This is O(n) plus callback work.
filter
Keeps pairs whose predicate returns True. Callbacks run in ascending key
order. Rebuilding the result is O(n log n) worst case.
foldLeft
Folds pairs from least to greatest key in O(n) plus callback work.
foldRight
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.