Searching for map

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) -> Map k a -> Map k b

map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b

O(n). Map a function over all values in the map.

> map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]

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

module Data.Map

An efficient implementation of maps from keys to values (dictionaries).

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

> import Data.Map (Map)
> 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

A Map from keys k to values a.

mapAccum :: (a -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)

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)

mapAccumWithKey :: (a -> Key -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)

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)

mapEither :: (a -> Either b c) -> IntMap a -> (IntMap b, IntMap c)

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 :: Ord k => (a -> Either b c) -> Map k a -> (Map k b, Map k c)

mapEitherWithKey :: (Key -> a -> Either b c) -> IntMap a -> (IntMap b, IntMap c)

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 :: Ord k => (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)

mapKeys :: Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a

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 smallest of these 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 :: (k1 -> k2) -> Map k1 a -> Map k2 a

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
> where ls = keys 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

mapKeysWith :: Ord k2 => (a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a

O(n*log n). 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.

> mapKeysWith (++) (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "cdab"
> mapKeysWith (++) (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "cdab"

mapMaybe :: (a -> Maybe b) -> IntMap a -> IntMap b

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"

mapMaybe :: Ord k => (a -> Maybe b) -> Map k a -> Map k b

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 :: (Key -> a -> Maybe b) -> IntMap a -> IntMap b