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