Portability | portable |
---|---|
Stability | provisional |
Maintainer | libraries@haskell.org |
An efficient implementation of maps from keys to values (dictionaries).
Since many function names (but not the type name) clash with
Prelude names, this module is usually imported qualified
, e.g.
import Data.Map (Map) import qualified Data.Map as Map
The implementation of Map
is based on size balanced binary trees (or
trees of bounded balance) as described by:
- Stephen Adams, "Efficient sets: a balancing act", Journal of Functional Programming 3(4):553-562, October 1993, http://www.swiss.ai.mit.edu/~adams/BB.
- J. Nievergelt and E.M. Reingold, "Binary search trees of bounded balance", SIAM journal of computing 2(1), March 1973.
Note that the implementation is left-biased -- the elements of a
first argument are always preferred to the second, for example in
union
or insert
.
- data Map k a
- (!) :: Ord k => Map k a -> k -> a
- (\\) :: Ord k => Map k a -> Map k b -> Map k a
- null :: Map k a -> Bool
- size :: Map k a -> Int
- member :: Ord k => k -> Map k a -> Bool
- notMember :: Ord k => k -> Map k a -> Bool
- lookup :: (Monad m, Ord k) => k -> Map k a -> m a
- findWithDefault :: Ord k => a -> k -> Map k a -> a
- empty :: Map k a
- singleton :: 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)
- 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
- 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)
- alter :: Ord k => (Maybe a -> Maybe a) -> k -> Map k 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
- unionsWith :: Ord k => (a -> a -> a) -> [Map k a] -> Map k a
- difference :: Ord k => Map k a -> Map k b -> Map k a
- differenceWith :: Ord k => (a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
- differenceWithKey :: Ord k => (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
- intersection :: Ord k => Map k a -> Map k b -> Map k a
- intersectionWith :: Ord k => (a -> b -> c) -> Map k a -> Map k b -> Map k c
- intersectionWithKey :: Ord k => (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
- 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)
- mapKeys :: Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
- mapKeysWith :: Ord k2 => (a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a
- mapKeysMonotonic :: (k1 -> k2) -> Map k1 a -> Map k2 a
- 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]
- keysSet :: Map k a -> Set 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)
- mapMaybe :: Ord k => (a -> Maybe b) -> Map k a -> Map k b
- mapMaybeWithKey :: Ord k => (k -> a -> Maybe b) -> Map k a -> Map k b
- mapEither :: Ord k => (a -> Either b c) -> Map k a -> (Map k b, Map k c)
- mapEitherWithKey :: Ord k => (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
- split :: Ord k => k -> Map k a -> (Map k a, Map k a)
- splitLookup :: Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a)
- isSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool
- isSubmapOfBy :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
- isProperSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool
- isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
- lookupIndex :: (Monad m, Ord k) => k -> Map k a -> m 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
- minView :: Monad m => Map k a -> m (a, Map k a)
- maxView :: Monad m => Map k a -> m (a, Map k a)
- minViewWithKey :: Monad m => Map k a -> m ((k, a), Map k a)
- maxViewWithKey :: Monad m => Map k a -> m ((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
to values a
.
Operators
(!) :: Ord k => Map k a -> k -> aSource
O(log n). Find the value at a key.
Calls error
when the element can not be found.
Query
findWithDefault :: Ord k => a -> k -> Map k a -> aSource
O(log n). The expression (
returns
the value at key findWithDefault
def k map)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.
If the key is already present in the map, the associated value is
replaced with the supplied value, i.e. insert
is equivalent to
.
insertWith
const
insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k aSource
O(log n). Insert with a combining function.
will insert the pair (key, value) into insertWith
f key value mpmp
if key does
not exist in the map. If the key does exist, the function will
insert the pair (key, f new_value old_value)
.
insertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k aSource
O(log n). Insert with a combining function.
will insert the pair (key, value) into insertWithKey
f key value mpmp
if key does
not exist in the map. If the key does exist, the function will
insert the pair (key,f key new_value old_value)
.
Note that the key passed to f is the same key passed to insertWithKey
.
insertLookupWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)Source
O(log n). The expression (
)
is a pair where the first element is equal to (insertLookupWithKey
f k x map
)
and the second element equal to (lookup
k map
).
insertWithKey
f k x map
insertWith' :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k aSource
Same as insertWith
, but the combining function is applied strictly.
insertWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k aSource
Same as insertWithKey
, but the combining function is applied strictly.
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.
updateWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> Map k aSource
O(log n). The expression (
) updates the
value updateWithKey
f k mapx
at k
(if it is in the map). If (f k x
) is Nothing
,
the element is deleted. If it is (
), the key Just
yk
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
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.
Hedge-union is more efficient on (bigset union
smallset).
unionsWith :: Ord k => (a -> a -> a) -> [Map k a] -> Map k aSource
The union of a list of maps, with a combining operation:
(
).
unionsWith
f == Prelude.foldl
(unionWith
f) empty
Difference
difference :: Ord k => Map k a -> Map k b -> 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 -> b -> Maybe a) -> Map k a -> Map k b -> 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 -> b -> Maybe a) -> Map k a -> Map k b -> 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 (
), the element is updated with a new value Just
yy
.
The implementation uses an efficient hedge algorithm comparable with hedge-union.
Intersection
intersection :: Ord k => Map k a -> Map k b -> 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 -> b -> c) -> Map k a -> Map k b -> Map k cSource
O(n+m). Intersection with a combining function.
intersectionWithKey :: Ord k => (k -> a -> b -> c) -> Map k a -> Map k b -> Map k cSource
O(n+m). Intersection with a combining function.
Intersection is more efficient on (bigset intersection
smallset)
intersectionWithKey :: Ord k => (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
intersectionWithKey f Tip t = Tip
intersectionWithKey f t Tip = Tip
intersectionWithKey f t1 t2 = intersectWithKey f t1 t2
intersectWithKey f Tip t = Tip intersectWithKey f t Tip = Tip intersectWithKey f t (Bin _ kx x l r) = case found of Nothing -> merge tl tr Just y -> join kx (f kx y x) tl tr where (lt,found,gt) = splitLookup kx t tl = intersectWithKey f lt l tr = intersectWithKey f gt r
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 ascending order of keys.
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 ascending order of keys.
mapKeys :: Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 aSource
O(n*log n).
is the map obtained by applying mapKeys
f sf
to each key of s
.
The size of the result may be smaller if f
maps two or more distinct
keys to the same new key. In this case the value at the smallest of
these keys is retained.
mapKeysWith :: Ord k2 => (a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 aSource
O(n*log n).
is the map obtained by applying mapKeysWith
c f sf
to each key of s
.
The size of the result may be smaller if f
maps two or more distinct
keys to the same new key. In this case the associated values will be
combined using c
.
mapKeysMonotonic :: (k1 -> k2) -> Map k1 a -> Map k2 aSource
O(n).
, but works only when mapKeysMonotonic
f s == mapKeys
f sf
is strictly monotonic.
The precondition is not checked.
Semi-formally, we have:
and [x < y ==> f x < f y | x <- ls, y <- ls] ==> mapKeysMonotonic f s == mapKeys f s where ls = keys s
Fold
foldWithKey :: (k -> a -> b -> b) -> b -> Map k a -> bSource
O(n). Fold the keys and values in the map, such that
.
For example,
foldWithKey
f z == Prelude.foldr
(uncurry
f) z . toAscList
keys map = foldWithKey (\k x ks -> k:ks) [] map
Conversion
O(n). Return all elements of the map in the ascending order of their keys.
assocs :: Map k a -> [(k, a)]Source
O(n). Return all key/value pairs in the map in ascending key order.
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. The precondition (input list is ascending) is not checked.
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. The precondition (input list is ascending) is not checked.
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. The precondition (input list is ascending) is not checked.
fromDistinctAscList :: [(k, a)] -> Map k aSource
O(n). Build a map from an ascending list of distinct elements in linear time. The precondition is not checked.
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 keys/values 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
.
mapMaybe :: Ord k => (a -> Maybe b) -> Map k a -> Map k bSource
O(n). Map values and collect the Just
results.
mapMaybeWithKey :: Ord k => (k -> a -> Maybe b) -> Map k a -> Map k bSource
O(n). Map keys/values and collect the Just
results.
split :: Ord k => k -> Map k a -> (Map k a, Map k a)Source
O(log n). The expression (
) is a pair split
k map(map1,map2)
where
the keys in map1
are smaller than k
and the keys in map2
larger than k
. Any key equal to k
is found in neither map1
nor map2
.
splitLookup :: Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a)Source
O(log n). The expression (
) splits a map just
like splitLookup
k mapsplit
but also returns
.
lookup
k map
Submap
isSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> BoolSource
O(n+m).
This function is defined as (
).
isSubmapOf
= isSubmapOfBy
(==)
isSubmapOfBy :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> BoolSource
O(n+m).
The expression (
) returns isSubmapOfBy
f t1 t2True
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
:
isSubmapOfBy (==) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) isSubmapOfBy (<=) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1),('b',2)])
But the following are all False
:
isSubmapOfBy (==) (fromList [('a',2)]) (fromList [('a',1),('b',2)]) isSubmapOfBy (<) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1)])
isProperSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> BoolSource
O(n+m). Is this a proper submap? (ie. a submap but not equal).
Defined as (
).
isProperSubmapOf
= isProperSubmapOfBy
(==)
isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> BoolSource
O(n+m). Is this a proper submap? (ie. a submap but not equal).
The expression (
) returns isProperSubmapOfBy
f m1 m2True
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
:
isProperSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)]) isProperSubmapOfBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
But the following are all False
:
isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)]) isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)]) isProperSubmapOfBy (<) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
Indexed
lookupIndex :: (Monad m, Ord k) => k -> Map k a -> m 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.
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.
updateMin :: (a -> Maybe a) -> Map k a -> Map k aSource
O(log n). Update the value at the minimal key.
updateMax :: (a -> Maybe a) -> Map k a -> Map k aSource
O(log n). Update the value at the maximal key.
updateMinWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k aSource
O(log n). Update the value at the minimal key.
updateMaxWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k aSource
O(log n). Update the value at the maximal key.
minView :: Monad m => Map k a -> m (a, Map k a)Source
O(log n). Retrieves the minimal key's value of the map, and the map stripped from that element
fail
s (in the monad) when passed an empty map.
maxView :: Monad m => Map k a -> m (a, Map k a)Source
O(log n). Retrieves the maximal key's value of the map, and the map stripped from that element
fail
s (in the monad) when passed an empty map.
minViewWithKey :: Monad m => Map k a -> m ((k, a), Map k a)Source
O(log n). Retrieves the minimal (key,value) pair of the map, and the map stripped from that element
fail
s (in the monad) when passed an empty map.
maxViewWithKey :: Monad m => Map k a -> m ((k, a), Map k a)Source
O(log n). Retrieves the maximal (key,value) pair of the map, and the map stripped from that element
fail
s (in the monad) when passed an empty map.
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 (
) shows
the tree that implements the map. Elements are shown using the showTreeWith
showelem hang wide mapshowElem
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> let t = fromDistinctAscList [(x,()) | x <- [1..5]] Map> putStrLn $ showTreeWith (\k x -> show (k,x)) True False t (4,()) +--(2,()) | +--(1,()) | +--(3,()) +--(5,()) Map> putStrLn $ showTreeWith (\k x -> show (k,x)) True True t (4,()) | +--(2,()) | | | +--(1,()) | | | +--(3,()) | +--(5,()) Map> putStrLn $ showTreeWith (\k x -> show (k,x)) False True t +--(5,()) | (4,()) | | +--(3,()) | | +--(2,()) | +--(1,())