Map — ordered, immutable finite maps
Synopsis
data Map k v = Tip | Bin Nat k v (Map k v) (Map k v)
A finite map from keys to values. Keys are ordered by their Ord instance, and the map is kept balanced (a weight-balanced binary search tree, in the style of Haskell's Data.Map and Idris's Data.SortedMap), so lookup, insert and delete are O(log n). Iteration (toList, keys, folds, show) is always in ascending key order, so it is deterministic — a map prints and compares the same however it was built.
The number of entries is cached in each node, so size is O(1) and balancing needs no recounting. INVARIANT (maintained by the API; please don't build Bin nodes by hand): in Bin _ k _ l r every key in l is < k, every key in r is > k, and size l and size r differ by at most a constant factor.
size : Map k v -> Nat
Cached node count (O(1)).
empty : Map k v
singleton : k -> v -> Map k v
A map with a single entry.
isEmpty : Map k v -> Bool
True if the map has no entries.
lookup : Ord k => k -> Map k v -> Maybe v
Look up the value at a key. Total: Nothing when the key is absent.
member : Ord k => k -> Map k v -> Bool
True if the key has an entry.
findWithDefault : Ord k => v -> k -> Map k v -> v
The value at a key, or a supplied default when the key is absent.
(!) : Ord k => Map k v -> k -> Maybe v
Safe subscript m[k]? — Nothing if the key is absent.
index : Ord k => Map k v -> k -> v
Direct subscript m[k] — panics if the key is absent.
set : Ord k => Map k v -> k -> v -> Map k v
Indexed update m { [k] := v } — insert/replace the value at k.
insert : Ord k => k -> v -> Map k v -> Map k v
Insert a key/value pair. If the key is already present its value is replaced.
insertWith : Ord k => (v -> v -> v) -> k -> v -> Map k v -> Map k v
Insert with a combining function. If the key is already present, store f newValue oldValue; otherwise insert newValue.
adjust : Ord k => (v -> v) -> k -> Map k v -> Map k v
Apply a function to the value at a key, if present (structure unchanged).
delete : Ord k => k -> Map k v -> Map k v
Remove a key (a no-op if absent).
toList : Map k v -> List (k, v)
All entries as a list of pairs, in ascending key order.
keys : Map k v -> List k
values : Map k v -> List v
The values, ordered by their keys.
fromList : Ord k => List (k, v) -> Map k v
Build a map from a list of pairs. If a key occurs more than once, the last occurrence wins (consistent with repeated insert).
map : (v -> w) -> Map k v -> Map k w
Apply a function to every value (keys and shape unchanged).
mapWithKey : (k -> v -> w) -> Map k v -> Map k w
Apply a function to every value, with access to the key.
foldr : (v -> b -> b) -> b -> Map k v -> b
Fold over the values in ascending key order.
foldl : (b -> v -> b) -> b -> Map k v -> b
Left fold over the values in ascending key order.
foldrWithKey : (k -> v -> b -> b) -> b -> Map k v -> b
Fold over entries (key and value) in ascending key order.
filterWithKey : Ord k => (k -> v -> Bool) -> Map k v -> Map k v
Keep only the entries whose key/value satisfy the predicate.
filter : Ord k => (v -> Bool) -> Map k v -> Map k v
Keep only the entries whose value satisfies the predicate.
unionWith : Ord k => (v -> v -> v) -> Map k v -> Map k v -> Map k v
Union with a combining function. On a shared key the result holds f leftValue rightValue.
union : Ord k => Map k v -> Map k v -> Map k v
Left-biased union: keep the left map's value on a shared key.
intersectionWith : Ord k => (a -> b -> c) -> Map k a -> Map k b -> Map k c
Intersection with a combining function: keys present in both, value f leftValue rightValue.
intersection : Ord k => Map k a -> Map k b -> Map k a
Left-biased intersection: keys in both, the left map's value.
difference : Ord k => Map k a -> Map k b -> Map k a
The entries of the left map whose key is not in the right map.