* Henning Thielemann
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