<div dir="ltr">In my case, I'm trying to avoid heap allocation, because in parallel haskell it is death to performance.<div><br></div><div>My claim is that:</div><div><ul><li>current version of foldrWithKey heap allocates in proportion to the input size<br>
</li><li>my proposed traverseWithKey_ doesn't </li><li>traverseWithKey_ may be a more obvious an idiom to some programmers than folding to compose an IO action (requires understanding the detailed interaction of laziness, optimizations, and first class IO actions)</li>
</ul><div>It sounds like Roman's alternate foldrWithKey will be an improvement as well, so I'll test it.</div><div><br></div><div> -Ryan</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">
On Thu, Jul 4, 2013 at 12:41 PM, Roman Cheplyaka <span dir="ltr"><<a href="mailto:roma@ro-che.info" target="_blank">roma@ro-che.info</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
* Henning Thielemann <<a href="mailto:lemming@henning-thielemann.de" target="_blank">lemming@henning-thielemann.de</a>> [2013-07-02 21:57:58+0200]<br>
<div><div>><br>
> On Tue, 2 Jul 2013, Ryan Newton wrote:<br>
><br>
> >Hi all,<br>
> >Thanks for the responses. I want to go through and make sure I understand these.<br>
> ><br>
> >--------------------------------------------------------<br>
> >First, Henning, won't both of these allocate in proportion to the size of the map?<br>
> ><br>
> > Map.foldrWithKey (\k a -> f k a >>) (return ())<br>
> > Foldable.sequence_ . Map.mapWithKey f<br>
> ><br>
> >In particular, will the compiler be able to avoid allocating when building up that large monadic computation<br>
> >in the foldrWithKey?<br>
><br>
> Since it is a foldr, the first action can be run without knowing the<br>
> following ones. That is, at no time all actions must be allocated.<br>
<br>
</div></div>It's not a foldr you would expect.<br>
Here's the code:<br>
<br>
foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b<br>
foldrWithKey f z = go z<br>
where<br>
go z' Tip = z'<br>
go z' (Bin _ kx x l r) = go (f kx x (go z' r)) l<br>
<br>
You can see that 'go' is (partially) driven by the tree structure.<br>
<br>
A more foldr-y foldr would look like<br>
<br>
foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b<br>
foldrWithKey f z = go z<br>
where<br>
go z' Tip = z'<br>
go z' (Bin _ kx x l r) = f kx x (go (go z' r) l)<br>
<br>
Perhaps this should be fixed? (Note that I haven't done any testing.)<br>
<br>
Another note: I guess "non-allocating" in the title means that we're not<br>
allocating anything of the order of map size. Some stack-like allocation<br>
is inevitable since we're working with a tree, but it will be<br>
logarithmic in the map size.<br>
<br>
But then, it seems to me that the current version of foldrWithKey<br>
should satsify that criterion, only with a big(ger) constant factor.<br>
It always traverses the left branch accumulating z, then yields control<br>
to f.<br>
<span><font color="#888888"><br>
Roman<br>
</font></span></blockquote></div><br></div></div>