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

[Andreas Abel]

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.)

Cheers,
Andreas

-- 
Andreas Abel  <><      Du bist der geliebte Mensch.

Theoretical Computer Science, University of Munich
Oettingenstr. 67, D-80538 Munich, GERMANY

andreas.abel at ifi.lmu.de
http://www2.tcs.ifi.lmu.de/~abel/