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

Shachaf Ben-Kiki shachaf at
Fri Jul 5 09:51:19 CEST 2013

On Tue, Jul 2, 2013 at 1:46 PM, Ryan Newton <rrnewton at> wrote:
>>     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:
> 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

* Following a discussion with Milan off-list, he implemented a simple
optimization in traverseWithKey which might have a significant impact.
. 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.


More information about the Libraries mailing list