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

[Roman Cheplyaka]

* 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