O(n).
mapKeysMonotonic f s == mapKeys f
s, but works only when
f is strictly increasing (both
monotonic and injective). That is, for any values
x and
y, if
x <
y then
f x <
f
y and
f is injective (i.e. it never maps two input keys
to the same output key).
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