On Tue, Aug 6, 2013 at 4:19 PM, Milan Straka <span dir="ltr"><<a href="mailto:fox@ucw.cz" target="_blank">fox@ucw.cz</a>></span> wrote:<br><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,<br>
<br>
> -----Original message-----<br>
> From: Edward Kmett <<a href="mailto:ekmett@gmail.com">ekmett@gmail.com</a>><br>
</div><div class="im">> Sent: 6 Aug 2013, 14:26<br>
><br>
> On Tue, Aug 6, 2013 at 2:09 PM, Milan Straka <<a href="mailto:fox@ucw.cz">fox@ucw.cz</a>> wrote:<br>
><br>
> > Hi Edward,I am not suggesting we should change the behaviour of existing<br>
> > functions<br>
> > 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>
> ><br>
><br>
> I wholeheartedly agree. =) I was just basing that on the code Ryan posted:<br>
><br>
> > traverseWithKey_ f = go<br>
> > where go Tip = pure ()<br>
> > go (Bin _ k v l r) = f k v *> go l *> go r<br>
> ><br>
> ><br>
> ... which visits the key/value pairs out of order unlike, say:<br>
><br>
> go (Bin _ k v l r = go l *> f k v *> go r<br>
<br>
</div>Oh, yes, we will definitely use the definition you suggest.<br>
<div class="im"><br>
> > 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>
> ><br>
><br>
> Sure, foldrM is typically implemented in terms of foldl and foldlM is<br>
> typically implemented in terms of foldr.<br>
><br>
> Do the usual definitions like that leak on a Map?<br>
<br>
</div>It is difficult to say whether it is a 'leak'. These methods (they are<br>
the same as Foldable.foldrM and Foldable.foldlM) heap-allocate space<br>
linear in the size of the map (to create the closures). When implemented<br>
directly, they do not heap-allocate.</blockquote><div><br></div><div>Ick. I hadn't walked through the expansion of those by hands and had admittedly just hoped they worked out of the box. </div><div><br></div><div>That means the similar combinators we have for them in lens probably also leak. =(</div>
<div><br></div><div>This indicates to me we may want to bite the bullet and move foldlM and foldrM into the Foldable class. </div><div><br></div><div>As hideous as that is, the unmitigable space leak strikes me as worse.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">
> traverseWithKey_ would normally be implemented with an appropriate newtype<br>
> and foldMapWithKey, rather than traverseWithKey. Does that also leak?<br>
<br>
</div>That does not leak, as Shachaf Ben-Kiki pointed out. That is one of the<br>
reasons why this discussion is so long :)<br>
<br>
BTW, Foldable.traverse_ also heap-allocates space linear in the size of<br>
the map, because it is defined as<br>
traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()<br>
traverse_ f = foldr ((*>) . f) (pure ())<br>
Maybe it would be better to define it using foldMap + the appropriate<br>
newtype? Then it would not heap-allocate, at least for Data.Map.<br></blockquote><div><br></div><div>Definitely. I'll talk to Shachaf and craft a suitable proposal to fix up traverse_.</div><div><br></div><div>-Edward</div>
</div>