Feature request: `traverseKeys` and `traverseKeysWith`

[mixphix]

Currently there are functions

mapKeys :: (Ord k) => (j -> k) -> Map j a -> Map k a
traverse :: (Applicative f) => (a -> f b) -> Map k a -> f (Map k b)

but nothing of the type (Applicative f, Ord k) => (j -> f k) -> Map j a -> f (Map k a).

A sample implementation:

traverseKeys :: (Applicative f, Ord k) => (j -> f k) -> Map j a -> f (Map k a)
traverseKeys f = fmap fromList . traverse (\(j, a) -> (,a) <$> f j) . assocs

traverseKeysWith :: (Applicative f, Ord k) => (a -> a -> a) -> (j -> f k) -> Map j a -> f (Map k a)
traverseKeysWith c f = fmap (fromListWith c) . traverse (\(j, a) -> (,a) <$> f j) . assocs

which is O(n log n), if I'm not mistaken; though I haven't looked through the internals of the implementation to dig for further optimizations.

[sjakobi]

For consistency, these additions make sense. I guess traverseKeysMonotonic should be added too then. (I'm not sure why there is no mapKeysMonotonicWith.)

Since IntMap offers the same API here, IntMap variants would be required too.

Let me ask you first though, @bi-functor: Do you have an actual need for these functions, or did you simply notice the current inconsistency of the API?

[mixphix]

I do have a need for these functions!

We have a newtype wrapper for Map that lifts Semigroup values (can’t wait for #539 btw), and we foldMap over rows in our database. Depending on the user viewing the result, we want to replace some metadata in the keys with other database data (obtained monadically). Calculating this metadata for each row is expensive, but doing one traversal when the values have been accumulated is far less so.

[sjakobi]

Unfortunately mapKeysWith has the same pitfall as fromListWith (haskell-unordered-containers/unordered-containers#264):

> x = fromList [(1, [1]), (2, [2])]
> mapKeysWith (++) (const 3) x
fromList [(3,[2,1])]

As long as we haven't added a better alternative to fromListWith, we might as well stick with this pattern for traverseKeysWith.

@treeowl What do you think about this feature request?

[sjakobi]

(I'm not sure why there is no mapKeysMonotonicWith.)

It's because all the mapped keys are distinct – there's no need to combine any.

[imuli]

I also have need of this function - for parsing the keys into a more restrictive type.

[imuli]

Based on the implementation of mapKeysWith we have:

-- | /O(n*log n)/.
-- @'traverseKeysWith' c f s@ is the map obtained by applying @f@ to each key of @s@,
-- and then sequencing the keys in an applicative context.
--
-- 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@. The value at the greater of the two original keys
-- is used as the first argument to @c@.
--
-- > traverseKeysWith (++) (\x -> [x,x+1]) (fromList [(1,"b"), (2, "a")]) == [fromList [(1,"b"),(2,"a")],fromList [(1,"b"),(3,"a")],fromList [(2,"ab")],fromList [(2,"b"),(3,"a")]]
traverseKeysWith :: (Ord k', Applicative m) => (v -> v -> v) -> (k -> m k') -> Map k v -> m (Map k' v)
traverseKeysWith c f = fmap (M.fromListWith c) . M.foldrWithKey (\k x -> liftA2 (:) (flip (,) x <$> f k)) (pure [])
{-# INLINABLE traverseKeysWith #-}

I'm not sure that the description or the example is the most illuminating however.

(edit: also completely missed the sample implementations given in the initial report)