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. 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. We can use this in the lens library for more efficient zippers on these containers, but in general having access to a 'balanced' foldMap is useful for any such container, and it seems odd not to be able to get at the keys in this orientation when you can go so every other way. A patch that implements the proposed operation is available here: https://github.com/haskell/containers/pull/24 Discussion Period: 2 weeks -Edward