A map from partially-ordered keys k to values v.

Test whether the structure is empty. The default implementation is optimized for structures that are similar to cons-lists, because there is no general way to do better.

Since: base-4.8.0.0

\(\mathcal{O}(1)\). The number of elements in this map.

\(\mathcal{O}(w)\). The width \(w\) of the chain decomposition in the internal data structure. This is always at least as big as the size of the biggest possible anti-chain.

\(\mathcal{O}(w\log n)\). Is the key a member of the map? See also notMember.

>>> member 5 (fromList [(5,'a'), (3,'b')]) == True
True
>>> member 1 (fromList [(5,'a'), (3,'b')]) == False
True

\(\mathcal{O}(w\log n)\). Is the key not a member of the map? See also member.

>>> notMember 5 (fromList [(5,'a'), (3,'b')]) == False
True
>>> notMember 1 (fromList [(5,'a'), (3,'b')]) == True
True

\(\mathcal{O}(w\log n)\). Is the key a member of the map?

\(\mathcal{O}(w\log n)\). The expression (findWithDefault def k map) returns the value at key k or returns default value def when the key is not in the map.

>>> findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
True
>>> findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
True

\(\mathcal{O}(w\log n)\). Find the largest set of keys smaller than the given one and return the corresponding list of (key, value) pairs.

Note that the following examples assume the Divisibility partial order defined at the top.

>>> lookupLT 3  (fromList [(3,'a'), (5,'b')])
[]
>>> lookupLT 9 (fromList [(3,'a'), (5,'b')])
[(3,'a')]

\(\mathcal{O}(w\log n)\). Find the smallest key greater than the given one and return the corresponding list of (key, value) pairs.

Note that the following examples assume the Divisibility partial order defined at the top.

>>> lookupGT 5 (fromList [(3,'a'), (10,'b')])
[(10,'b')]
>>> lookupGT 5 (fromList [(3,'a'), (5,'b')])
[]

\(\mathcal{O}(w\log n)\). Find the largest key smaller or equal to the given one and return the corresponding list of (key, value) pairs.

Note that the following examples assume the Divisibility partial order defined at the top.

>>> lookupLE 2 (fromList [(3,'a'), (5,'b')])
[]
>>> lookupLE 3 (fromList [(3,'a'), (5,'b')])
[(3,'a')]
>>> lookupLE 10 (fromList [(3,'a'), (5,'b')])
[(5,'b')]

\(\mathcal{O}(w\log n)\). Find the smallest key greater or equal to the given one and return the corresponding list of (key, value) pairs.

Note that the following examples assume the Divisibility partial order defined at the top.

>>> lookupGE 3 (fromList [(3,'a'), (5,'b')])
[(3,'a')]
>>> lookupGE 5 (fromList [(3,'a'), (10,'b')])
[(10,'b')]
>>> lookupGE 6 (fromList [(3,'a'), (5,'b')])
[]

\(\mathcal{O}(1)\). The empty map.

>>> empty
fromList []
>>> size empty
0

\(\mathcal{O}(1)\). A map with a single element.

>>> singleton 1 'a'
fromList [(1,'a')]
>>> size (singleton 1 'a')
1

\(\mathcal{O}(w\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. insert is equivalent to insertWith const.

>>> insert 5 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3,'b'), (5,'x')]
True
>>> insert 7 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3,'b'), (5,'a'), (7,'x')]
True
>>> insert 5 'x' empty                         == singleton 5 'x'
True

\(\mathcal{O}(w\log n)\). Insert with a function, combining new value and old value. insertWith f key value mp will insert the pair (key, value) into mp 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).

>>> insertWith (++) 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "xxxa")]
True
>>> insertWith (++) 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
True
>>> insertWith (++) 5 "xxx" empty                         == singleton 5 "xxx"
True

\(\mathcal{O}(w\log n)\). Insert with a function, combining key, new value and old value. insertWithKey f key value mp will insert the pair (key, value) into mp 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.

>>> let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
>>> insertWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:xxx|a")]
True
>>> insertWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
True
>>> insertWithKey f 5 "xxx" empty                         == singleton 5 "xxx"
True

\(\mathcal{O}(w\log n)\). Combines insert operation with old value retrieval. 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).

>>> let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
>>> insertLookupWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:xxx|a")])
True
>>> insertLookupWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a"), (7, "xxx")])
True
>>> insertLookupWithKey f 5 "xxx" empty                         == (Nothing,  singleton 5 "xxx")
True

This is how to define insertLookup using insertLookupWithKey:

>>> let insertLookup kx x t = insertLookupWithKey (\_ a _ -> a) kx x t
>>> insertLookup 5 "x" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "x")])
True
>>> insertLookup 7 "x" (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a"), (7, "x")])
True

\(\mathcal{O}(w\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.

>>> delete 5 (fromList [(5,"a"), (3,"b")])
fromList [(3,"b")]
>>> delete 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
True
>>> delete 5 empty
fromList []

\(\mathcal{O}(w\log n)\). Simultaneous delete and lookup.

\(\mathcal{O}(w\log n)\). Adjust a value at a specific key with the result of the provided function. When the key is not a member of the map, the original map is returned.

>>> adjust ("new " ++) 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
True
>>> adjust ("new " ++) 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
True
>>> adjust ("new " ++) 7 empty                         == empty
True

\(\mathcal{O}(w\log n)\). Adjust a value at a specific key with the result of the provided function. When the key is not a member of the map, the original map is returned.

>>> let f key x = (show key) ++ ":new " ++ x
>>> adjustWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
True
>>> adjustWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
True
>>> adjustWithKey f 7 empty                         == empty
True

\(\mathcal{O}(w\log n)\). Adjust a value at a specific key with the result of the provided function and simultaneously look up the old value at that key. When the key is not a member of the map, the original map is returned.

>>> let f key old_value = show key ++ ":" ++ show 42 ++ "|" ++ old_value
>>> adjustLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:42|a")])
True
>>> adjustLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a")])
True
>>> adjustLookupWithKey f 5 empty                         == (Nothing,  empty)
True

\(\mathcal{O}(w\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.

>>> let f x = if x == "a" then Just "new a" else Nothing
>>> update f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
True
>>> update f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
True
>>> update f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
True

\(\mathcal{O}(w\log n)\). The expression (updateWithKey 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.

>>> let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
>>> updateWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
True
>>> updateWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
True
>>> updateWithKey f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
True

\(\mathcal{O}(w\log n)\). Lookup and update. See also updateWithKey. Warning: Contrary to Data.Map.Lazy, the lookup does not return the updated value, but the old value. This is consistent with insertLookupWithKey and also Data.IntMap.Lazy.updateLookupWithKey.

Re-apply the updating function to the looked-up value once more to get the value in the map, like in the last example:

>>> let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
>>> updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:new a")])
True
>>> updateLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a")])
True
>>> updateLookupWithKey f 3 (fromList [(5,"a"), (3,"b")]) == (Just "b", singleton 5 "a")
True
>>> fst (updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")])) >>= f 5
Just "5:new a"

\(\mathcal{O}(w\log n)\). The expression (alter f k map) alters the value x at k, or absence thereof. alter can be used to insert, delete, or update a value in a Map. In short : lookup k (alter f k m) = f (lookup k m).

>>> let f _ = Nothing
>>> alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
True
>>> alter f 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
True
>>> let f _ = Just "c"
>>> alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "c")]
True
>>> alter f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "c")]
True

\(\mathcal{O}(w\log n)\). The expression (alterWithKey f k map) alters the value x at k, or absence thereof. alterWithKey can be used to insert, delete, or update a value in a Map. In short : lookup k (alter f k m) = f k (lookup k m).

>>> let f _ _ = Nothing
>>> alterWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
True
>>> alterWithKey f 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
True
>>> let f k _ = Just (show k ++ ":c")
>>> alterWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "7:c")]
True
>>> alterWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:c")]
True

\(\mathcal{O}(w\log n)\). Lookup and alteration. See also alterWithKey.

>>> let f k x = if x == Nothing then Just ((show k) ++ ":new a") else Nothing
>>> alterLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b")])
True
>>> alterLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a"), (7, "7:new a")])
True
>>> alterLookupWithKey f 3 (fromList [(5,"a"), (3,"b")]) == (Just "b", singleton 5 "a")
True

\(\mathcal{O}(w\log n)\). The expression (alterF f k map) alters the value x at k, or absence thereof. alterF can be used to inspect, insert, delete, or update a value in a Map. In short: lookup k <$> alterF f k m = f (lookup k m).

Example:

interactiveAlter :: Divibility -> DivMap String -> IO (DivMap String)
interactiveAlter k m = alterF f k m where
  f Nothing -> do
     putStrLn $ show k ++
         " was not found in the map. Would you like to add it?"
     getUserResponse1 :: IO (Maybe String)
  f (Just old) -> do
     putStrLn "The key is currently bound to " ++ show old ++
         ". Would you like to change or delete it?"
     getUserresponse2 :: IO (Maybe String)

alterF is the most general operation for working with an individual key that may or may not be in a given map. When used with trivial functors like Identity and Const, it is often slightly slower than more specialized combinators like lookup and insert. However, when the functor is non-trivial and key comparison is not particularly cheap, it is the fastest way.

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). The expression (union t1 t2) takes the left-biased union of t1 and t2. It prefers t1 when duplicate keys are encountered, i.e. (union == unionWith const).

>>> union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]
True

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). Union with a combining function.

>>> unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]
True

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). Union with a combining function.

>>> let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value
>>> unionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "5:a|A"), (7, "C")]
True

\(\mathcal{O}(wn\log n)\), where \(n=\max_i n_i\) and \(w=\max_i w_i\). The union of a list of maps: (unions == foldl union empty).

>>> :{
  unions [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
     == fromList [(3, "b"), (5, "a"), (7, "C")]
:}
True

>>> :{
 unions [(fromList [(5, "A3"), (3, "B3")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "a"), (3, "b")])]
     == fromList [(3, "B3"), (5, "A3"), (7, "C")]
:}
True

\(\mathcal{O}(wn\log n)\), where \(n=\max_i n_i\) and \(w=\max_i w_i\). The union of a list of maps, with a combining operation: (unionsWith f == foldl (unionWith f) empty).

>>> :{
 unionsWith (++) [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
     == fromList [(3, "bB3"), (5, "aAA3"), (7, "C")]
:}
True

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). Difference of two maps. Return elements of the first map not existing in the second map.

>>> difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
fromList [(3,"b")]

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). Difference with a combining function. When two equal keys are encountered, the combining function is applied to the values of these keys. 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.

>>> let f al ar = if al == "b" then Just (al ++ ":" ++ ar) else Nothing
>>> differenceWith f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (7, "C")])
fromList [(3,"b:B")]

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). 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.

>>> let f k al ar = if al == "b" then Just ((show k) ++ ":" ++ al ++ "|" ++ ar) else Nothing
>>> differenceWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (10, "C")])
fromList [(3,"3:b|B")]

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). Intersection of two maps. Return data in the first map for the keys existing in both maps. (intersection m1 m2 == intersectionWith const m1 m2).

>>> intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
fromList [(5,"a")]

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). Intersection with a combining function.

>>> intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
fromList [(5,"aA")]

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). Intersection with a combining function.

>>> let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar
>>> intersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
fromList [(5,"5:a|A")]

\(\mathcal{O}(n)\). Map a function over all values in the map.

>>> map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
True

\(\mathcal{O}(n)\). Map a function over all values in the map.

>>> let f key x = (show key) ++ ":" ++ x
>>> mapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]
True

\(\mathcal{O}(n)\). traverseWithKey f m == fromList $ traverse ((k, v) -> (v' -> v' seq (k,v')) $ f k v) (toList m) That is, it behaves much like a regular traverse except that the traversing function also has access to the key associated with a value and the values are forced before they are installed in the result map.

>>> traverseWithKey (\(Div k) v -> if odd k then Just (succ v) else Nothing) (fromList [(1, 'a'), (5, 'e')]) == Just (fromList [(1, 'b'), (5, 'f')])
True
>>> traverseWithKey (\(Div k) v -> if odd k then Just (succ v) else Nothing) (fromList [(2, 'c')])           == Nothing
True

\(\mathcal{O}(n)\). Traverse keys/values and collect the Just results.

\(\mathcal{O}(n)\). The function mapAccum threads an accumulating argument through the map in ascending order of keys.

>>> let f a b = (a ++ b, b ++ "X")
>>> mapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])
True

\(\mathcal{O}(n)\). The function mapAccumWithKey threads an accumulating argument through the map in ascending order of keys.

>>> let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")
>>> mapAccumWithKey f "Everything:" (fromList [(5,"a"), (3,"b")]) == ("Everything: 3-b 5-a", fromList [(3, "bX"), (5, "aX")])
True

\(\mathcal{O}(wn\log n)\). mapKeys f s is the map obtained by applying f 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 greatest of the original keys is retained.

>>> mapKeys (+ 1) (fromList [(5,"a"), (3,"b")]) == fromList [(4, "b"), (6, "a")]
True
>>> mapKeys (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
fromList [(1,"c")]
>>> mapKeys (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
fromList [(3,"c")]

\(\mathcal{O}(wn\log n)\). mapKeysWith c f s is the map obtained by applying f 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.

>>> mapKeysWith (+) (\ _ -> 1) (fromList [(1,1), (2,2), (3,3), (4,4)]) == singleton 1 10
True
>>> mapKeysWith (+) (\ _ -> 3) (fromList [(1,1), (2,1), (3,1), (4,1)]) == singleton 3 4
True

\(\mathcal{O}(n)\). mapKeysMonotonic f s == mapKeys f s, but works only when f is strictly monotonic. That is, for any values x and y, if x < y then f x < f y. The precondition is not checked. Semi-formally, for every chain ls in s we have:

and [x < y ==> f x < f y | x <- ls, y <- ls]
                    ==> mapKeysMonotonic f s == mapKeys f s

This means that f maps distinct original keys to distinct resulting keys. This function has better performance than mapKeys.

>>> mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")]) == fromList [(6, "b"), (10, "a")]
True

\(\mathcal{O}(n)\). Fold the keys and values in the map using the given right-associative binary operator, such that foldrWithKey f z == foldr (uncurry f) z . toAscList.

For example,

>>> keys map = foldrWithKey (\k x ks -> k:ks) [] map

>>> let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
>>> foldrWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"
True

\(\mathcal{O}(n)\). Fold the keys and values in the map using the given left-associative binary operator, such that foldlWithKey f z == foldl (\z' (kx, x) -> f z' kx x) z . toAscList.

>>> keys = reverse . foldlWithKey (\ks k x -> k:ks) []

>>> let f result k a = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
>>> foldlWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (3:b)(5:a)"
True

\(\mathcal{O}(n)\). Fold the keys and values in the map using the given monoid, such that

foldMapWithKey f = fold . mapWithKey f

\(\mathcal{O}(n)\). A strict version of foldr. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.

\(\mathcal{O}(n)\). A strict version of foldl. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.

\(\mathcal{O}(n)\). A strict version of foldrWithKey. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.

\(\mathcal{O}(n)\). A strict version of foldlWithKey. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.

\(\mathcal{O}(n)\). Return all elements of the map in unspecified order.

>>> elems (fromList [(5,"a"), (3,"b")])
["b","a"]
>>> elems empty
[]

\(\mathcal{O}(n)\). Return all keys of the map in unspecified order.

>>> keys (fromList [(5,"a"), (3,"b")])
[3,5]
>>> keys empty
[]

\(\mathcal{O}(n)\). Return all key/value pairs in the map in unspecified order.

>>> assocs (fromList [(5,"a"), (3,"b")])
[(3,"b"),(5,"a")]
>>> assocs empty
[]

\(\mathcal{O}(n)\). Return all key/value pairs in the map in unspecified order.

Currently, toList = assocs.

\(\mathcal{O}(wn\log n)\). Build a map from a list of key/value pairs. If the list contains more than one value for the same key, the last value for the key is retained.

>>> fromList [] == (empty :: DivMap String)
True
>>> fromList [(5,"a"), (3,"b"), (5, "c")] == fromList [(5,"c"), (3,"b")]
True
>>> fromList [(5,"c"), (3,"b"), (5, "a")] == fromList [(5,"a"), (3,"b")]
True

\(\mathcal{O}(wn\log n)\). Build a map from a list of key/value pairs with a combining function.

>>> fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]
True
>>> fromListWith (++) [] == (empty :: DivMap String)
True

\(\mathcal{O}(wn\log n)\). Build a map from a list of key/value pairs with a combining function.

>>> let f k a1 a2 = (show k) ++ a1 ++ a2
>>> fromListWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "3ab"), (5, "5a5ba")]
True
>>> fromListWithKey f [] == (empty :: DivMap String)
True

\(\mathcal{O}(w^2n)\). Return all key/value pairs in the map such that map fst (toLinearisation m) is a linearisation of the all keys present in the map. E.g., for any key k1 occuring before k2 in the linearisation, it cannot happen that k1 is strictly greater than k2 (so they are either incomparable or k1 <= k2).

\(\mathcal{O}(wn\log n)\). Build a map from a linearisation of key/value pairs. If the list contains more than one value for the same key, the last value for the key is retained.

\(\mathcal{O}(n)\). Filter all values that satisfy the predicate.

>>> filter (> "a") (fromList [(5,"a"), (3,"b")])
fromList [(3,"b")]
>>> filter (> "x") (fromList [(5,"a"), (3,"b")])
fromList []
>>> filter (< "a") (fromList [(5,"a"), (3,"b")])
fromList []

\(\mathcal{O}(n)\). Filter all keys/values that satisfy the predicate.

>>> filterWithKey (\(Div k) _ -> k > 4) (fromList [(5,"a"), (3,"b")])
fromList [(5,"a")]

\(\mathcal{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.

>>> partition (> "a") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b")], fromList [(5, "a")])
True
>>> partition (< "x") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
True
>>> partition (> "x") (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
True

\(\mathcal{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 (\ (Div k) _ -> k > 3) (fromList [(5,"a"), (3,"b")]) == (fromList [(5, "a")], fromList [(3, "b")])
True
>>> partitionWithKey (\ (Div k) _ -> k < 7) (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
True
>>> partitionWithKey (\ (Div k) _ -> k > 7) (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
True

\(\mathcal{O}(\log n)\). Take while a predicate on the keys holds. The user is responsible for ensuring that for all keys j and k in the map, j < k ==> p j >= p k. See note at spanAntitone.

takeWhileAntitone p = filterWithKey (k _ -> p k)

Since: 0.0.1.0

\(\mathcal{O}(\log n)\). Drop while a predicate on the keys holds. The user is responsible for ensuring that for all keys j and k in the map, j < k ==> p j >= p k. See note at spanAntitone.

dropWhileAntitone p = filterWithKey (k -> not (p k))

Since: 0.0.1.0

\(\mathcal{O}(log n)\). Divide a map at the point where a predicate on the keys stops holding. The user is responsible for ensuring that for all keys j and k in the map, j < k ==> p j >= p k.

spanAntitone p xs = partitionWithKey (k _ -> p k) xs

Note: if p is not actually antitone, then spanAntitone will split the map at some unspecified point where the predicate switches from holding to not holding (where the predicate is seen to hold before the first key and to fail after the last key).

Since: 0.0.1.0

\(\mathcal{O}(n)\). Map values and collect the Just results.

>>> let f x = if x == "a" then Just "new a" else Nothing
>>> mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"
True

\(\mathcal{O}(n)\). Map keys/values and collect the Just results.

>>> let f k _ = if k == 3 then Just ("key : " ++ (show k)) else Nothing
>>> mapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"
True

\(\mathcal{O}(n)\). Map values and separate the Left and Right results.

>>> let f a = if a < "c" then Left a else Right a

>>> :{
  mapEither f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
    == (fromList [(3,"b"), (5,"a")], fromList [(1,"x"), (7,"z")])
:}
True

>>> :{
  mapEither (\ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
    == (empty, fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
:}
True

\(\mathcal{O}(n)\). Map keys/values and separate the Left and Right results.

>>> let f (Div k) a = if k < 5 then Left (k * 2) else Right (a ++ a)

>>> :{
  mapEitherWithKey f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
    == (fromList [(1,2), (3,6)], fromList [(5,"aa"), (7,"zz")])
:}
True

>>> :{
  mapEitherWithKey (\_ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
    == (empty, fromList [(1,"x"), (3,"b"), (5,"a"), (7,"z")])
:}
True

\(\mathcal{O}(n_2 w_1 n_1 \log n_1)\). This function is defined as (isSubmapOf = isSubmapOfBy (==)).

\(\mathcal{O}(n_2 w_1 n_1 \log n_1)\). The expression (isSubmapOfBy 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:

>>> isSubmapOfBy (==) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
True
>>> isSubmapOfBy (<=) (fromList [(1,'a')]) (fromList [(1,'b'),(2,'c')])
True
>>> isSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a'),(2,'b')])
True

But the following are all False:

>>> isSubmapOfBy (==) (fromList [(2,'a')]) (fromList [(1,'a'),(2,'b')])
False
>>> isSubmapOfBy (<)  (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
False
>>> isSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a')])
False

\(\mathcal{O}(n_2 w_1 n_1 \log n_1)\). Is this a proper submap? (ie. a submap but not equal). Defined as (isProperSubmapOf = isProperSubmapOfBy (==)).

\(\mathcal{O}(n_2 w_1 n_1 \log n_1)\). Is this a proper submap? (ie. a submap but not equal). The expression (isProperSubmapOfBy 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:

>>> isProperSubmapOfBy (==) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
True
>>> isProperSubmapOfBy (<=) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
True

But the following are all False:

>>> isProperSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a'),(2,'b')])
False
>>> isProperSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a')])
False
>>> isProperSubmapOfBy (<)  (fromList [(1,'a')])         (fromList [(1,'a'),(2,'b')])
False

\(\mathcal{O}(w\log n)\). The minimal keys of the map.

Note that the following examples assume the Divisibility partial order defined at the top.

>>> lookupMin (fromList [(6,"a"), (3,"b")])
[(3,"b")]
>>> lookupMin empty
[]

\(\mathcal{O}(w\log n)\). The maximal keys of the map.

Note that the following examples assume the Divisibility partial order defined at the top.

>>> lookupMax (fromList [(6,"a"), (3,"b")])
[(6,"a")]
>>> lookupMax empty
[]