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

[Ryan Newton]

Hi all,

Thanks for the responses.  I want to go through and make sure I understand
these.

--------------------------------------------------------
First, Henning, won't both of these allocate in proportion to the size of
the map?

    Map.foldrWithKey (\k a -> f k a >>) (return ())
    Foldable.sequence_ . Map.mapWithKey f

In particular, will the compiler be able to avoid allocating when building
up that large monadic computation in the foldrWithKey?

--------------------------------------------------------
Edward said to use foldMapWithKey, which hasn't been released yet, but it
sounds like it will be.


https://github.com/ekmett/containers/commit/40187f32a43689ff02ca2b97465aa4fcd9f9d150

Even then, I might argue it is somewhat non-obvious to the programmers how
to use this to do a non-allocating "for-each".  For example, I am not
totally clear on what will happen with that tree of mappend calls -- will
it allocate thunks?  Further, IO is not a monoid, so am I to create an
instance of "Monoid (IO ())" in order to use foldMapWithKey to iterate over
the Map?

--------------------------------------------------------
On Tue, Jul 2, 2013 at 10:29 AM, Shachaf Ben-Kiki <shachaf at gmail.com> wrote:
*> 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_
*

That function looks more overloaded than the traverse in Data.Map that I'm
referring to, e.g. here:

http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Map-Strict.html#g:13

I'm afraid I don't understand the proposal then -- is it to use lens
somehow?  For the traversal I need to do over a Data.Map.Map, I need to fix
't' to be IO or Par or whatever I'm working with, so that the (k -> a -> t
b) function I'm passing in can do the effects I need.

To be specific I'm proposing providing these variants:

   traverseWithKey :: **Applicative t => (k -> a -> t b) -> Map k a -> t
(Map k b)
   traverseWithKey_ :: **Applicative t => (k -> a -> t ()) -> Map k a -> t
()

And without exposing the latter natively, I still don't understand how to
trick the former into not allocating, if that's the proposal.

   -Ryan


On Tue, Jul 2, 2013 at 2:54 PM, Edward Kmett <ekmett at gmail.com> wrote:

> On Tue, Jul 2, 2013 at 2:45 PM, Henning Thielemann <
> lemming at henning-thielemann.de> wrote:
>
>>   Foldable.sequence_ . Map.mapWithKey f
>
>
>
> which looks more elegant.
>>
>
> This has the unfortunate consequence that it builds an entire new map
> strictly before sequencing it, due to the fact that Data.Map is
> spine-strict. =(
>
> -Edward
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20130702/af6e3022/attachment.htm>