Portability | portable |
---|---|

Stability | provisional |

Maintainer | libraries@haskell.org |

Safe Haskell | Safe |

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`

.

Operation comments contain the operation time complexity in the Big-O notation http://en.wikipedia.org/wiki/Big_O_notation.

- 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 :: Ord k => k -> Map k a -> Maybe 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
- 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
- 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)
- 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)
- 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)
- mapAccumRWithKey :: (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
- foldr :: (a -> b -> b) -> b -> Map k a -> b
- foldl :: (a -> b -> a) -> a -> Map k b -> a
- foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
- foldlWithKey :: (a -> k -> b -> a) -> a -> Map k b -> a
- foldr' :: (a -> b -> b) -> b -> Map k a -> b
- foldl' :: (a -> b -> a) -> a -> Map k b -> a
- foldrWithKey' :: (k -> a -> b -> b) -> b -> Map k a -> b
- foldlWithKey' :: (a -> k -> b -> a) -> a -> Map k b -> 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)]
- toDescList :: 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 :: 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
- minView :: Map k a -> Maybe (a, Map k a)
- maxView :: Map k a -> Maybe (a, Map k a)
- minViewWithKey :: Map k a -> Maybe ((k, a), Map k a)
- maxViewWithKey :: Map k a -> Maybe ((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`

.

Typeable2 Map | |

Functor (Map k) | |

Foldable (Map k) | |

Traversable (Map k) | |

(Eq k, Eq a) => Eq (Map k a) | |

(Data k, Data a, Ord k) => Data (Map k a) | |

(Ord k, Ord v) => Ord (Map k v) | |

(Ord k, Read k, Read e) => Read (Map k e) | |

(Show k, Show a) => Show (Map k a) | |

Ord k => Monoid (Map k v) | |

(NFData k, NFData a) => NFData (Map k 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.

fromList [(5,'a'), (3,'b')] ! 1 Error: element not in the map fromList [(5,'a'), (3,'b')] ! 5 == 'a'

# Query

*O(1)*. Is the map empty?

Data.Map.null (empty) == True Data.Map.null (singleton 1 'a') == False

*O(1)*. The number of elements in the map.

size empty == 0 size (singleton 1 'a') == 1 size (fromList([(1,'a'), (2,'c'), (3,'b')])) == 3

member :: Ord k => k -> Map k a -> BoolSource

*O(log n)*. Is the key a member of the map? See also `notMember`

.

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

notMember :: Ord k => k -> Map k a -> BoolSource

*O(log n)*. Is the key not a member of the map? See also `member`

.

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

lookup :: Ord k => k -> Map k a -> Maybe aSource

*O(log n)*. Lookup the value at a key in the map.

The function will return the corresponding value as `(`

,
or `Just`

value)`Nothing`

if the key isn't in the map.

An example of using `lookup`

:

import Prelude hiding (lookup) import Data.Map employeeDept = fromList([("John","Sales"), ("Bob","IT")]) deptCountry = fromList([("IT","USA"), ("Sales","France")]) countryCurrency = fromList([("USA", "Dollar"), ("France", "Euro")]) employeeCurrency :: String -> Maybe String employeeCurrency name = do dept <- lookup name employeeDept country <- lookup dept deptCountry lookup country countryCurrency main = do putStrLn $ "John's currency: " ++ (show (employeeCurrency "John")) putStrLn $ "Pete's currency: " ++ (show (employeeCurrency "Pete"))

The output of this program:

John's currency: Just "Euro" Pete's currency: Nothing

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 default value `def`

when the key is not in the map.

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

# Construction

singleton :: k -> a -> Map k aSource

*O(1)*. A map with a single element.

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

## 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. `insert`

is equivalent to

.
`insertWith`

`const`

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

insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k aSource

*O(log n)*. Insert with a function, combining new value and old value.

will insert the pair (key, value) into `insertWith`

f key value mp`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")] insertWith (++) 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")] insertWith (++) 5 "xxx" empty == singleton 5 "xxx"

insertWith' :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k aSource

Same as `insertWith`

, but the combining function is applied strictly.
This is often the most desirable behavior.

For example, to update a counter:

insertWith' (+) k 1 m

insertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k aSource

*O(log n)*. Insert with a function, combining key, new value and old value.

will insert the pair (key, value) into `insertWithKey`

f key value mp`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")] insertWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")] insertWithKey f 5 "xxx" empty == singleton 5 "xxx"

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.

insertLookupWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)Source

*O(log n)*. Combines insert operation with old value retrieval.
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

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")]) insertLookupWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == (Nothing, fromList [(3, "b"), (5, "a"), (7, "xxx")]) insertLookupWithKey f 5 "xxx" empty == (Nothing, singleton 5 "xxx")

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")]) insertLookup 7 "x" (fromList [(5,"a"), (3,"b")]) == (Nothing, fromList [(3, "b"), (5, "a"), (7, "x")])

insertLookupWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)Source

*O(log n)*. A strict version of `insertLookupWithKey`

.

## 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.

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

adjust :: Ord k => (a -> a) -> k -> Map k a -> Map k aSource

*O(log n)*. Update 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")] adjust ("new " ++) 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")] adjust ("new " ++) 7 empty == empty

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.

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

update :: Ord k => (a -> Maybe a) -> k -> Map k a -> Map k aSource

*O(log n)*. The expression (

) updates the value `update`

f k map`x`

at `k`

(if it is in the map). If (`f x`

) is `Nothing`

, the element is
deleted. If it is (

), the key `Just`

y`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")] update f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")] update f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"

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 map`x`

at `k`

(if it is in the map). If (`f k x`

) is `Nothing`

,
the element is deleted. If it is (

), the key `Just`

y`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")] updateWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")] updateWithKey f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"

updateLookupWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)Source

*O(log n)*. Lookup and update. See also `updateWithKey`

.
The function returns changed value, if it is updated.
Returns the original key value if the map entry is deleted.

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

alter :: Ord k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k aSource

*O(log n)*. The expression (

) alters the value `alter`

f k map`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")] alter f 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b" let f _ = Just "c" alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "c")] alter f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "c")]

# 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 t2`t1`

and `t2`

.
It prefers `t1`

when duplicate keys are encountered,
i.e. (

).
The implementation uses the efficient `union`

== `unionWith`

`const`

*hedge-union* algorithm.
Hedge-union is more efficient on (bigset ``union`

` smallset).

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

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.

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

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).

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")]

unions :: Ord k => [Map k a] -> Map k aSource

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")] unions [(fromList [(5, "A3"), (3, "B3")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "a"), (3, "b")])] == fromList [(3, "B3"), (5, "A3"), (7, "C")]

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 == `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")]

## Difference

difference :: Ord k => Map k a -> Map k b -> Map k aSource

*O(n+m)*. Difference of two maps.
Return elements of the first map not existing in the second map.
The implementation uses an efficient *hedge* algorithm comparable with *hedge-union*.

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

differenceWith :: Ord 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 values of these keys.
If it returns `Nothing`

, the element is discarded (proper set difference). If
it returns (

), the element is updated with a new value `Just`

y`y`

.
The implementation uses an efficient *hedge* algorithm comparable with *hedge-union*.

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")]) == singleton 3 "b:B"

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`

y`y`

.
The implementation uses an efficient *hedge* algorithm comparable with *hedge-union*.

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")]) == singleton 3 "3:b|B"

## Intersection

intersection :: Ord k => Map k a -> Map k b -> Map k aSource

*O(n+m)*. 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")]) == singleton 5 "a"

intersectionWith :: Ord k => (a -> b -> c) -> Map k a -> Map k b -> Map k cSource

*O(n+m)*. Intersection with a combining function.

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

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).

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

# Traversal

## Map

map :: (a -> b) -> Map k a -> Map k bSource

*O(n)*. Map a function over all values in the map.

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

mapWithKey :: (k -> a -> b) -> Map k a -> Map k bSource

*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")]

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.

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

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.

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")])

mapAccumRWithKey :: (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)Source

*O(n)*. The function `mapAccumR`

threads an accumulating
argument through the map in descending 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 s`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 smallest of
these keys is retained.

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

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 s`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,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "cdab" mapKeysWith (++) (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "cdab"

mapKeysMonotonic :: (k1 -> k2) -> Map k1 a -> Map k2 aSource

*O(n)*.

, but works only when `mapKeysMonotonic`

f s == `mapKeys`

f s`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, we have:

and [x < y ==> f x < f y | x <- ls, y <- ls] ==> mapKeysMonotonic f s == mapKeys f s where ls = keys 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")] valid (mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")])) == True valid (mapKeysMonotonic (\ _ -> 1) (fromList [(5,"a"), (3,"b")])) == False

# Folds

foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> bSource

*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)"

foldlWithKey :: (a -> k -> b -> a) -> a -> Map k b -> aSource

*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`

For example,

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)"

## Strict folds

foldr' :: (a -> b -> b) -> b -> Map k a -> bSource

*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.

foldl' :: (a -> b -> a) -> a -> Map k b -> aSource

*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.

foldrWithKey' :: (k -> a -> b -> b) -> b -> Map k a -> bSource

*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.

foldlWithKey' :: (a -> k -> b -> a) -> a -> Map k b -> aSource

*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.

## Legacy folds

fold :: (a -> b -> b) -> b -> Map k a -> bSource

*O(n)*. Fold the values in the map using the given right-associative
binary operator. This function is an equivalent of `foldr`

and is present
for compatibility only.

*Please note that fold will be deprecated in the future and removed.*

foldWithKey :: (k -> a -> b -> b) -> b -> Map k a -> bSource

*O(n)*. Fold the keys and values in the map using the given right-associative
binary operator. This function is an equivalent of `foldrWithKey`

and is present
for compatibility only.

*Please note that foldWithKey will be deprecated in the future and removed.*

# Conversion

*O(n)*.
Return all elements of the map in the ascending order of their keys.

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

*O(n)*. Return all keys of the map in ascending order.

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

keysSet :: Map k a -> Set kSource

*O(n)*. The set of all keys of the map.

keysSet (fromList [(5,"a"), (3,"b")]) == Data.Set.fromList [3,5] keysSet empty == Data.Set.empty

assocs :: Map k a -> [(k, a)]Source

*O(n)*. Return all key/value pairs in the map in ascending key order.

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

## Lists

toList :: Map k a -> [(k, a)]Source

*O(n)*. Convert to a list of key/value pairs.

toList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")] toList empty == []

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`

.
If the list contains more than one value for the same key, the last value
for the key is retained.

fromList [] == empty fromList [(5,"a"), (3,"b"), (5, "c")] == fromList [(5,"c"), (3,"b")] fromList [(5,"c"), (3,"b"), (5, "a")] == fromList [(5,"a"), (3,"b")]

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`

.

fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")] fromListWith (++) [] == empty

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`

.

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")] fromListWithKey f [] == empty

## Ordered lists

toAscList :: Map k a -> [(k, a)]Source

*O(n)*. Convert to an ascending list.

toAscList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]

toDescList :: Map k a -> [(k, a)]Source

*O(n)*. Convert to a descending list.

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.*

fromAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")] fromAscList [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "b")] valid (fromAscList [(3,"b"), (5,"a"), (5,"b")]) == True valid (fromAscList [(5,"a"), (3,"b"), (5,"b")]) == False

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.*

fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")] valid (fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")]) == True valid (fromAscListWith (++) [(5,"a"), (3,"b"), (5,"b")]) == False

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.*

let f k a1 a2 = (show k) ++ ":" ++ a1 ++ a2 fromAscListWithKey f [(3,"b"), (5,"a"), (5,"b"), (5,"b")] == fromList [(3, "b"), (5, "5:b5:ba")] valid (fromAscListWithKey f [(3,"b"), (5,"a"), (5,"b"), (5,"b")]) == True valid (fromAscListWithKey f [(5,"a"), (3,"b"), (5,"b"), (5,"b")]) == False

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.*

fromDistinctAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")] valid (fromDistinctAscList [(3,"b"), (5,"a")]) == True valid (fromDistinctAscList [(3,"b"), (5,"a"), (5,"b")]) == False

# Filter

filter :: Ord k => (a -> Bool) -> Map k a -> Map k aSource

*O(n)*. Filter all values that satisfy the predicate.

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

filterWithKey :: Ord k => (k -> a -> Bool) -> Map k a -> Map k aSource

*O(n)*. Filter all keys/values that satisfy the predicate.

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

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`

.

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

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`

.

partitionWithKey (\ k _ -> k > 3) (fromList [(5,"a"), (3,"b")]) == (singleton 5 "a", singleton 3 "b") partitionWithKey (\ k _ -> k < 7) (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty) partitionWithKey (\ k _ -> k > 7) (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])

mapMaybe :: Ord k => (a -> Maybe b) -> Map k a -> Map k bSource

*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"

mapMaybeWithKey :: Ord k => (k -> a -> Maybe b) -> Map k a -> Map k bSource

*O(n)*. Map keys/values and collect the `Just`

results.

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

mapEither :: Ord k => (a -> Either b c) -> Map k a -> (Map k b, Map k c)Source

*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")]) mapEither (\ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")]) == (empty, fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])

mapEitherWithKey :: Ord k => (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)Source

*O(n)*. Map keys/values and separate the `Left`

and `Right`

results.

let f 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")]) mapEitherWithKey (\_ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")]) == (empty, fromList [(1,"x"), (3,"b"), (5,"a"), (7,"z")])

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`

.

split 2 (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3,"b"), (5,"a")]) split 3 (fromList [(5,"a"), (3,"b")]) == (empty, singleton 5 "a") split 4 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", singleton 5 "a") split 5 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", empty) split 6 (fromList [(5,"a"), (3,"b")]) == (fromList [(3,"b"), (5,"a")], empty)

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 map`split`

but also returns

.
`lookup`

k map

splitLookup 2 (fromList [(5,"a"), (3,"b")]) == (empty, Nothing, fromList [(3,"b"), (5,"a")]) splitLookup 3 (fromList [(5,"a"), (3,"b")]) == (empty, Just "b", singleton 5 "a") splitLookup 4 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", Nothing, singleton 5 "a") splitLookup 5 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", Just "a", empty) splitLookup 6 (fromList [(5,"a"), (3,"b")]) == (fromList [(3,"b"), (5,"a")], Nothing, empty)

# 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 t2`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 [('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 m2`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,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 :: 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.

isJust (lookupIndex 2 (fromList [(5,"a"), (3,"b")])) == False fromJust (lookupIndex 3 (fromList [(5,"a"), (3,"b")])) == 0 fromJust (lookupIndex 5 (fromList [(5,"a"), (3,"b")])) == 1 isJust (lookupIndex 6 (fromList [(5,"a"), (3,"b")])) == False

findIndex :: Ord k => k -> Map k a -> IntSource

*O(log n)*. Return the *index* of a key. The index is a number from
*0* up to, but not including, the `size`

of the map. Calls `error`

when
the key is not a `member`

of the map.

findIndex 2 (fromList [(5,"a"), (3,"b")]) Error: element is not in the map findIndex 3 (fromList [(5,"a"), (3,"b")]) == 0 findIndex 5 (fromList [(5,"a"), (3,"b")]) == 1 findIndex 6 (fromList [(5,"a"), (3,"b")]) Error: element is not in 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.

elemAt 0 (fromList [(5,"a"), (3,"b")]) == (3,"b") elemAt 1 (fromList [(5,"a"), (3,"b")]) == (5, "a") elemAt 2 (fromList [(5,"a"), (3,"b")]) Error: index out of range

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.

updateAt (\ _ _ -> Just "x") 0 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "x"), (5, "a")] updateAt (\ _ _ -> Just "x") 1 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "x")] updateAt (\ _ _ -> Just "x") 2 (fromList [(5,"a"), (3,"b")]) Error: index out of range updateAt (\ _ _ -> Just "x") (-1) (fromList [(5,"a"), (3,"b")]) Error: index out of range updateAt (\_ _ -> Nothing) 0 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a" updateAt (\_ _ -> Nothing) 1 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b" updateAt (\_ _ -> Nothing) 2 (fromList [(5,"a"), (3,"b")]) Error: index out of range updateAt (\_ _ -> Nothing) (-1) (fromList [(5,"a"), (3,"b")]) Error: index out of range

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

deleteAt 0 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a" deleteAt 1 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b" deleteAt 2 (fromList [(5,"a"), (3,"b")]) Error: index out of range deleteAt (-1) (fromList [(5,"a"), (3,"b")]) Error: index out of range

# Min/Max

findMin :: Map k a -> (k, a)Source

*O(log n)*. The minimal key of the map. Calls `error`

if the map is empty.

findMin (fromList [(5,"a"), (3,"b")]) == (3,"b") findMin empty Error: empty map has no minimal element

findMax :: Map k a -> (k, a)Source

*O(log n)*. The maximal key of the map. Calls `error`

if the map is empty.

findMax (fromList [(5,"a"), (3,"b")]) == (5,"a") findMax empty Error: empty map has no maximal element

deleteMin :: Map k a -> Map k aSource

*O(log n)*. Delete the minimal key. Returns an empty map if the map is empty.

deleteMin (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(5,"a"), (7,"c")] deleteMin empty == empty

deleteMax :: Map k a -> Map k aSource

*O(log n)*. Delete the maximal key. Returns an empty map if the map is empty.

deleteMax (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(3,"b"), (5,"a")] deleteMax empty == empty

deleteFindMin :: Map k a -> ((k, a), Map k a)Source

*O(log n)*. Delete and find the minimal element.

deleteFindMin (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((3,"b"), fromList[(5,"a"), (10,"c")]) deleteFindMin Error: can not return the minimal element of an empty map

deleteFindMax :: Map k a -> ((k, a), Map k a)Source

*O(log n)*. Delete and find the maximal element.

deleteFindMax (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((10,"c"), fromList [(3,"b"), (5,"a")]) deleteFindMax empty Error: can not return the maximal element of an empty map

updateMin :: (a -> Maybe a) -> Map k a -> Map k aSource

*O(log n)*. Update the value at the minimal key.

updateMin (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "Xb"), (5, "a")] updateMin (\ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"

updateMax :: (a -> Maybe a) -> Map k a -> Map k aSource

*O(log n)*. Update the value at the maximal key.

updateMax (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "Xa")] updateMax (\ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"

updateMinWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k aSource

*O(log n)*. Update the value at the minimal key.

updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"3:b"), (5,"a")] updateMinWithKey (\ _ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"

updateMaxWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k aSource

*O(log n)*. Update the value at the maximal key.

updateMaxWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"b"), (5,"5:a")] updateMaxWithKey (\ _ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"

minView :: Map k a -> Maybe (a, Map k a)Source

*O(log n)*. Retrieves the value associated with minimal key of the
map, and the map stripped of that element, or `Nothing`

if passed an
empty map.

minView (fromList [(5,"a"), (3,"b")]) == Just ("b", singleton 5 "a") minView empty == Nothing

maxView :: Map k a -> Maybe (a, Map k a)Source

*O(log n)*. Retrieves the value associated with maximal key of the
map, and the map stripped of that element, or `Nothing`

if passed an

maxView (fromList [(5,"a"), (3,"b")]) == Just ("a", singleton 3 "b") maxView empty == Nothing

minViewWithKey :: Map k a -> Maybe ((k, a), Map k a)Source

*O(log n)*. Retrieves the minimal (key,value) pair of the map, and
the map stripped of that element, or `Nothing`

if passed an empty map.

minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a") minViewWithKey empty == Nothing

maxViewWithKey :: Map k a -> Maybe ((k, a), Map k a)Source

*O(log n)*. Retrieves the maximal (key,value) pair of the map, and
the map stripped of that element, or `Nothing`

if passed an empty map.

maxViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((5,"a"), singleton 3 "b") maxViewWithKey empty == Nothing

# 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. See `showTreeWith`

.

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 map`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> 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,())