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

[Ryan Newton]

In my case, I'm trying to avoid heap allocation, because in parallel
haskell it is death to performance.

My claim is that:

   - current version of foldrWithKey heap allocates in proportion to the
   input size
   - my proposed traverseWithKey_ doesn't
   - traverseWithKey_ may be a more obvious an idiom to some programmers
   than folding to compose an IO action (requires understanding the detailed
   interaction of laziness, optimizations, and first class IO actions)

It sounds like Roman's alternate foldrWithKey will be an improvement as
well, so I'll test it.

   -Ryan


On Thu, Jul 4, 2013 at 12:41 PM, Roman Cheplyaka <roma at ro-che.info> wrote:

> * Henning Thielemann <lemming at henning-thielemann.de> [2013-07-02
> 21:57:58+0200]
> >
> > On Tue, 2 Jul 2013, Ryan Newton wrote:
> >
> > >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?
> >
> > Since it is a foldr, the first action can be run without knowing the
> > following ones. That is, at no time all actions must be allocated.
>
> It's not a foldr you would expect.
> Here's the code:
>
>   foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
>   foldrWithKey f z = go z
>     where
>       go z' Tip             = z'
>       go z' (Bin _ kx x l r) = go (f kx x (go z' r)) l
>
> You can see that 'go' is (partially) driven by the tree structure.
>
> A more foldr-y foldr would look like
>
>   foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
>   foldrWithKey f z = go z
>     where
>       go z' Tip             = z'
>       go z' (Bin _ kx x l r) = f kx x (go (go z' r) l)
>
> Perhaps this should be fixed? (Note that I haven't done any testing.)
>
> Another note: I guess "non-allocating" in the title means that we're not
> allocating anything of the order of map size. Some stack-like allocation
> is inevitable since we're working with a tree, but it will be
> logarithmic in the map size.
>
> But then, it seems to me that the current version of foldrWithKey
> should satsify that criterion, only with a big(ger) constant factor.
> It always traverses the left branch accumulating z, then yields control
> to f.
>
> Roman
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20130704/f700e578/attachment.htm>