Re: Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

foldMapWithKey :: Monoid r => (k -> a -> r) -> M.Map k a -> r foldMapWithKey f = getConst . M.traverseWithKey (\k x -> Const (f k x))

Shachaf, thanks for fleshing it out. I updated the test with your version as well: https://gist.github.com/rrnewton/5912908 In short, it performs exactly the same as the foldrWithKey version, as you pointed out (32M allocation). In both cases, using first class monadic/applicative values seems to foil GHC. And btw, these do show the scaling you would expect, on 2M elements, it allocates 64MB, 4M -> 128MB, and so on, whereas the traverseWithKey_ version allocates a constant amount. -Ryan