Map -text +containers

module Data.Map
containers Data.Map
Note: You should use Data.Map.Strict instead of this module if: * You will eventually need all the values stored. * The stored values don't represent large virtual data structures to be lazily computed. An efficient implementation of ordered maps from keys to values (dictionaries). These modules are intended to be imported qualified, to avoid name clashes with Prelude functions, e.g. > import qualified Data.Map as Map The implementation of Map is based on size balanced binary trees (or trees of bounded balance) as described by: * Stephen Adams, "Efficient sets: a balancing act", Journal of Functional Programming 3(4):553-562, October 1993, http://www.swiss.ai.mit.edu/~adams/BB/. * J. Nievergelt and E.M. Reingold, "Binary search trees of bounded balance", SIAM journal of computing 2(1), March 1973. Note that the implementation is left-biased -- the elements of a first argument are always preferred to the second, for example in union or insert. Operation comments contain the operation time complexity in the Big-O notation (http://en.wikipedia.org/wiki/Big_O_notation).
data Map k a
containers Data.Map.Lazy, containers Data.Map.Strict
A Map from keys k to values a.
map :: (Key -> Key) -> IntSet -> IntSet
containers Data.IntSet
O(n*min(n,W)). map f s is the set obtained by applying f to each element of s. It's worth noting that the size of the result may be smaller if, for some (x,y), x /= y && f x == f y
map :: (a -> b) -> IntMap a -> IntMap b
containers Data.IntMap.Strict, containers Data.IntMap.Lazy
O(n). Map a function over all values in the map. > map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
map :: (a -> b) -> Map k a -> Map k b
containers Data.Map.Lazy, containers Data.Map.Strict
O(n). Map a function over all values in the map. > map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
map :: Ord b => (a -> b) -> Set a -> Set b
containers Data.Set
O(n*log n). map f s is the set obtained by applying f to each element of s. It's worth noting that the size of the result may be smaller if, for some (x,y), x /= y && f x == f y
mapAccum :: (a -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
containers Data.IntMap.Strict, containers Data.IntMap.Lazy
O(n). The function mapAccum threads an accumulating argument through the map in ascending order of keys. > let f a b = (a ++ b, b ++ "X") > mapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])
mapAccum :: (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
containers Data.Map.Lazy, containers Data.Map.Strict
O(n). The function mapAccum threads an accumulating argument through the map in ascending order of keys. > let f a b = (a ++ b, b ++ "X") > mapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])
mapAccumRWithKey :: (a -> Key -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
containers Data.IntMap.Strict, containers Data.IntMap.Lazy
O(n). The function mapAccumR threads an accumulating argument through the map in descending order of keys.
mapAccumRWithKey :: (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
containers Data.Map.Lazy, containers Data.Map.Strict
O(n). The function mapAccumR threads an accumulating argument through the map in descending order of keys.
mapAccumWithKey :: (a -> Key -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
containers Data.IntMap.Strict, containers Data.IntMap.Lazy
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")])
mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
containers Data.Map.Lazy, containers Data.Map.Strict
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")])
mapEither :: (a -> Either b c) -> IntMap a -> (IntMap b, IntMap c)
containers Data.IntMap.Strict, containers Data.IntMap.Lazy
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")])
mapEither :: (a -> Either b c) -> Map k a -> (Map k b, Map k c)
containers Data.Map.Lazy, containers Data.Map.Strict
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 :: (Key -> a -> Either b c) -> IntMap a -> (IntMap b, IntMap c)
containers Data.IntMap.Strict, containers Data.IntMap.Lazy
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")])
mapEitherWithKey :: (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
containers Data.Map.Lazy, containers Data.Map.Strict
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")])
mapKeys :: (Key -> Key) -> IntMap a -> IntMap a
containers Data.IntMap.Strict, containers Data.IntMap.Lazy
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. > mapKeys (+ 1) (fromList [(5,"a"), (3,"b")]) == fromList [(4, "b"), (6, "a")] > mapKeys (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "c" > mapKeys (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "c"
mapKeys :: Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
containers Data.Map.Lazy, containers Data.Map.Strict
O(n*log n). 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. > mapKeys (+ 1) (fromList [(5,"a"), (3,"b")]) == fromList [(4, "b"), (6, "a")] > mapKeys (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "c" > mapKeys (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "c"
mapKeysMonotonic :: (Key -> Key) -> IntMap a -> IntMap a
containers Data.IntMap.Strict, containers Data.IntMap.Lazy
O(n*min(n,W)). 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. The precondition is not checked. Semi-formally, we have: > and [x < y ==> f x < f y | x <- ls, y <- ls] > ==> mapKeysMonotonic f s == mapKeys f s > This means that f maps distinct original keys to distinct resulting keys. This function has slightly better performance than mapKeys. > mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")]) == fromList [(6, "b"), (10, "a")]
mapKeysMonotonic :: (k1 -> k2) -> Map k1 a -> Map k2 a
containers Data.Map.Lazy, containers Data.Map.Strict
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. The precondition is not checked. Semi-formally, we have: > and [x < y ==> f x < f y | x <- ls, y <- ls] > ==> mapKeysMonotonic f s == mapKeys f s > This means that f maps distinct original keys to distinct resulting keys. This function has better performance than mapKeys. > mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")]) == fromList [(6, "b"), (10, "a")] > valid (mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")])) == True > valid (mapKeysMonotonic (\ _ -> 1) (fromList [(5,"a"), (3,"b")])) == False

Show more results