- data Map k a
- (!) :: Ord k => Map k a -> k -> a
- (\\) :: Ord k => Map k a -> Map k a -> Map k a
- isEmpty :: Map k a -> Bool
- size :: Map k a -> Int
- member :: Ord k => k -> Map k a -> Bool
- lookup :: Ord k => k -> Map k a -> Maybe a
- find :: Ord k => k -> Map k a -> a
- findWithDefault :: Ord k => a -> k -> Map k a -> a
- empty :: Map k a
- single :: k -> a -> Map k a
- insert :: Ord k => k -> a -> Map k a -> Map k a
- insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
- insertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
- insertLookupWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
- delete :: Ord k => k -> Map k a -> Map k a
- adjust :: Ord k => (a -> a) -> k -> Map k a -> Map k a
- adjustWithKey :: Ord k => (k -> a -> a) -> k -> Map k a -> Map k a
- update :: Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a
- updateWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> Map k a
- updateLookupWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)
- union :: Ord k => Map k a -> Map k a -> Map k a
- unionWith :: Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
- unionWithKey :: Ord k => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
- unions :: Ord k => [Map k a] -> Map k a
- difference :: Ord k => Map k a -> Map k a -> Map k a
- differenceWith :: Ord k => (a -> a -> Maybe a) -> Map k a -> Map k a -> Map k a
- differenceWithKey :: Ord k => (k -> a -> a -> Maybe a) -> Map k a -> Map k a -> Map k a
- intersection :: Ord k => Map k a -> Map k a -> Map k a
- intersectionWith :: Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
- intersectionWithKey :: Ord k => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
- map :: (a -> b) -> Map k a -> Map k b
- mapWithKey :: (k -> a -> b) -> Map k a -> Map k b
- mapAccum :: (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
- mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
- fold :: (a -> b -> b) -> b -> Map k a -> b
- foldWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
- elems :: Map k a -> [a]
- keys :: Map k a -> [k]
- assocs :: Map k a -> [(k, a)]
- toList :: Map k a -> [(k, a)]
- fromList :: Ord k => [(k, a)] -> Map k a
- fromListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
- fromListWithKey :: Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
- toAscList :: Map k a -> [(k, a)]
- fromAscList :: Eq k => [(k, a)] -> Map k a
- fromAscListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a
- fromAscListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
- fromDistinctAscList :: [(k, a)] -> Map k a
- filter :: Ord k => (a -> Bool) -> Map k a -> Map k a
- filterWithKey :: Ord k => (k -> a -> Bool) -> Map k a -> Map k a
- partition :: Ord k => (a -> Bool) -> Map k a -> (Map k a, Map k a)
- partitionWithKey :: Ord k => (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
- split :: Ord k => k -> Map k a -> (Map k a, Map k a)
- splitLookup :: Ord k => k -> Map k a -> (Maybe a, Map k a, Map k a)
- subset :: (Ord k, Eq a) => Map k a -> Map k a -> Bool
- subsetBy :: Ord k => (a -> a -> Bool) -> Map k a -> Map k a -> Bool
- properSubset :: (Ord k, Eq a) => Map k a -> Map k a -> Bool
- properSubsetBy :: (Ord k, Eq a) => (a -> a -> Bool) -> Map k a -> Map k a -> Bool
- lookupIndex :: Ord k => k -> Map k a -> Maybe Int
- findIndex :: Ord k => k -> Map k a -> Int
- elemAt :: Int -> Map k a -> (k, a)
- updateAt :: (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
- deleteAt :: Int -> Map k a -> Map k a
- findMin :: Map k a -> (k, a)
- findMax :: Map k a -> (k, a)
- deleteMin :: Map k a -> Map k a
- deleteMax :: Map k a -> Map k a
- deleteFindMin :: Map k a -> ((k, a), Map k a)
- deleteFindMax :: Map k a -> ((k, a), Map k a)
- updateMin :: (a -> Maybe a) -> Map k a -> Map k a
- updateMax :: (a -> Maybe a) -> Map k a -> Map k a
- updateMinWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k a
- updateMaxWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k a
- showTree :: (Show k, Show a) => Map k a -> String
- showTreeWith :: (k -> a -> String) -> Bool -> Bool -> Map k a -> String
- valid :: Ord k => Map k a -> Bool
Map type
A Map from keys k
and values a
.
Operators
Query
find :: Ord k => k -> Map k a -> aSource
O(log n). Find the value of a key. Calls error
when the element can not be found.
findWithDefault :: Ord k => a -> k -> Map k a -> aSource
O(log n). The expression (findWithDefault def k map)
returns the value of key k
or returns def
when
the key is not in the map.
Construction
Insertion
insert :: Ord k => k -> a -> Map k a -> Map k aSource
O(log n). Insert a new key and value in the map.
insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k aSource
O(log n). Insert with a combining function.
insertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k aSource
O(log n). Insert with a combining function.
insertLookupWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)Source
O(log n). The expression (insertLookupWithKey f k x map
) is a pair where
the first element is equal to (lookup k map
) and the second element
equal to (insertWithKey f k x map
).
Delete/Update
delete :: Ord k => k -> Map k a -> Map k aSource
O(log n). Delete a key and its value from the map. When the key is not a member of the map, the original map is returned.
adjust :: Ord k => (a -> a) -> k -> Map k a -> Map k aSource
O(log n). Adjust a value at a specific key. When the key is not a member of the map, the original map is returned.
adjustWithKey :: Ord k => (k -> a -> a) -> k -> Map k a -> Map k aSource
O(log n). Adjust a value at a specific key. When the key is not a member of the map, the original map is returned.
update :: Ord k => (a -> Maybe a) -> k -> Map k a -> Map k aSource
O(log n). The expression (update f k map
) updates the value x
at k
(if it is in the map). If (f x
) is Nothing
, the element is
deleted. If it is (Just y
), the key k
is bound to the new value y
.
updateWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> Map k aSource
O(log n). The expression (update f k map
) updates the value x
at k
(if it is in the map). If (f k x
) is Nothing
, the element is
deleted. If it is (Just y
), the key k
is bound to the new value y
.
updateLookupWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)Source
O(log n). Lookup and update.
Combine
Union
union :: Ord k => Map k a -> Map k a -> Map k aSource
O(n+m).
The expression (
) takes the left-biased union of union
t1 t2t1
and t2
.
It prefers t1
when duplicate keys are encountered, ie. (union == unionWith const
).
The implementation uses the efficient hedge-union algorithm.
unionWith :: Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k aSource
O(n+m). Union with a combining function. The implementation uses the efficient hedge-union algorithm.
unionWithKey :: Ord k => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k aSource
O(n+m). Union with a combining function. The implementation uses the efficient hedge-union algorithm.
unions :: Ord k => [Map k a] -> Map k aSource
The union of a list of maps: (unions == foldl union empty
).
Difference
difference :: Ord k => Map k a -> Map k a -> Map k aSource
O(n+m). Difference of two maps. The implementation uses an efficient hedge algorithm comparable with hedge-union.
differenceWith :: Ord k => (a -> a -> Maybe a) -> Map k a -> Map k a -> Map k aSource
O(n+m). Difference with a combining function. The implementation uses an efficient hedge algorithm comparable with hedge-union.
differenceWithKey :: Ord k => (k -> a -> a -> Maybe a) -> Map k a -> Map k a -> Map k aSource
O(n+m). Difference with a combining function. When two equal keys are
encountered, the combining function is applied to the key and both values.
If it returns Nothing
, the element is discarded (proper set difference). If
it returns (Just y
), the element is updated with a new value y
.
The implementation uses an efficient hedge algorithm comparable with hedge-union.
Intersection
intersection :: Ord k => Map k a -> Map k a -> Map k aSource
O(n+m). Intersection of two maps. The values in the first
map are returned, i.e. (intersection m1 m2 == intersectionWith const m1 m2
).
intersectionWith :: Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k aSource
O(n+m). Intersection with a combining function.
intersectionWithKey :: Ord k => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k aSource
O(n+m). Intersection with a combining function.
Traversal
Map
mapWithKey :: (k -> a -> b) -> Map k a -> Map k bSource
O(n). Map a function over all values in the map.
mapAccum :: (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)Source
O(n). The function mapAccum
threads an accumulating
argument through the map in an unspecified order.
mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)Source
O(n). The function mapAccumWithKey
threads an accumulating
argument through the map in unspecified order. (= ascending pre-order)
Fold
fold :: (a -> b -> b) -> b -> Map k a -> bSource
O(n). Fold the map in an unspecified order. (= descending post-order).
foldWithKey :: (k -> a -> b -> b) -> b -> Map k a -> bSource
O(n). Fold the map in an unspecified order. (= descending post-order).
Conversion
Lists
fromList :: Ord k => [(k, a)] -> Map k aSource
O(n*log n). Build a map from a list of key/value pairs. See also fromAscList
.
fromListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map k aSource
O(n*log n). Build a map from a list of key/value pairs with a combining function. See also fromAscListWith
.
fromListWithKey :: Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k aSource
O(n*log n). Build a map from a list of key/value pairs with a combining function. See also fromAscListWithKey
.
Ordered lists
fromAscList :: Eq k => [(k, a)] -> Map k aSource
O(n). Build a map from an ascending list in linear time.
fromAscListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k aSource
O(n). Build a map from an ascending list in linear time with a combining function for equal keys.
fromAscListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k aSource
O(n). Build a map from an ascending list in linear time with a combining function for equal keys
fromDistinctAscList :: [(k, a)] -> Map k aSource
O(n). Build a map from an ascending list of distinct elements in linear time.
Filter
filter :: Ord k => (a -> Bool) -> Map k a -> Map k aSource
O(n). Filter all values that satisfy the predicate.
filterWithKey :: Ord k => (k -> a -> Bool) -> Map k a -> Map k aSource
O(n). Filter all keysvalues that satisfy the predicate.
partition :: Ord k => (a -> Bool) -> Map k a -> (Map k a, Map k a)Source
O(n). partition the map according to a predicate. The first
map contains all elements that satisfy the predicate, the second all
elements that fail the predicate. See also split
.
partitionWithKey :: Ord k => (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)Source
O(n). partition the map according to a predicate. The first
map contains all elements that satisfy the predicate, the second all
elements that fail the predicate. See also split
.
split :: Ord k => k -> Map k a -> (Map k a, Map k a)Source
O(log n). The expression (split k map
) is a pair (map1,map2)
where
the keys in map1
are smaller than k
and the keys in map2
larger than k
.
splitLookup :: Ord k => k -> Map k a -> (Maybe a, Map k a, Map k a)Source
O(log n). The expression (splitLookup k map
) splits a map just
like split
but also returns lookup k map
.
Subset
subset :: (Ord k, Eq a) => Map k a -> Map k a -> BoolSource
O(n+m).
This function is defined as (subset = subsetBy (==)
).
subsetBy :: Ord k => (a -> a -> Bool) -> Map k a -> Map k a -> BoolSource
O(n+m).
The expression (subsetBy f t1 t2
) returns True
if
all keys in t1
are in tree t2
, and when f
returns True
when
applied to their respective values. For example, the following
expressions are all True
.
subsetBy (==) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) subsetBy (<=) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) subsetBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1),('b',2)])
But the following are all False
:
subsetBy (==) (fromList [('a',2)]) (fromList [('a',1),('b',2)]) subsetBy (<) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) subsetBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1)])
properSubset :: (Ord k, Eq a) => Map k a -> Map k a -> BoolSource
O(n+m). Is this a proper subset? (ie. a subset but not equal).
Defined as (properSubset = properSubsetBy (==)
).
properSubsetBy :: (Ord k, Eq a) => (a -> a -> Bool) -> Map k a -> Map k a -> BoolSource
O(n+m). Is this a proper subset? (ie. a subset but not equal).
The expression (properSubsetBy f m1 m2
) returns True
when
m1
and m2
are not equal,
all keys in m1
are in m2
, and when f
returns True
when
applied to their respective values. For example, the following
expressions are all True
.
properSubsetBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)]) properSubsetBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
But the following are all False
:
properSubsetBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)]) properSubsetBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)]) properSubsetBy (<) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
Indexed
lookupIndex :: Ord k => k -> Map k a -> Maybe IntSource
O(log n). Lookup the index of a key. The index is a number from
0 up to, but not including, the size
of the map.
elemAt :: Int -> Map k a -> (k, a)Source
O(log n). Retrieve an element by index. Calls error
when an
invalid index is used.
updateAt :: (k -> a -> Maybe a) -> Int -> Map k a -> Map k aSource
O(log n). Update the element at index. Calls error
when an
invalid index is used.
deleteAt :: Int -> Map k a -> Map k aSource
O(log n). Delete the element at index. Defined as (deleteAt i map = updateAt (k x -> Nothing) i map
).
Min/Max
deleteFindMin :: Map k a -> ((k, a), Map k a)Source
O(log n). Delete and find the minimal element.
deleteFindMax :: Map k a -> ((k, a), Map k a)Source
O(log n). Delete and find the maximal element.
updateMinWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k aSource
O(log n). Update the minimal key
updateMaxWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k aSource
O(log n). Update the maximal key
Debugging
showTree :: (Show k, Show a) => Map k a -> StringSource
O(n). Show the tree that implements the map. The tree is shown in a compressed, hanging format.
showTreeWith :: (k -> a -> String) -> Bool -> Bool -> Map k a -> StringSource
O(n). The expression (showTreeWith showelem hang wide map
) shows
the tree that implements the map. Elements are shown using the showElem
function. If hang
is
True
, a hanging tree is shown otherwise a rotated tree is shown. If
wide
is true, an extra wide version is shown.
Map> putStrLn $ showTreeWith (\k x -> show (k,x)) True False $ fromDistinctAscList [(x,()) | x <- [1..5]] (4,()) +--(2,()) | +--(1,()) | +--(3,()) +--(5,()) Map> putStrLn $ showTreeWith (\k x -> show (k,x)) True True $ fromDistinctAscList [(x,()) | x <- [1..5]] (4,()) | +--(2,()) | | | +--(1,()) | | | +--(3,()) | +--(5,()) Map> putStrLn $ showTreeWith (\k x -> show (k,x)) False True $ fromDistinctAscList [(x,()) | x <- [1..5]] +--(5,()) | (4,()) | | +--(3,()) | | +--(2,()) | +--(1,())