The IntMap v type represents a finite map (sometimes called a dictionary)
from key of type Int to values of type v.
Each function in this module is careful to force values before installing
them in an IntMap. This is usually more efficient when laziness is not
necessary. When laziness is required, use the functions in
Data.IntMap.Lazy.
In particular, the functions in this module obey the following law:
If all values stored in all maps in the arguments are in WHNF, then all
values stored in all maps in the results will be in WHNF once those maps
are evaluated.
For a walkthrough of the most commonly used functions see the
maps introduction.
This module is intended to be imported qualified, to avoid name clashes with
Prelude functions, e.g.
import Data.IntMap.Strict (IntMap)
import qualified Data.IntMap.Strict as IntMap
Note that the implementation is generally left-biased. Functions that take
two maps as arguments and combine them, such as union and intersection,
prefer the values in the first argument to those in the second.
Warning
The IntMap type is shared between the lazy and strict modules, meaning that
the same IntMap value can be passed to functions in both modules. This
means that the Functor, Traversable and Data instances are
the same as for the Data.IntMap.Lazy module, so if they are used the
resulting map may contain suspended values (thunks).
Implementation
The implementation is based on big-endian patricia trees. This data
structure performs especially well on binary operations like union and
intersection. Additionally, benchmarks show that it is also (much) faster
on insertions and deletions when compared to a generic size-balanced map
implementation (see Data.Map).
D.R. Morrison,
"PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric",
Journal of the ACM, 15(4), October 1968, pages 514-534,
https://doi.org/10.1145/321479.321481.
Performance information
Operation comments contain the operation time complexity in
big-O notation, with n
referring to the number of entries in the map and W referring to the
number of bits in an Int (32 or 64).
Operations like lookup, insert, and delete 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). These peculiar asymptotics are determined by the
depth of the Patricia trees:
even for an extremely unbalanced tree, the depth cannot be larger than
the number of elements n,
each level of a Patricia tree determines at least one more bit
shared by all subelements, so there could not be more
than W levels.
If all n keys in the tree are between 0 and N (or, say, between
-N and N), the estimate can be refined to O(\min(n, \log N)). If
the set of keys is sufficiently "dense", this becomes O(\min(n, \log n))
or simply the familiar O(\log n), matching balanced binary trees.
The most performant scenario for IntMap are keys from a contiguous subset,
in which case the complexity is proportional to \log n, capped by W.
The worst scenario are exponentially growing keys 1,2,4,\ldots,2^n,
for which complexity grows as fast as n but again is capped by W.
Binary set operations like union and intersection take
O(\min(n, m \log \frac{2^W}{m})) time, where m and n
are the sizes of the smaller and larger input maps respectively.
O(n). Build a map from a list of key/value pairs where
the keys are in ascending order.
Warning: This function should be used only if the keys are in
non-decreasing order. This precondition is not checked. Use fromList if the
precondition may not hold.
O(n). Build a map from a list of key/value pairs where
the keys are in ascending order, with a combining function on equal keys.
Warning: This function should be used only if the keys are in
non-decreasing order. This precondition is not checked. Use fromListWith if
the precondition may not hold.
O(n). Build a map from a list of key/value pairs where
the keys are in ascending order, with a combining function on equal keys.
Warning: This function should be used only if the keys are in
non-decreasing order. This precondition is not checked. Use fromListWithKey
if the precondition may not hold.
O(n). Build a map from a list of key/value pairs where
the keys are in ascending order and all distinct.
Warning: This function should be used only if the keys are in
strictly increasing order. This precondition is not checked. Use fromList
if the precondition may not hold.
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
insertWithconst.
O(\min(n,W)). Insert with a combining function.
insertWith f key value mp
will insert the pair (key, value) into mp if key does
not exist in the map. If the key does exist, the function will
insert f new_value old_value.
O(\min(n,W)). Insert with a combining function.
insertWithKey f key value mp
will insert the pair (key, value) into mp if key does
not exist in the map. If the key does exist, the function will
insert f key new_value old_value.
O(\min(n,W)). 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).
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")])
O(\min(n,W)). 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.
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"
O(\min(n,W)). 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.
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"
O(\min(n,W)). Look up 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")
O(\min(n,W)). The expression (alter f k map) alters the value x 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).
O(\min(n,W)). The expression (alterF f k map) alters the value x at
k, or absence thereof. alterF can be used to inspect, insert, delete,
or update a value in an IntMap. In short : lookup k <$> alterF f k m = f
(lookup k m).
Example:
interactiveAlter :: Int -> IntMap String -> IO (IntMap String)
interactiveAlter k m = alterF f k m where
f Nothing = do
putStrLn $ show k ++
" was not found in the map. Would you like to add it?"
getUserResponse1 :: IO (Maybe String)
f (Just old) = do
putStrLn $ "The key is currently bound to " ++ show old ++
". Would you like to change or delete it?"
getUserResponse2 :: IO (Maybe String)
alterF is the most general operation for working with an individual
key that may or may not be in a given map.
O(\min(n, m \log \frac{2^W}{m})), m \leq n.
The (left-biased) union of two maps.
It prefers the first map when duplicate keys are encountered,
i.e. (union == unionWithconst).
O(\min(n, m \log \frac{2^W}{m})), m \leq n.
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"
O(\min(n, m \log \frac{2^W}{m})), m \leq n.
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.
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"
O(\min(n, m \log \frac{2^W}{m})), m \leq n.
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"
Note: Prior to v0.6.4, Data.IntMap.Strict exposed a version of
compose that forced the values of the output IntMap. This version does
not force these values.
O(\min(n, m \log \frac{2^W}{m})), m \leq n.
A high-performance universal combining function. Using
mergeWithKey, all combining functions can be defined without any loss of
efficiency (with exception of union, difference and intersection,
where sharing of some nodes is lost with mergeWithKey).
Warning: Please make sure you know what is going on when using mergeWithKey,
otherwise you can be surprised by unexpected code growth or even
corruption of the data structure.
myUnionWithKey f m1 m2 = mergeWithKey (\k x1 x2 -> Just (f k x1 x2)) id id m1 m2
myDifferenceWithKey f m1 m2 = mergeWithKey f id (const empty) m1 m2
myIntersectionWithKey f m1 m2 = mergeWithKey (\k x1 x2 -> Just (f k x1 x2)) (const empty) (const empty) m1 m2
When calling mergeWithKey combine only1 only2, a function combining two
IntMaps is created, such that
if a key is present in both maps, it is passed with both corresponding
values to the combine function. Depending on the result, the key is either
present in the result with specified value, or is left out;
a nonempty subtree present only in the first map is passed to only1 and
the output is added to the result;
a nonempty subtree present only in the second map is passed to only2 and
the output is added to the result.
The only1 and only2 methods must return a map with a subset (possibly empty) of the keys of the given map.
The values can be modified arbitrarily. Most common variants of only1 and
only2 are id and constempty, but for example map f or
filterWithKey f could be used for any f.
O(n).
traverseWithKey f s == fromList$traverse ((k, v) -> (,) k $ f k v) (toList m)
That is, behaves exactly like a regular traverse except that the traversing
function also has access to the key associated with a value.
traverseWithKey (\k v -> if odd k then Just (succ v) else Nothing) (fromList [(1, 'a'), (5, 'e')]) == Just (fromList [(1, 'b'), (5, 'f')])
traverseWithKey (\k v -> if odd k then Just (succ v) else Nothing) (fromList [(2, 'c')]) == Nothing
O(n). The function mapAccumWithKey threads an accumulating
argument through the map in ascending order of keys.
let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")
mapAccumWithKey f "Everything:" (fromList [(5,"a"), (3,"b")]) == ("Everything: 3-b 5-a", fromList [(3, "bX"), (5, "aX")])
O(n \min(n,W)).
mapKeys f s is the map obtained by applying f to each key of s.
The size of the result may be smaller if f maps two or more distinct
keys to the same new key. In this case the value at the greatest of the
original keys is retained.
O(n \min(n,W)).
mapKeysWith c f s is the map obtained by applying f to each key of s.
The size of the result may be smaller if f maps two or more distinct
keys to the same new key. In this case the associated values will be
combined using c.
O(n).
mapKeysMonotonic f s == mapKeys f s, but works only when f
is strictly monotonic.
That is, for any values x and y, if x < y then f x < f y.
Semi-formally, we have:
and [x < y ==> f x < f y | x <- ls, y <- ls]
==> mapKeysMonotonic f s == mapKeys f s
where ls = keys s
This means that f maps distinct original keys to distinct resulting keys.
This function has slightly better performance than mapKeys.
Warning: This function should be used only if f is monotonically
strictly increasing. This precondition is not checked. Use mapKeys if the
precondition may not hold.
mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")]) == fromList [(6, "b"), (10, "a")]
O(n). Fold the keys and values in the map using the given right-associative
binary operator, such that
foldrWithKey f z == Prelude.foldr (uncurry f) z . toAscList.
For example,
keys map = foldrWithKey (\k x ks -> k:ks) [] map
let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
foldrWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"
O(n). Fold the keys and values in the map using the given left-associative
binary operator, such that
foldlWithKey f z == Prelude.foldl (\z' (kx, x) -> f z' kx x) z . toAscList.
For example,
keys = reverse . foldlWithKey (\ks k x -> k:ks) []
let f result k a = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
foldlWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (3:b)(5:a)"
O(n). A strict version of foldr. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.
vvaluefoldl' :: (a -> b -> a) -> a -> IntMapb -> a
O(n). A strict version of foldl. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.
O(n). A strict version of foldrWithKey. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.
O(n). A strict version of foldlWithKey. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.
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.
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")])
O(\min(n,W)). Take while a predicate on the keys holds.
The user is responsible for ensuring that for all Ints, j < k ==> p j >= p k.
See note at spanAntitone.
O(\min(n,W)). Drop while a predicate on the keys holds.
The user is responsible for ensuring that for all Ints, j < k ==> p j >= p k.
See note at spanAntitone.
O(\min(n,W)). Divide a map at the point where a predicate on the keys stops holding.
The user is responsible for ensuring that for all Ints, j < k ==> p j >= p k.
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")])
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")])
O(\min(n,W)). The expression (split k map) is a pair (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.
O(1). Decompose a map into pieces based on the structure
of the underlying tree. This function is useful for consuming a
map in parallel.
No guarantee is made as to the sizes of the pieces; an internal, but
deterministic process determines this. However, it is guaranteed that the
pieces returned will be in ascending order (all elements in the first submap
less than all elements in the second, and so on).
Note that the current implementation does not return more than two submaps,
but you should not depend on this behaviour because it can change in the
future without notice.
O(\min(n, m \log \frac{2^W}{m})), m \leq n.
The expression (isSubmapOfBy f m1 m2) returns 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:
O(\min(n, m \log \frac{2^W}{m})), m \leq n.
Is this a proper submap? (ie. a submap but not equal).
Defined as (isProperSubmapOf = isProperSubmapOfBy (==)).
O(\min(n, m \log \frac{2^W}{m})), m \leq n.
Is this a proper submap? (ie. a submap but not equal).
The expression (isProperSubmapOfBy f m1 m2) returns True when
keys m1 and keys 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: