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

[Shachaf Ben-Kiki]

On Tue, Jul 2, 2013 at 6:58 AM, Ryan Newton <rrnewton at gmail.com> 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
http://hackage.haskell.org/packages/archive/lens/3.9.0.2/doc/html/Control-Lens-Fold.html#v:traverseOf_
? 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
https://github.com/ekmett/lens/issues/177 .)

    Shachaf