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

Shachaf Ben-Kiki shachaf at
Tue Jul 2 16:29:02 CEST 2013

On Tue, Jul 2, 2013 at 6:58 AM, Ryan Newton <rrnewton at> wrote:
> If there's not an existing way to do this, I suppose this is a minor
> proposal.
> When writing monadic code that consumes a container (Set, Map) etc, I often
> find that I just want what iterators in imperative languages provide:  that
> is, to iterate over the contents of a large container, performing monadic
> effects along the way, but without allocating.
> The Foldable instance for Data.Map almost gives you what you want, but it
> only exposes the values, not their keys.  The "traverseWithKey" function is
> close too, but it builds a new Map as output:
> traverseWithKey :: Applicative t => (k -> a -> t b) -> Map k a -> t (Map k
> b)
> So in practice what I do, and what I assume others do is this:
> mapM_ f (toList myMap)
> And I don't see any fusion rules that would ameliorate this (they seem
> limited to pure code), so I'm betting I always pay the cost of conversion to
> a list.
> In the case of Data.Map the proposal is simply a "traverseWithKey_" that
> returns "t ()".  This follows the suffixing convention of mapM/mapM_ etc.
> More generally, it would be nice to do an audit of all popular containers
> with the assumption of very large collections that cant' be frivolously
> copied.
>    -Ryan
> P.S. Actually, there are a number of places where the standard libraries
> could do with a more complete set of "_" functions -- e.g. it always chafes
> to not have "atomicModifyIORef_", which would apply a (a->a) function like a
> regular modifyIORef.

Is there a reason you couldn't implement this just as well using
traverseWithKey, à la
? traverse-style functions let you choose your own Applicative, so
with the right choice of Applicative you can accumulate effects
without building up a new structure.

Of course, if you think this should be added for convenience, that's a
different matter, but the API already seems to provide the ability.

(Note: The implementation in lens uses undefined internally in one
place, but that's not necessary in general. See .)


More information about the Libraries mailing list