**mapKeys**

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