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 mpmp
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 mpmp
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 mapx
at k
(if it is in the map). If (f x
) is Nothing
, the element is
deleted. If it is (
), the key Just
yk
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 mapx
at k
(if it is in the map). If (f k x
) is Nothing
, the element is
deleted. If it is (
), the key Just
yk
is bound to the new value y
.
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
yy
.
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 m2True
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 m2True
when
m1
and m2
are not equal,
all keys in m1
are in m2
, and when f
returns True
when
applied to their respective values. For example, the following
expressions are all True
:
isProperSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)]) isProperSubmapOfBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
But the following are all False
:
isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)]) isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)]) isProperSubmapOfBy (<) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
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 maphang
is
True
, a hanging tree is shown otherwise a rotated tree is shown. If
wide
is True
, an extra wide version is shown.