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

Ryan Newton rrnewton at
Tue Jul 2 22:46:18 CEST 2013

>     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

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.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Libraries mailing list