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

If you think about it, traverseWithKey already mimics the bracketing of IntMap internally. On Sun, Dec 30, 2012 at 5:42 AM, Milan Straka wrote:

Hi all,

...

-----Original message----- From: Edward Kmett 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