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

[Roman Cheplyaka]

* Andreas Abel <andreas.abel at ifi.lmu.de> [2013-07-04 23:41:45+0300]
> Hello Roman,
> 
> On 04.07.2013 19:41, Roman Cheplyaka wrote:
> >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.
> 
> This called an in-order traversal of the tree.  (The node is handled
> in-between the sub trees.)
> 
>   foldrWithKey f z = foldr (uncurry f) z . toAscList
> 
> >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)
> 
> This is a post-order traversal. (The node is handled after the
> subtrees.)  This is a different thing.
> 
> >Perhaps this should be fixed?
> 
> I don't think so.  You would change the semantics.  (Try to convert a
> Map into an ascending key-value list with your new definition.)

Thanks Andreas, I missed the fact that this transformation changes the
traversal order. (Although I believe my version is pre-order, not
post-order.)

The same applies to the Ryan's traverseWithKey_, by the way — in his
patch he also handles the node before the subtrees. But that's easily
fixable.

After playing a bit with Ryan's benchmark, I no longer think that the
order matters much for the total number of allocations. Nor do I believe
in first-class vs non-first-class IO actions. All that should matter is
how many allocations we can move to the stack. But I haven't yet figured
out why exactly different versions differ so drastically in this regard.

Roman