traverse and traverse_ visit elements in the same order as foldMap and foldr up to the Monoid/Applicative laws permitting (finite) reassociation and unit mapping.<div><br></div><div>It would stand to reason that traverseWithKey, traverseWithKey_, foldMapWithKey and foldrWithKey should retain that relationship.<div>
<br></div><div>I don't particularly care about what the order is, but that said, if you start breaking the invariant of the current ordering, you'll silently break a lot of people's code while still permitting it to typecheck.</div>
<div><br></div><div>This means that the errors will be insidious and difficult to find. e.g. the lens-based zipper code for walking into a Map will silently break and I'm sure I'm not the only one who has taken advantage of the existing ordering on these combinators.</div>
<div><br></div><div>-Edward<br><br><div class="gmail_quote">On Tue, Aug 6, 2013 at 9:51 AM, Ryan Newton <span dir="ltr"><<a href="mailto:rrnewton@gmail.com" target="_blank">rrnewton@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr"><div><p>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><div class="im"><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>> Fixing this involves *<b>nested</b>* CPR analysis, which I am working on at the moment.</p></div></div><div>Sounds neat! Is nested CPR analysis on a branch?</div>
<div class="im">
<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>
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><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"><div class="im">
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><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>
<span class="HOEnZb"><font color="#888888">
<div><br></div><div> -Ryan </div></font></span><div><br></div><div>P.S.: Relevant code:</div><div class="im"><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 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></div>
<br>_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org">Libraries@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/libraries" target="_blank">http://www.haskell.org/mailman/listinfo/libraries</a><br>
<br></blockquote></div><br></div></div>