mapKeys can be more efficient

[meooow25]

containers/containers/src/Data/Map/Internal.hs

Lines 3208 to 3209 in 734785d

	mapKeys :: Ord k2 => (k1->k2) -> Map k1 a -> Map k2 a
	mapKeys f = fromList . foldrWithKey (\k x xs -> (f k, x) : xs) []

containers/containers/src/Data/Map/Internal.hs

Lines 3227 to 3228 in 734785d

	mapKeysWith :: Ord k2 => (a -> a -> a) -> (k1->k2) -> Map k1 a -> Map k2 a
	mapKeysWith c f = fromListWith c . foldrWithKey (\k x xs -> (f k, x) : xs) []

containers/containers/src/Data/Map/Strict/Internal.hs

Lines 1454 to 1455 in 734785d

	mapKeysWith :: Ord k2 => (a -> a -> a) -> (k1->k2) -> Map k1 a -> Map k2 a
	mapKeysWith c f = fromListWith c . foldrWithKey (\k x xs -> (f k, x) : xs) []

containers/containers/src/Data/IntMap/Internal.hs

Lines 2578 to 2579 in 734785d

	mapKeys :: (Key->Key) -> IntMap a -> IntMap a
	mapKeys f = fromList . foldrWithKey (\k x xs -> (f k, x) : xs) []

containers/containers/src/Data/IntMap/Internal.hs

Lines 2593 to 2595 in 734785d

	mapKeysWith :: (a -> a -> a) -> (Key->Key) -> IntMap a -> IntMap a
	mapKeysWith c f
	= fromListWith c . foldrWithKey (\k x xs -> (f k, x) : xs) []

containers/containers/src/Data/IntMap/Strict/Internal.hs

Lines 983 to 984 in 734785d

	mapKeysWith :: (a -> a -> a) -> (Key->Key) -> IntMap a -> IntMap a
	mapKeysWith c f = fromListWith c . foldrWithKey (\k x xs -> (f k, x) : xs) []

It would be more efficient to skip the intermediate list and foldl' over the map accumulating into another map.

An exception here is Map.mapKeys, since Map.fromList is O(n) on an already sorted list.

This raises a related question of whether fromListWith should also have such an optimization.

[meooow25]

I think it is a good idea to make mapKeysWith (and by extension mapKeys) O(n) when given a non-decreasing mapping function. This will be useful if

1. The author could have used mapKeysMonotonic but did not.
2. Consecutive runs of values are merged. mapKeysMonotonic cannot be used here since it required a strictly increasing function.
3. The map function is unknown, often applied on some type wrapping a Map, but it could perhaps be non-decreasing.

Hackage search can be used to examine some usages in the wild.

---

To do this, I am considering something like

data MapBuilder k a = ...

emptyBuilder :: MapBuilder k a
insertBuilder :: k -> a -> MapBuilder k a > MapBuilder a
insertWithBuilder :: (a -> a -> a) -> k -> a -> MapBuilder k a > MapBuilder a
finishBuilder :: MapBuilder a -> Map k a

implemented using a fromDistinctAscList-like Stack as long as elements are non-decreasing. Once an element is out-of-order, it switches to Map.insert. (This is just want fromList does today)

---

However, to apply a merging function to the last key and a new key, the fromDistinctAscList's MonoState won't work because it merges the stack too eagerly. I have an implementation that removes MonoState and just uses a Stack, keeping access to the last element. Just have to test how it holds up in benchmarks.
Edit: Made a PR, #1029