| ||||||||

| ||||||||

| ||||||||

Description | ||||||||

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 import Data.IntMap (IntMap) import qualified Data.IntMap as IntMap The implementation is based on - 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 | ||||||||

Synopsis | ||||||||

Map type | ||||||||

| ||||||||

| ||||||||

| ||||||||

Operators | ||||||||

| ||||||||

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

| ||||||||

Same as difference.
| ||||||||

Query | ||||||||

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

empty == fromList [] size empty == 0 | ||||||||

| ||||||||

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

Insertion | ||||||||

| ||||||||

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' | ||||||||

| ||||||||

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

| ||||||||

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

| ||||||||

)
and the second element equal to (lookup k map).
insertWithKey f k x maplet 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 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 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 ("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 | ||||||||

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

O(log n). The expression () alters the value alter f k mapx at k, or absence thereof.
alter can be used to insert, delete, or update a value in an IntMap.
In short : .
lookup k (alter f k m) = f (lookup k m) | ||||||||

Combine | ||||||||

Union | ||||||||

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

O(n). The function mapAccumR threads an accumulating
argument through the map in descending order of keys.
| ||||||||

Fold | ||||||||

| ||||||||

elems map = fold (:) [] map let f a len = len + (length a) fold f 0 (fromList [(5,"a"), (3,"bbb")]) == 4 | ||||||||

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

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

Lists | ||||||||

| ||||||||

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

| ||||||||

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 (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")] fromListWith (++) [] == empty | ||||||||

| ||||||||

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

Ordered lists | ||||||||

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

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

Filter | ||||||||

| ||||||||

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 (\k _ -> k > 4) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a" | ||||||||

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

(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 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 | ||||||||

| ||||||||

O(n+m). Is this a submap?
Defined as ().
isSubmapOf = isSubmapOfBy (==) | ||||||||

| ||||||||

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

| ||||||||

O(n+m). Is this a proper submap? (ie. a submap but not equal).
Defined as ().
isProperSubmapOf = isProperSubmapOfBy (==) | ||||||||

| ||||||||

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

| ||||||||

O(log n). Retrieves the maximal key of the map, and the map
stripped of that element, or Nothing if passed an empty map.
| ||||||||

| ||||||||

O(log n). Retrieves the minimal key of the map, and the map
stripped of that element, or Nothing if passed an empty map.
| ||||||||

| ||||||||

O(log n). The minimal key of the map.
| ||||||||

| ||||||||

O(log n). The maximal key of the map.
| ||||||||

| ||||||||

O(log n). Delete the minimal key.
| ||||||||

| ||||||||

O(log n). Delete the maximal key.
| ||||||||

| ||||||||

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

| ||||||||

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

| ||||||||

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

| ||||||||

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

Debugging | ||||||||

| ||||||||

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

| ||||||||

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

Produced by Haddock version 2.6.1 |