# map -package:Cabal -package:base -package:text -package:dlist -package:blaze-html package:containers -is:module

O(n). Map a function over all values in the map.
```map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
```
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
O(n). Map a function over all values in the map.
```map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
```
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
A Map from keys k to values a. The Semigroup operation for Map is union, which prefers values from the left operand. If m1 maps a key k to a value a1, and m2 maps the same key to a different value a2, then their union m1 <> m2 maps k to a1.
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")])
```
O(n). The function mapAccumRWithKey threads an accumulating argument through the map in descending order of keys.
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). 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")])
```
Map covariantly over a WhenMatched f k x, using only a 'Functor f' constraint.
Map covariantly over a WhenMissing f x, using only a 'Functor f' constraint.
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"
```
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
where ls = keys 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")]
```
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.
```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"
```
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"
```
Map over the entries whose keys are missing from the other map, optionally removing some. This is the most powerful SimpleWhenMissing tactic, but others are usually more efficient.
```mapMaybeMissing :: (Key -> x -> Maybe y) -> SimpleWhenMissing x y
```
```mapMaybeMissing f = traverseMaybeMissing (\k x -> pure (f k x))
```
but mapMaybeMissing uses fewer unnecessary Applicative operations.
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"
```
Map over the entries whose keys are missing from the other map.
```mapMissing :: (k -> x -> y) -> SimpleWhenMissing x y
```
```mapMissing f = mapMaybeMissing (\k x -> Just \$ f k x)
```
but mapMissing is somewhat faster.
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")]
```
Map over the entries whose keys are missing from the other map, optionally removing some. This is the most powerful SimpleWhenMissing tactic, but others are usually more efficient.
```mapMaybeMissing :: (k -> x -> Maybe y) -> SimpleWhenMissing k x y
```
```mapMaybeMissing f = traverseMaybeMissing (\k x -> pure (f k x))
```
but mapMaybeMissing uses fewer unnecessary Applicative operations.
Map over the entries whose keys are missing from the other map.
```mapMissing :: (k -> x -> y) -> SimpleWhenMissing k x y
```
```mapMissing f = mapMaybeMissing (\k x -> Just \$ f k x)
```
but mapMissing is somewhat faster.
Map covariantly over a WhenMatched f k x y.