<div dir="ltr"><div><p class="">On Sat, Aug 3, 2013 at 5:31 PM, Simon Peyton-Jones <span dir="ltr"><<a href="mailto:simonpj@microsoft.com" target="_blank">simonpj@microsoft.com</a>></span> wrote:<br></p><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div lang="EN-GB" link="blue" vlink="purple"></div></blockquote><p class="">> Fixing this involves *<b>nested</b>* CPR analysis, which I am working on at the moment.</p></div><div>Sounds neat! Is nested CPR analysis on a branch?</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div lang="EN-GB" link="blue" vlink="purple"><p class="">
This one I do not understand. Could you pull out the two alternative ways of phrasing this algorithm into a standalone form, in which one allocates more than t’other? Then I could investigate more easily. </p>
</div></blockquote><div class="gmail_extra">Milan pasted the relevant code (thanks) for traverseWithKey_ vs. foldWithKey which I reattach at the bottom of this email.<br><br><div class="gmail_quote">On Sun, Aug 4, 2013 at 7:48 AM, Sjoerd Visscher <span dir="ltr"><<a href="mailto:sjoerd@w3future.com" target="_blank">sjoerd@w3future.com</a>></span> wrote:<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
Would it help if traverse_ was implemented with foldMap using the Traverse_ newtype? In which case maybe we should fix Data.Foldable!<br></blockquote><div><br></div><div>That sounds good to me! And straightforward. Any objections?<br>
</div><div><br></div><div>Milan, why does it bother you that there is no specified order? I'm perfectly happy as long as its deterministic on a particular machine. (I have never been sure whether pure code in Haskell must be deterministic across multiple machines... numCapabilities was a counter example for a long time.) Aren't we already used to using Data.Map.toList and Data.Set.toList where order is not specified? Further, other languages (like Scheme) have maps/folds that do not specify order of side effects.</div>
<div><br></div><div> -Ryan </div><div><br></div><div>P.S.: Relevant code:</div><div><br></div><div><span style="font-family:arial,sans-serif;font-size:12.727272033691406px">traverseWithKey_ :: Applicative t => (k -> a -> t b) -> Map k a -> t ()</span><br style="font-family:arial,sans-serif;font-size:12.727272033691406px">
<span style="font-family:arial,sans-serif;font-size:12.727272033691406px"> traverseWithKey_ f = go</span><br style="font-family:arial,sans-serif;font-size:12.727272033691406px"><span style="font-family:arial,sans-serif;font-size:12.727272033691406px"> where go Tip = pure ()</span><br style="font-family:arial,sans-serif;font-size:12.727272033691406px">
<span style="font-family:arial,sans-serif;font-size:12.727272033691406px"> go (Bin _ k v l r) = f k v *> go l *> go r</span><br style="font-family:arial,sans-serif;font-size:12.727272033691406px"><div class="im" style="font-family:arial,sans-serif;font-size:12.727272033691406px">
<br> foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b<br> foldrWithKey f z = go z<br> where go z' Tip = z'<br> go z' (Bin _ kx x l r) = go (f kx x (go z' r)) l<br><br>
</div><span style="font-family:arial,sans-serif;font-size:12.727272033691406px">and we call them like this:</span><br style="font-family:arial,sans-serif;font-size:12.727272033691406px"><span style="font-family:arial,sans-serif;font-size:12.727272033691406px"> let actionTraverse _k 1000000 = putStrLn "Hit 1000000"</span><br style="font-family:arial,sans-serif;font-size:12.727272033691406px">
<span style="font-family:arial,sans-serif;font-size:12.727272033691406px"> actionTraverse _k _v = return ()</span><br style="font-family:arial,sans-serif;font-size:12.727272033691406px"><span style="font-family:arial,sans-serif;font-size:12.727272033691406px"> in traverseWithKey_ actionTraverse map</span><br style="font-family:arial,sans-serif;font-size:12.727272033691406px">
<br style="font-family:arial,sans-serif;font-size:12.727272033691406px"><span style="font-family:arial,sans-serif;font-size:12.727272033691406px">and this:</span><br style="font-family:arial,sans-serif;font-size:12.727272033691406px">
<span style="font-family:arial,sans-serif;font-size:12.727272033691406px"> let actionFoldr _k 1000000 z = putStrLn "Hit 1000000" *> z</span><br style="font-family:arial,sans-serif;font-size:12.727272033691406px">
<span style="font-family:arial,sans-serif;font-size:12.727272033691406px"> actionFoldr _k _v z = z</span><br style="font-family:arial,sans-serif;font-size:12.727272033691406px"><span style="font-family:arial,sans-serif;font-size:12.727272033691406px"> in foldrWithKey actionFoldr (pure ()) map</span><br>
</div><div><span style="font-family:arial,sans-serif;font-size:12.727272033691406px"><br></span></div></div></div></div>