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

Edward Kmett ekmett at
Tue Jul 2 20:51:39 CEST 2013

This could be implemented very easily with an appropriate Monoid with
foldMapWithKey. I put in a proposal for adding it (and a ticket on
containers) that received a couple of +1s, but I confess I never followed
up on it with Milan and Johan after the proposal period ended.

A simpler construction that works today for this case would be to just use
foldrWithKey or foldlWithKey.


On Tue, Jul 2, 2013 at 9: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<http://../base-> t
> => (k -> a -> t b) -> Map <http://Data-Map-Lazy.html#t:Map> k a -> t (Map<http://Data-Map-Lazy.html#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.
> _______________________________________________
> Libraries mailing list
> Libraries at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Libraries mailing list