Add `mapWithKeyMonotonic : (k -> a -> (k, b)) -> Map k a -> Map k b`

[andreasabel]

I have come across situations where I both want to update the key in an order-preserving way and also change the value.
I suggest to add a function mapWithKeyMonotonic : (k -> a -> (k, b)) -> Map k a -> Map k b and respective variants for the other map types (e.g. mapWithKeyMonotonic : (Int -> a -> (Int, b)) -> IntMap a -> IntMap b).
This structure preserving rewrite can be done in a single pass. The current API only offers an implementation in two passes, mapWithKey and mapKeysMonotonic, and only for the cases where the function k -> a -> (k, b) can be split into (k -> k, k -> a -> b).

Bikeshed colorings:

1. mapWithKeyMonotonic
2. mapValuesAndKeysMonotonic
3. mapKeysAndValuesMonotonic
4. transformMonotonic
5. bimapMonotonic if we want to follow https://hackage-content.haskell.org/package/dbus-1.4.2/docs/DBus-Internal-Types.html#v:bimap

I guess I prefer 1 since it is a close variant of existing names, but I am open to alternatives.

Example uses: Derivative of polynomial implemented as Map Natural c of IntMap c: derive = Map.mapWithKeyMonotonic (\ d k -> (d-1, d*k)) . Map.delete 0.

[meooow25]

Seems reasonable to add. What do you think @treeowl?

However, the name mapWithKeyMonotonic doesn't fit with the existing mapWithKey.

mapWithKey :: (k -> a -> b) -> Map k a -> Map k b
mapWithKeyMonotonic :: (k -> a -> (k, b)) -> Map k a -> Map k b

I would also generalize the type.

mapMonotonicSomething :: (k1 -> a -> (k2, b)) -> Map k1 a -> Map k2 b

Finally, even if we don't have this, one can always go through toList and fromDistinctAscList.

mapMonotonicSomething :: (k1 -> a -> (k2, b)) -> Map k1 a -> Map k2 b
mapMonotonicSomething f = Map.fromDistinctAscList . map (uncurry f) . Map.toList

[treeowl]

Yes, with the generalized type. Going through lists will be less efficient, unless we have rewrite rules for that and they fire (I don't remember if we do).

[andreasabel]

However, the name mapWithKeyMonotonic doesn't fit with the existing mapWithKey.

It is not a terrible fit. Monotonic has been used in this package for a transformation of keys that preserves the tree structure. So I'd say this is comprensible. And mapWithKey has been used as a transformation of values that involves the keys.

But of course, I am open to better name suggestions (as I have already indicated in the original message).