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

Ryan Newton rrnewton at
Tue Jul 2 15:58:10 CEST 2013

If there's not an existing way to do this, I suppose this is a minor

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<../base-> t
=> (k -> a -> t b) -> Map <Data-Map-Lazy.html#t:Map> k a -> t
(Map<Data-Map-Lazy.html#t:Map> k

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


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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Libraries mailing list