<div>On Tue, Aug 6, 2013 at 2:09 PM, Milan Straka <span dir="ltr">&lt;<a href="mailto:fox@ucw.cz" target="_blank">fox@ucw.cz</a>&gt;</span> wrote:</div><div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="im">Hi Edward,I am not suggesting we should change the behaviour of existing functions</div>
and traverseWithKey_ should definitely use the same order as<br>
traverseWithKey. Changing semantics without changing type signatures is<br>
really suspicious and usually plainly wrong.<br></blockquote><div><br></div><div>I wholeheartedly agree. =) I was just basing that on the code Ryan posted:</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">
<blockquote><span style="color:rgb(80,0,80);font-family:arial,sans-serif;background-color:rgb(255,255,255);font-size:12.727272033691406px">  traverseWithKey_ f = go<br></span><span style="color:rgb(80,0,80);font-family:arial,sans-serif;background-color:rgb(255,255,255);font-size:12.727272033691406px">    where go Tip = pure ()<br>
</span><span style="color:rgb(80,0,80);font-family:arial,sans-serif;background-color:rgb(255,255,255);font-size:12.727272033691406px">          go (Bin _ k v l r) = f k v *&gt; go l *&gt; go r</span></blockquote></blockquote>
<div><br></div><div>... which visits the key/value pairs out of order unlike, say:</div><div><br></div><div>  go (Bin _ k v l r = go l *&gt; f k v *&gt; go r</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

Nevertheless, I was wondering whether we should have a monadic fold<br>
(foldrM and foldlM) which would process the elements in a given order<br>
(ascending and descending, analogously to foldr and foldl). From one<br>
point of view, we can implement foldrM and foldlM using foldr and foldl,<br></blockquote><div><div><br></div><div>Sure, foldrM is typically implemented in terms of foldl and foldlM is typically implemented in terms of foldr. </div>
<div><br></div><div>Do the usual definitions like that leak on a Map?</div></div><div><pre><span class="hs-definition">foldrM</span> <span class="hs-keyglyph" style="color:red">::</span> <span class="hs-layout" style="color:red">(</span><span class="hs-conid">Foldable</span> <span class="hs-varid">t</span><span class="hs-layout" style="color:red">,</span> <span class="hs-conid">Monad</span> <span class="hs-varid">m</span><span class="hs-layout" style="color:red">)</span> <span class="hs-keyglyph" style="color:red">=&gt;</span> <span class="hs-layout" style="color:red">(</span><span class="hs-varid">a</span> <span class="hs-keyglyph" style="color:red">-&gt;</span> <span class="hs-varid">b</span> <span class="hs-keyglyph" style="color:red">-&gt;</span> <span class="hs-varid">m</span> <span class="hs-varid">b</span><span class="hs-layout" style="color:red">)</span> <span class="hs-keyglyph" style="color:red">-&gt;</span> <span class="hs-varid">b</span> <span class="hs-keyglyph" style="color:red">-&gt;</span> <span class="hs-varid">t</span> <span class="hs-varid">a</span> <span class="hs-keyglyph" style="color:red">-&gt;</span> <span class="hs-varid">m</span> <span class="hs-varid">b</span>
<a name="line-193"></a><span class="hs-definition">foldrM</span> <span class="hs-varid">f</span> <span class="hs-varid">z0</span> <span class="hs-varid">xs</span> <span class="hs-keyglyph" style="color:red">=</span> <span class="hs-varid">foldl</span> <span class="hs-varid">f&#39;</span> <span class="hs-varid">return</span> <span class="hs-varid">xs</span> <span class="hs-varid">z0</span>
<a name="line-194"></a>  <span class="hs-keyword" style="color:blue">where</span> <span class="hs-varid">f&#39;</span> <span class="hs-varid">k</span> <span class="hs-varid">x</span> <span class="hs-varid">z</span> <span class="hs-keyglyph" style="color:red">=</span> <span class="hs-varid">f</span> <span class="hs-varid">x</span> <span class="hs-varid">z</span> <span class="hs-varop">&gt;&gt;=</span> <span class="hs-varid">k</span></pre>
</div><div><pre><span class="hs-definition">foldlM</span> <span class="hs-keyglyph" style="color:red">::</span> <span class="hs-layout" style="color:red">(</span><span class="hs-conid">Foldable</span> <span class="hs-varid">t</span><span class="hs-layout" style="color:red">,</span> <span class="hs-conid">Monad</span> <span class="hs-varid">m</span><span class="hs-layout" style="color:red">)</span> <span class="hs-keyglyph" style="color:red">=&gt;</span> <span class="hs-layout" style="color:red">(</span><span class="hs-varid">a</span> <span class="hs-keyglyph" style="color:red">-&gt;</span> <span class="hs-varid">b</span> <span class="hs-keyglyph" style="color:red">-&gt;</span> <span class="hs-varid">m</span> <span class="hs-varid">a</span><span class="hs-layout" style="color:red">)</span> <span class="hs-keyglyph" style="color:red">-&gt;</span> <span class="hs-varid">a</span> <span class="hs-keyglyph" style="color:red">-&gt;</span> <span class="hs-varid">t</span> <span class="hs-varid">b</span> <span class="hs-keyglyph" style="color:red">-&gt;</span> <span class="hs-varid">m</span> <span class="hs-varid">a</span>
<a name="line-199"></a><span class="hs-definition">foldlM</span> <span class="hs-varid">f</span> <span class="hs-varid">z0</span> <span class="hs-varid">xs</span> <span class="hs-keyglyph" style="color:red">=</span> <span class="hs-varid">foldr</span> <span class="hs-varid">f&#39;</span> <span class="hs-varid">return</span> <span class="hs-varid">xs</span> <span class="hs-varid">z0</span>
<a name="line-200"></a>  <span class="hs-keyword" style="color:blue">where</span> <span class="hs-varid">f&#39;</span> <span class="hs-varid">x</span> <span class="hs-varid">k</span> <span class="hs-varid">z</span> <span class="hs-keyglyph" style="color:red">=</span> <span class="hs-varid">f</span> <span class="hs-varid">z</span> <span class="hs-varid">x</span> <span class="hs-varop">&gt;&gt;=</span> <span class="hs-varid">k</span></pre>
</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
nevertheless using linear heap space complexity compared to constant<br>
heap space complexity we can achieve with specialized implementations.<br>
This is the same situation as traverseWithKey_ -- we can implement it<br>
using traverseWithKey, but the heap space complexity increases.<br></blockquote><div><br></div><div><div>traverseWithKey_ would normally be implemented with an appropriate newtype and foldMapWithKey, rather than traverseWithKey. Does that also leak?</div>
<div><br>-Edward</div></div></div></div>