Proposal: Add foldMapWithKey to Data.Map and Data.IntMap

[Milan Straka]

Hi all,

> -----Original message-----
> From: Edward Kmett <ekmett at gmail.com>
> Sent: 28 Dec 2012, 18:36
>
> I'd like to add foldMapWithKey to Data.Map and Data.IntMap.
> 
> Right now you can foldrWithKey and foldlWithKey on Data.Map and
> Data.IntMap, but you cannot foldMapWithKey.
> 
> You can fake this by using fold . mapWithKey but this requires converting
> the entire structure.
> 
> You can also implement it with traverseWithKey and the use of the Const Monoid
> in a manner similar to foldMapDefault.

One can implement foldMapWithKey as

foldMapWithKey f = foldlWithKey (\a k b -> a `mappend` f k b) mempty

This is a valid definition which does not create intermediate structure.
The difference to the proposed implementation is, as Edward mentions:

> When you have a monoid that can take advantage of the balanced nature of
> the tree, it'd be nice to be able to not lose the original near balanced
> parenthesization of the source tree.

Both definitions differ in the bracketing of the mappend-s.
This should be mentioned in the documentation of the foldMapWithKey.
However, while the bracketing of foldlWithKey and foldrWithKey is well
defined, the bracketing of foldMapWithKey depends on the internal
structure of the container. But it is probably safe to assume that the bracketing
will be "balanced" in some way for any implementation of the data structure.

Cheers,
Milan