On Tue, Jul 2, 2013 at 1:46 PM, Ryan Newton
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
If you're actually benchmarking it, you should note a few things: * As I mentioned, lens's actual implementation of this function is slightly different: -- The argument 'a' of the result should not be used! newtype Traversed a f = Traversed { getTraversed :: f a } instance Applicative f => Monoid (Traversed a f) where mempty = Traversed (pure (error "Traversed: value used")) Traversed ma `mappend` Traversed mb = Traversed (ma *> mb) with one "void" applied at the very end of the fold, instead of one in each step. This may or may not be better; it should probably be measured. * Following a discussion with Milan off-list, he implemented a simple optimization in traverseWithKey which might have a significant impact. See https://github.com/haskell/containers/commit/4d24ff5d08f0bb27ca73a9888286d64... . It should probably be considered in these benchmarks. * I haven't thought it through, but it's possible that using a "difference monoid" -- i.e. folding with Endo, the way Data.Foldable.foldr is implemented by default -- would also be useful to measure, to compare with the existing foldrWithKey. Shachaf