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

4 Jul 2013

      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  wrote:
...
* Henning Thielemann  [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