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

Stability | provisional |

Maintainer | libraries@haskell.org |

An efficient implementation of maps from integer keys to values.

Since many function names (but not the type name) clash with
Prelude names, this module is usually imported `qualified`

, e.g.

import Data.EnumMap (EnumMap) import qualified Data.EnumMap k as EnumMap

The implementation is based on *big-endian patricia trees*. This data
structure performs especially well on binary operations like `union`

and `intersection`

. However, my benchmarks show that it is also
(much) faster on insertions and deletions when compared to a generic
size-balanced map implementation (see Data.Map).

- Chris Okasaki and Andy Gill, "
*Fast Mergeable Integer Maps*", Workshop on ML, September 1998, pages 77-86, http://citeseer.ist.psu.edu/okasaki98fast.html - D.R. Morrison, "/PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric/", Journal of the ACM, 15(4), October 1968, pages 514-534.

Operation comments contain the operation time complexity in
the Big-O notation http://en.wikipedia.org/wiki/Big_O_notation.
Many operations have a worst-case complexity of *O(min(n,W))*.
This means that the operation can become linear in the number of
elements with a maximum of *W* -- the number of bits in an `Int`

(32 or 64).

- data EnumMap k a
- type Key_ = Int
- (!) :: (Show k, Enum k) => EnumMap k a -> k -> a
- (\\) :: Enum k => EnumMap k a -> EnumMap k b -> EnumMap k a
- null :: EnumMap k a -> Bool
- size :: EnumMap k a -> Int
- member :: Enum k => k -> EnumMap k a -> Bool
- notMember :: Enum k => k -> EnumMap k a -> Bool
- lookup :: Enum k => k -> EnumMap k a -> Maybe a
- findWithDefault :: Enum k => a -> k -> EnumMap k a -> a
- empty :: EnumMap k a
- singleton :: Enum k => k -> a -> EnumMap k a
- insert :: Enum k => k -> a -> EnumMap k a -> EnumMap k a
- insertWith :: Enum k => (a -> a -> a) -> k -> a -> EnumMap k a -> EnumMap k a
- insertWithKey :: Enum k => (k -> a -> a -> a) -> k -> a -> EnumMap k a -> EnumMap k a
- insertLookupWithKey :: Enum k => (k -> a -> a -> a) -> k -> a -> EnumMap k a -> (Maybe a, EnumMap k a)
- delete :: Enum k => k -> EnumMap k a -> EnumMap k a
- adjust :: Enum k => (a -> a) -> k -> EnumMap k a -> EnumMap k a
- adjustWithKey :: Enum k => (k -> a -> a) -> k -> EnumMap k a -> EnumMap k a
- update :: Enum k => (a -> Maybe a) -> k -> EnumMap k a -> EnumMap k a
- updateWithKey :: Enum k => (k -> a -> Maybe a) -> k -> EnumMap k a -> EnumMap k a
- updateLookupWithKey :: Enum k => (k -> a -> Maybe a) -> k -> EnumMap k a -> (Maybe a, EnumMap k a)
- alter :: (Maybe a -> Maybe a) -> Int -> EnumMap k a -> EnumMap k a
- union :: Enum k => EnumMap k a -> EnumMap k a -> EnumMap k a
- unionWith :: Enum k => (a -> a -> a) -> EnumMap k a -> EnumMap k a -> EnumMap k a
- unionWithKey :: Enum k => (k -> a -> a -> a) -> EnumMap k a -> EnumMap k a -> EnumMap k a
- unions :: Enum k => [EnumMap k a] -> EnumMap k a
- unionsWith :: Enum k => (a -> a -> a) -> [EnumMap k a] -> EnumMap k a
- difference :: Enum k => EnumMap k a -> EnumMap k b -> EnumMap k a
- differenceWith :: Enum k => (a -> b -> Maybe a) -> EnumMap k a -> EnumMap k b -> EnumMap k a
- differenceWithKey :: Enum k => (k -> a -> b -> Maybe a) -> EnumMap k a -> EnumMap k b -> EnumMap k a
- intersection :: Enum k => EnumMap k a -> EnumMap k b -> EnumMap k a
- intersectionWith :: Enum k => (a -> b -> a) -> EnumMap k a -> EnumMap k b -> EnumMap k a
- intersectionWithKey :: Enum k => (k -> a -> b -> a) -> EnumMap k a -> EnumMap k b -> EnumMap k a
- map :: Enum k => (a -> b) -> EnumMap k a -> EnumMap k b
- mapWithKey :: Enum k => (k -> a -> b) -> EnumMap k a -> EnumMap k b
- mapAccum :: Enum k => (a -> b -> (a, c)) -> a -> EnumMap k b -> (a, EnumMap k c)
- mapAccumWithKey :: Enum k => (a -> k -> b -> (a, c)) -> a -> EnumMap k b -> (a, EnumMap k c)
- fold :: Enum k => (a -> b -> b) -> b -> EnumMap k a -> b
- foldWithKey :: Enum k => (k -> a -> b -> b) -> b -> EnumMap k a -> b
- elems :: Enum k => EnumMap k a -> [a]
- keys :: Enum k => EnumMap k a -> [k]
- keysSet :: Enum k => EnumMap k a -> IntSet
- assocs :: Enum k => EnumMap k a -> [(k, a)]
- toList :: Enum k => EnumMap k a -> [(k, a)]
- fromList :: Enum k => [(k, a)] -> EnumMap k a
- fromListWith :: Enum k => (a -> a -> a) -> [(k, a)] -> EnumMap k a
- fromListWithKey :: Enum k => (k -> a -> a -> a) -> [(k, a)] -> EnumMap k a
- toAscList :: (Num k, Ord k, Enum k) => EnumMap k a -> [(k, a)]
- fromAscList :: Enum k => [(k, a)] -> EnumMap k a
- fromAscListWith :: Enum k => (a -> a -> a) -> [(k, a)] -> EnumMap k a
- fromAscListWithKey :: Enum k => (k -> a -> a -> a) -> [(k, a)] -> EnumMap k a
- fromDistinctAscList :: Enum k => [(k, a)] -> EnumMap k a
- filter :: Enum k => (a -> Bool) -> EnumMap k a -> EnumMap k a
- filterWithKey :: Enum k => (k -> a -> Bool) -> EnumMap k a -> EnumMap k a
- partition :: Enum k => (a -> Bool) -> EnumMap k a -> (EnumMap k a, EnumMap k a)
- partitionWithKey :: Enum k => (k -> a -> Bool) -> EnumMap k a -> (EnumMap k a, EnumMap k a)
- mapMaybe :: Enum k => (a -> Maybe b) -> EnumMap k a -> EnumMap k b
- mapMaybeWithKey :: Enum k => (k -> a -> Maybe b) -> EnumMap k a -> EnumMap k b
- mapEither :: Enum k => (a -> Either b c) -> EnumMap k a -> (EnumMap k b, EnumMap k c)
- mapEitherWithKey :: Enum k => (k -> a -> Either b c) -> EnumMap k a -> (EnumMap k b, EnumMap k c)
- split :: Enum k => k -> EnumMap k a -> (EnumMap k a, EnumMap k a)
- splitLookup :: Enum k => k -> EnumMap k a -> (EnumMap k a, Maybe a, EnumMap k a)
- isSubmapOf :: (Eq a, Enum k) => EnumMap k a -> EnumMap k a -> Bool
- isSubmapOfBy :: Enum k => (a -> b -> Bool) -> EnumMap k a -> EnumMap k b -> Bool
- isProperSubmapOf :: (Enum k, Eq a) => EnumMap k a -> EnumMap k a -> Bool
- isProperSubmapOfBy :: Enum k => (a -> b -> Bool) -> EnumMap k a -> EnumMap k b -> Bool
- maxView :: Enum k => EnumMap k a -> Maybe (a, EnumMap k a)
- minView :: Enum k => EnumMap k a -> Maybe (a, EnumMap k a)
- findMin :: Enum k => EnumMap k a -> a
- findMax :: Enum k => EnumMap k a -> a
- deleteMin :: Enum k => EnumMap k a -> EnumMap k a
- deleteMax :: Enum k => EnumMap k a -> EnumMap k a
- deleteFindMin :: Enum k => EnumMap k a -> (a, EnumMap k a)
- deleteFindMax :: Enum k => EnumMap k a -> (a, EnumMap k a)
- updateMin :: Enum k => (a -> a) -> EnumMap k a -> EnumMap k a
- updateMax :: Enum k => (a -> a) -> EnumMap k a -> EnumMap k a
- updateMinWithKey :: Enum k => (k -> a -> a) -> EnumMap k a -> EnumMap k a
- updateMaxWithKey :: Enum k => (k -> a -> a) -> EnumMap k a -> EnumMap k a
- minViewWithKey :: Enum k => EnumMap k a -> Maybe ((k, a), EnumMap k a)
- maxViewWithKey :: Enum k => EnumMap k a -> Maybe ((k, a), EnumMap k a)
- showTree :: Show a => EnumMap k a -> String
- showTreeWith :: Show a => Bool -> Bool -> EnumMap k a -> String

# Map type

A map of integers to values `a`

.

Enum k => Functor (EnumMap k) | |

Typeable1 (EnumMap k) | |

Foldable (EnumMap k) | |

Eq a => Eq (EnumMap k a) | |

(Data a, Data k, Enum k) => Data (EnumMap k a) | |

(Ord k, Ord a, Enum k) => Ord (EnumMap k a) | |

(Read e, Read k, Enum k) => Read (EnumMap k e) | |

(Show a, Show k, Enum k) => Show (EnumMap k a) | |

Enum k => Monoid (EnumMap k a) |

# Operators

(!) :: (Show k, Enum k) => EnumMap k a -> k -> aSource

*O(min(n,W))*. 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

null :: EnumMap k a -> BoolSource

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

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

size :: EnumMap k a -> IntSource

*O(n)*. Number of elements in the map.

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

member :: Enum k => k -> EnumMap k a -> BoolSource

*O(min(n,W))*. Is the key a member of the map?

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

notMember :: Enum k => k -> EnumMap k a -> BoolSource

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

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

lookup :: Enum k => k -> EnumMap k a -> Maybe aSource

*O(min(n,W))*. Lookup the value at a key in the map. See also `Data.Map.lookup`

.

findWithDefault :: Enum k => a -> k -> EnumMap k a -> aSource

*O(min(n,W))*. The expression `(`

returns the value at key `findWithDefault`

def k map)`k`

or returns `def`

when the key is not an
element of the map.

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

# Construction

singleton :: Enum k => k -> a -> EnumMap k aSource

*O(1)*. A map of one element.

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

## Insertion

insert :: Enum k => k -> a -> EnumMap k a -> EnumMap k aSource

*O(min(n,W))*. Insert a new key/value pair 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`

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 :: Enum k => (a -> a -> a) -> k -> a -> EnumMap k a -> EnumMap k aSource

*O(min(n,W))*. Insert with a combining function.

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

insertWithKey :: Enum k => (k -> a -> a -> a) -> k -> a -> EnumMap k a -> EnumMap k aSource

*O(min(n,W))*. Insert with a combining function.

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 `f key new_value old_value`

.

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"

insertLookupWithKey :: Enum k => (k -> a -> a -> a) -> k -> a -> EnumMap k a -> (Maybe a, EnumMap k a)Source

*O(min(n,W))*. 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")])

## Delete/Update

delete :: Enum k => k -> EnumMap k a -> EnumMap k aSource

*O(min(n,W))*. 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 :: Enum k => (a -> a) -> k -> EnumMap k a -> EnumMap k aSource

*O(min(n,W))*. Adjust a value at a specific key. 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 :: Enum k => (k -> a -> a) -> k -> EnumMap k a -> EnumMap k aSource

*O(min(n,W))*. 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 :: Enum k => (a -> Maybe a) -> k -> EnumMap k a -> EnumMap k aSource

*O(min(n,W))*. 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 :: Enum k => (k -> a -> Maybe a) -> k -> EnumMap k a -> EnumMap k aSource

*O(min(n,W))*. The expression (

) updates the value `update`

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 :: Enum k => (k -> a -> Maybe a) -> k -> EnumMap k a -> (Maybe a, EnumMap k a)Source

*O(min(n,W))*. Lookup and update.
The function returns original value, if it is updated.
This is different behavior than `Data.Map.updateLookupWithKey`

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

# Combine

## Union

unionWith :: Enum k => (a -> a -> a) -> EnumMap k a -> EnumMap k a -> EnumMap k aSource

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

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

unionWithKey :: Enum k => (k -> a -> a -> a) -> EnumMap k a -> EnumMap k a -> EnumMap k aSource

*O(n+m)*. The 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")]

unions :: Enum k => [EnumMap k a] -> EnumMap k aSource

The union of a list of maps.

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 :: Enum k => (a -> a -> a) -> [EnumMap k a] -> EnumMap k aSource

The union of a list of maps, with a combining operation.

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 :: Enum k => EnumMap k a -> EnumMap k b -> EnumMap k aSource

*O(n+m)*. Difference between two maps (based on keys).

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

differenceWith :: Enum k => (a -> b -> Maybe a) -> EnumMap k a -> EnumMap k b -> EnumMap k aSource

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

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 :: Enum k => (k -> a -> b -> Maybe a) -> EnumMap k a -> EnumMap k b -> EnumMap 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`

.

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 :: Enum k => EnumMap k a -> EnumMap k b -> EnumMap k aSource

*O(n+m)*. The (left-biased) intersection of two maps (based on keys).

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

intersectionWith :: Enum k => (a -> b -> a) -> EnumMap k a -> EnumMap k b -> EnumMap k aSource

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

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

intersectionWithKey :: Enum k => (k -> a -> b -> a) -> EnumMap k a -> EnumMap k b -> EnumMap k aSource

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

# Traversal

## Map

map :: Enum k => (a -> b) -> EnumMap k a -> EnumMap 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 :: Enum k => (k -> a -> b) -> EnumMap k a -> EnumMap 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 :: Enum k => (a -> b -> (a, c)) -> a -> EnumMap k b -> (a, EnumMap k c)Source

*O(n)*. The function

threads an accumulating
argument through the map in ascending order of keys.
`mapAccum`

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

mapAccumWithKey :: Enum k => (a -> k -> b -> (a, c)) -> a -> EnumMap k b -> (a, EnumMap k c)Source

*O(n)*. The function

threads an accumulating
argument through the map in ascending order of keys.
`mapAccumWithKey`

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

## Fold

foldWithKey :: Enum k => (k -> a -> b -> b) -> b -> EnumMap k a -> bSource

*O(n)*. Fold the keys and values in the map, such that

.
For example,
`foldWithKey`

f z == `foldr`

(`uncurry`

f) z . `toAscList`

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

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

# Conversion

elems :: Enum k => EnumMap k a -> [a]Source

*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 == []

keys :: Enum k => EnumMap k a -> [k]Source

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

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

keysSet :: Enum k => EnumMap k a -> IntSetSource

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

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

assocs :: Enum k => EnumMap 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 :: Enum k => EnumMap k a -> [(k, a)]Source

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

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

fromList :: Enum k => [(k, a)] -> EnumMap k aSource

*O(n*min(n,W))*. Create a map from a list of key/value pairs.

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 :: Enum k => (a -> a -> a) -> [(k, a)] -> EnumMap k aSource

*O(n*min(n,W))*. Create 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 :: Enum k => (k -> a -> a -> a) -> [(k, a)] -> EnumMap k aSource

*O(n*min(n,W))*. Build a map from a list of key/value pairs with a combining function. See also fromAscListWithKey'.

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

## Ordered lists

toAscList :: (Num k, Ord k, Enum k) => EnumMap k a -> [(k, a)]Source

*O(n)*. Convert the map to a list of key/value pairs where the
keys are in ascending order.

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

fromAscList :: Enum k => [(k, a)] -> EnumMap k aSource

*O(n*min(n,W))*. Build a map from a list of key/value pairs where
the keys are in ascending order.

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

fromAscListWith :: Enum k => (a -> a -> a) -> [(k, a)] -> EnumMap k aSource

*O(n*min(n,W))*. Build a map from a list of key/value pairs where
the keys are in ascending order, with a combining function on equal keys.

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

fromAscListWithKey :: Enum k => (k -> a -> a -> a) -> [(k, a)] -> EnumMap k aSource

*O(n*min(n,W))*. Build a map from a list of key/value pairs where
the keys are in ascending order, with a combining function on equal keys.

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

fromDistinctAscList :: Enum k => [(k, a)] -> EnumMap k aSource

*O(n*min(n,W))*. Build a map from a list of key/value pairs where
the keys are in ascending order and all distinct.

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

# Filter

filter :: Enum k => (a -> Bool) -> EnumMap k a -> EnumMap k aSource

*O(n)*. Filter all values that satisfy some 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 :: Enum k => (k -> a -> Bool) -> EnumMap k a -> EnumMap k aSource

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

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

partition :: Enum k => (a -> Bool) -> EnumMap k a -> (EnumMap k a, EnumMap k a)Source

*O(n)*. Partition the map according to some 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 :: Enum k => (k -> a -> Bool) -> EnumMap k a -> (EnumMap k a, EnumMap k a)Source

*O(n)*. Partition the map according to some 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 :: Enum k => (a -> Maybe b) -> EnumMap k a -> EnumMap 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 :: Enum k => (k -> a -> Maybe b) -> EnumMap k a -> EnumMap 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 :: Enum k => (a -> Either b c) -> EnumMap k a -> (EnumMap k b, EnumMap 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 :: Enum k => (k -> a -> Either b c) -> EnumMap k a -> (EnumMap k b, EnumMap 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 :: Enum k => k -> EnumMap k a -> (EnumMap k a, EnumMap k a)Source

*O(log n)*. The expression (

) is a pair `split`

k map`(map1,map2)`

where all keys in `map1`

are lower than `k`

and all 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 :: Enum k => k -> EnumMap k a -> (EnumMap k a, Maybe a, EnumMap k a)Source

*O(log n)*. Performs a `split`

but also returns whether the pivot
key was found in the original 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 :: (Eq a, Enum k) => EnumMap k a -> EnumMap k a -> BoolSource

*O(n+m)*. Is this a submap?
Defined as (

).
`isSubmapOf`

= `isSubmapOfBy`

(==)

isSubmapOfBy :: Enum k => (a -> b -> Bool) -> EnumMap k a -> EnumMap k b -> BoolSource

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

) returns `isSubmapOfBy`

f m1 m2`True`

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

:

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

But the following are all `False`

:

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

isProperSubmapOf :: (Enum k, Eq a) => EnumMap k a -> EnumMap k a -> BoolSource

*O(n+m)*. Is this a proper submap? (ie. a submap but not equal).
Defined as (

).
`isProperSubmapOf`

= `isProperSubmapOfBy`

(==)

isProperSubmapOfBy :: Enum k => (a -> b -> Bool) -> EnumMap k a -> EnumMap 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)])

# Min/Max

maxView :: Enum k => EnumMap k a -> Maybe (a, EnumMap k a)Source

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

if passed an empty map.

minView :: Enum k => EnumMap k a -> Maybe (a, EnumMap k a)Source

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

if passed an empty map.

deleteFindMin :: Enum k => EnumMap k a -> (a, EnumMap k a)Source

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

deleteFindMax :: Enum k => EnumMap k a -> (a, EnumMap k a)Source

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

updateMin :: Enum k => (a -> a) -> EnumMap k a -> EnumMap 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 :: Enum k => (a -> a) -> EnumMap k a -> EnumMap 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 :: Enum k => (k -> a -> a) -> EnumMap k a -> EnumMap 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 :: Enum k => (k -> a -> a) -> EnumMap k a -> EnumMap 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"

minViewWithKey :: Enum k => EnumMap k a -> Maybe ((k, a), EnumMap 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 :: Enum k => EnumMap k a -> Maybe ((k, a), EnumMap 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 a => EnumMap k a -> StringSource

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

showTreeWith :: Show a => Bool -> Bool -> EnumMap k a -> StringSource

*O(n)*. The expression (

) shows
the tree that implements the map. If `showTreeWith`

hang wide map`hang`

is
`True`

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

is `True`

, an extra wide version is shown.