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

[Edward Kmett]

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.

-Edward

On Tue, Jul 2, 2013 at 9: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<http://../base-4.6.0.1/Control-Applicative.html#t:Applicative> 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 haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20130702/9a9526c9/attachment.htm>