- data Map k a
- (!) :: Ord k => Map k a -> k -> a
- (\\) :: Ord k => Map k a -> Map k a -> Map k a
- isEmpty :: Map k a -> Bool
- size :: Map k a -> Int
- member :: Ord k => k -> Map k a -> Bool
- lookup :: Ord k => k -> Map k a -> Maybe a
- find :: Ord k => k -> Map k a -> a
- findWithDefault :: Ord k => a -> k -> Map k a -> a
- empty :: Map k a
- single :: k -> a -> Map k a
- insert :: Ord k => k -> a -> Map k a -> Map k a
- insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
- insertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
- insertLookupWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
- delete :: Ord k => k -> Map k a -> Map k a
- adjust :: Ord k => (a -> a) -> k -> Map k a -> Map k a
- adjustWithKey :: Ord k => (k -> a -> a) -> k -> Map k a -> Map k a
- update :: Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a
- updateWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> Map k a
- updateLookupWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)
- union :: Ord k => Map k a -> Map k a -> Map k a
- unionWith :: Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
- unionWithKey :: Ord k => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
- unions :: Ord k => [Map k a] -> Map k a
- difference :: Ord k => Map k a -> Map k a -> Map k a
- differenceWith :: Ord k => (a -> a -> Maybe a) -> Map k a -> Map k a -> Map k a
- differenceWithKey :: Ord k => (k -> a -> a -> Maybe a) -> Map k a -> Map k a -> Map k a
- intersection :: Ord k => Map k a -> Map k a -> Map k a
- intersectionWith :: Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
- intersectionWithKey :: Ord k => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
- map :: (a -> b) -> Map k a -> Map k b
- mapWithKey :: (k -> a -> b) -> Map k a -> Map k b
- mapAccum :: (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
- mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
- fold :: (a -> b -> b) -> b -> Map k a -> b
- foldWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
- elems :: Map k a -> [a]
- keys :: Map k a -> [k]
- assocs :: Map k a -> [(k, a)]
- toList :: Map k a -> [(k, a)]
- fromList :: Ord k => [(k, a)] -> Map k a
- fromListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
- fromListWithKey :: Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
- toAscList :: Map k a -> [(k, a)]
- fromAscList :: Eq k => [(k, a)] -> Map k a
- fromAscListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a
- fromAscListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
- fromDistinctAscList :: [(k, a)] -> Map k a
- filter :: Ord k => (a -> Bool) -> Map k a -> Map k a
- filterWithKey :: Ord k => (k -> a -> Bool) -> Map k a -> Map k a
- partition :: Ord k => (a -> Bool) -> Map k a -> (Map k a, Map k a)
- partitionWithKey :: Ord k => (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
- split :: Ord k => k -> Map k a -> (Map k a, Map k a)
- splitLookup :: Ord k => k -> Map k a -> (Maybe a, Map k a, Map k a)
- subset :: (Ord k, Eq a) => Map k a -> Map k a -> Bool
- subsetBy :: Ord k => (a -> a -> Bool) -> Map k a -> Map k a -> Bool
- properSubset :: (Ord k, Eq a) => Map k a -> Map k a -> Bool
- properSubsetBy :: (Ord k, Eq a) => (a -> a -> Bool) -> Map k a -> Map k a -> Bool
- lookupIndex :: Ord k => k -> Map k a -> Maybe Int
- findIndex :: Ord k => k -> Map k a -> Int
- elemAt :: Int -> Map k a -> (k, a)
- updateAt :: (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
- deleteAt :: Int -> Map k a -> Map k a
- findMin :: Map k a -> (k, a)
- findMax :: Map k a -> (k, a)
- deleteMin :: Map k a -> Map k a
- deleteMax :: Map k a -> Map k a
- deleteFindMin :: Map k a -> ((k, a), Map k a)
- deleteFindMax :: Map k a -> ((k, a), Map k a)
- updateMin :: (a -> Maybe a) -> Map k a -> Map k a
- updateMax :: (a -> Maybe a) -> Map k a -> Map k a
- updateMinWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k a
- updateMaxWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k a
- showTree :: (Show k, Show a) => Map k a -> String
- showTreeWith :: (k -> a -> String) -> Bool -> Bool -> Map k a -> String
- valid :: Ord k => Map k a -> Bool

# Map type

A Map from keys `k`

and values `a`

.

# Operators

# Query

find :: Ord k => k -> Map k a -> aSource

*O(log n)*. Find the value of a key. Calls `error`

when the element can not be found.

findWithDefault :: Ord k => a -> k -> Map k a -> aSource

*O(log n)*. The expression `(findWithDefault def k map)`

returns the value of key `k`

or returns `def`

when
the key is not in the map.

# Construction

## Insertion

insert :: Ord k => k -> a -> Map k a -> Map k aSource

*O(log n)*. Insert a new key and value in the map.

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

*O(log n)*. Insert with a combining function.

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

*O(log n)*. Insert with a combining function.

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

*O(log n)*. The expression (`insertLookupWithKey f k x map`

) is a pair where
the first element is equal to (`lookup k map`

) and the second element
equal to (`insertWithKey f k x map`

).

## Delete/Update

delete :: Ord k => k -> Map k a -> Map k aSource

*O(log n)*. Delete a key and its value from the map. When the key is not
a member of the map, the original map is returned.

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

*O(log n)*. Adjust a value at a specific key. When the key is not
a member of the map, the original map is returned.

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

*O(log n)*. Adjust a value at a specific key. When the key is not
a member of the map, the original map is returned.

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

*O(log n)*. The expression (`update f k map`

) updates the value `x`

at `k`

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

) is `Nothing`

, the element is
deleted. If it is (`Just y`

), the key `k`

is bound to the new value `y`

.

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

*O(log n)*. The expression (`update f k map`

) updates the value `x`

at `k`

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

) is `Nothing`

, the element is
deleted. If it is (`Just y`

), the key `k`

is bound to the new value `y`

.

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

*O(log n)*. Lookup and update.

# Combine

## Union

union :: Ord k => Map k a -> Map k a -> Map k aSource

*O(n+m)*.
The expression (

) takes the left-biased union of `union`

t1 t2`t1`

and `t2`

.
It prefers `t1`

when duplicate keys are encountered, ie. (`union == unionWith const`

).
The implementation uses the efficient *hedge-union* algorithm.

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

*O(n+m)*. Union with a combining function. The implementation uses the efficient *hedge-union* algorithm.

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

*O(n+m)*.
Union with a combining function. The implementation uses the efficient *hedge-union* algorithm.

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

The union of a list of maps: (`unions == foldl union empty`

).

## Difference

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

*O(n+m)*. Difference of two maps.
The implementation uses an efficient *hedge* algorithm comparable with *hedge-union*.

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

*O(n+m)*. Difference with a combining function.
The implementation uses an efficient *hedge* algorithm comparable with *hedge-union*.

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

*O(n+m)*. Difference with a combining function. When two equal keys are
encountered, the combining function is applied to the key and both values.
If it returns `Nothing`

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

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

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

## Intersection

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

*O(n+m)*. Intersection of two maps. The values in the first
map are returned, i.e. (`intersection m1 m2 == intersectionWith const m1 m2`

).

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

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

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

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

# Traversal

## Map

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

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

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

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

threads an accumulating
argument through the map in an unspecified order.

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

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

threads an accumulating
argument through the map in unspecified order. (= ascending pre-order)

## Fold

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

*O(n)*. Fold the map in an unspecified order. (= descending post-order).

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

*O(n)*. Fold the map in an unspecified order. (= descending post-order).

# Conversion

## Lists

fromList :: Ord k => [(k, a)] -> Map k aSource

*O(n*log n)*. Build a map from a list of key/value pairs. See also `fromAscList`

.

fromListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map k aSource

*O(n*log n)*. Build a map from a list of key/value pairs with a combining function. See also `fromAscListWith`

.

fromListWithKey :: Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k aSource

*O(n*log n)*. Build a map from a list of key/value pairs with a combining function. See also `fromAscListWithKey`

.

## Ordered lists

fromAscList :: Eq k => [(k, a)] -> Map k aSource

*O(n)*. Build a map from an ascending list in linear time.

fromAscListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k aSource

*O(n)*. Build a map from an ascending list in linear time with a combining function for equal keys.

fromAscListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k aSource

*O(n)*. Build a map from an ascending list in linear time with a combining function for equal keys

fromDistinctAscList :: [(k, a)] -> Map k aSource

*O(n)*. Build a map from an ascending list of distinct elements in linear time.

# Filter

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

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

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

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

partition :: Ord k => (a -> Bool) -> Map k a -> (Map k a, Map k a)Source

*O(n)*. partition the map according to a predicate. The first
map contains all elements that satisfy the predicate, the second all
elements that fail the predicate. See also `split`

.

partitionWithKey :: Ord k => (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)Source

*O(n)*. partition the map according to a predicate. The first
map contains all elements that satisfy the predicate, the second all
elements that fail the predicate. See also `split`

.

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

*O(log n)*. The expression (`split k map`

) is a pair `(map1,map2)`

where
the keys in `map1`

are smaller than `k`

and the keys in `map2`

larger than `k`

.

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

*O(log n)*. The expression (`splitLookup k map`

) splits a map just
like `split`

but also returns `lookup k map`

.

# Subset

subset :: (Ord k, Eq a) => Map k a -> Map k a -> BoolSource

*O(n+m)*.
This function is defined as (`subset = subsetBy (==)`

).

subsetBy :: Ord k => (a -> a -> Bool) -> Map k a -> Map k a -> BoolSource

*O(n+m)*.
The expression (`subsetBy f t1 t2`

) returns `True`

if
all keys in `t1`

are in tree `t2`

, and when `f`

returns `True`

when
applied to their respective values. For example, the following
expressions are all `True`

.

subsetBy (==) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) subsetBy (<=) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) subsetBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1),('b',2)])

But the following are all `False`

:

subsetBy (==) (fromList [('a',2)]) (fromList [('a',1),('b',2)]) subsetBy (<) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) subsetBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1)])

properSubset :: (Ord k, Eq a) => Map k a -> Map k a -> BoolSource

*O(n+m)*. Is this a proper subset? (ie. a subset but not equal).
Defined as (`properSubset = properSubsetBy (==)`

).

properSubsetBy :: (Ord k, Eq a) => (a -> a -> Bool) -> Map k a -> Map k a -> BoolSource

*O(n+m)*. Is this a proper subset? (ie. a subset but not equal).
The expression (`properSubsetBy f m1 m2`

) returns `True`

when
`m1`

and `m2`

are not equal,
all keys in `m1`

are in `m2`

, and when `f`

returns `True`

when
applied to their respective values. For example, the following
expressions are all `True`

.

properSubsetBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)]) properSubsetBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])

But the following are all `False`

:

properSubsetBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)]) properSubsetBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)]) properSubsetBy (<) (fromList [(1,1)]) (fromList [(1,1),(2,2)])

# Indexed

lookupIndex :: Ord k => k -> Map k a -> Maybe IntSource

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

of the map.

elemAt :: Int -> Map k a -> (k, a)Source

*O(log n)*. Retrieve an element by *index*. Calls `error`

when an
invalid index is used.

updateAt :: (k -> a -> Maybe a) -> Int -> Map k a -> Map k aSource

*O(log n)*. Update the element at *index*. Calls `error`

when an
invalid index is used.

deleteAt :: Int -> Map k a -> Map k aSource

*O(log n)*. Delete the element at *index*. Defined as (`deleteAt i map = updateAt (k x -> Nothing) i map`

).

# Min/Max

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

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

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

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

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

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

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

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

# Debugging

showTree :: (Show k, Show a) => Map k a -> StringSource

*O(n)*. Show the tree that implements the map. The tree is shown
in a compressed, hanging format.

showTreeWith :: (k -> a -> String) -> Bool -> Bool -> Map k a -> StringSource

*O(n)*. The expression (`showTreeWith showelem hang wide map`

) shows
the tree that implements the map. Elements are shown using the `showElem`

function. If `hang`

is
`True`

, a *hanging* tree is shown otherwise a rotated tree is shown. If
`wide`

is true, an extra wide version is shown.

Map> putStrLn $ showTreeWith (\k x -> show (k,x)) True False $ fromDistinctAscList [(x,()) | x <- [1..5]] (4,()) +--(2,()) | +--(1,()) | +--(3,()) +--(5,()) Map> putStrLn $ showTreeWith (\k x -> show (k,x)) True True $ fromDistinctAscList [(x,()) | x <- [1..5]] (4,()) | +--(2,()) | | | +--(1,()) | | | +--(3,()) | +--(5,()) Map> putStrLn $ showTreeWith (\k x -> show (k,x)) False True $ fromDistinctAscList [(x,()) | x <- [1..5]] +--(5,()) | (4,()) | | +--(3,()) | | +--(2,()) | +--(1,())