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

Ryan Newton rrnewton at
Tue Jul 2 21:32:44 CEST 2013

Hi all,

Thanks for the responses.  I want to go through and make sure I understand

First, Henning, won't both of these allocate in proportion to the size of
the map?

    Map.foldrWithKey (\k a -> f k a >>) (return ())
    Foldable.sequence_ . Map.mapWithKey f

In particular, will the compiler be able to avoid allocating when building
up that large monadic computation in the foldrWithKey?

Edward said to use foldMapWithKey, which hasn't been released yet, but it
sounds like it will be.

Even then, I might argue it is somewhat non-obvious to the programmers how
to use this to do a non-allocating "for-each".  For example, I am not
totally clear on what will happen with that tree of mappend calls -- will
it allocate thunks?  Further, IO is not a monoid, so am I to create an
instance of "Monoid (IO ())" in order to use foldMapWithKey to iterate over
the Map?

On Tue, Jul 2, 2013 at 10:29 AM, Shachaf Ben-Kiki <shachaf at> wrote:
*> Is there a reason you couldn't implement this just as well
using traverseWithKey, à la

That function looks more overloaded than the traverse in Data.Map that I'm
referring to, e.g. here:

I'm afraid I don't understand the proposal then -- is it to use lens
somehow?  For the traversal I need to do over a Data.Map.Map, I need to fix
't' to be IO or Par or whatever I'm working with, so that the (k -> a -> t
b) function I'm passing in can do the effects I need.

To be specific I'm proposing providing these variants:

   traverseWithKey :: **Applicative t => (k -> a -> t b) -> Map k a -> t
(Map k b)
   traverseWithKey_ :: **Applicative t => (k -> a -> t ()) -> Map k a -> t

And without exposing the latter natively, I still don't understand how to
trick the former into not allocating, if that's the proposal.


On Tue, Jul 2, 2013 at 2:54 PM, Edward Kmett <ekmett at> wrote:

> On Tue, Jul 2, 2013 at 2:45 PM, Henning Thielemann <
> lemming at> wrote:
>>   Foldable.sequence_ . Map.mapWithKey f
> which looks more elegant.
> This has the unfortunate consequence that it builds an entire new map
> strictly before sequencing it, due to the fact that Data.Map is
> spine-strict. =(
> -Edward
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Libraries mailing list