<div dir="ltr">The extra members that were added to the class weren't an exhaustive selection -- it is more that the proponents that were pushing them forward at the time stopped when they themselves got exhausted.<div><br></div><div>Having the option for tree-based vs. foldl' based accumulation would give the best of both worlds in one respect: O(log n) time bounds for some containers, much better constants for others.</div><div><br></div><div>The downside would be re-opening old wounds on the FTP front.<br><div><br></div><div>-Edward</div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Feb 7, 2016 at 5:44 AM, Joachim Breitner <span dir="ltr"><<a href="mailto:mail@joachim-breitner.de" target="_blank">mail@joachim-breitner.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Dear List,<br>
<br>
the following discussion stalled:<br>
<span class=""><br>
Am Donnerstag, den 29.10.2015, 17:34 +0200 schrieb Roman Cheplyaka:<br>
</span><div><div class="h5">> I just realized (thanks to this reddit thread[1]) that minimumBy is now<br>
> implemented through foldr1. Previously (before FTP), minimumBy from Data.List<br>
> used foldl1, while minimumBy from Data.Foldable used foldr1.<br>
><br>
> I think that the way these were merged was a mistake.<br>
><br>
> Let's admit that the absolute majority of use cases for minimumBy are numbers,<br>
> for which the comparison functions are strict in both arguments. Even for<br>
> something like Bool, where comparison could potentially be in one of the<br>
> arguments, the standard compare method is derived and is strict.<br>
><br>
> Now, for Foldable, there isn't necesarily a connection between the direction and<br>
> the way fold is performed. For example, for Data.Map.Map both folds are<br>
> tail-recursive. Yet foldr is non-tail-recursive at least for:<br>
><br>
> - good old lists<br>
> - anything that uses the same convention for foldl/foldr as lists<br>
> - anything that defines its foldable instance through conversion to lists<br>
> - anything that uses the default implementation of foldr/foldr1<br>
><br>
> I also put a simple microbenchmark[2] to show the difference in performance;<br>
> on it, the proposed implementation is more than 20x faster than the current one.<br>
><br>
> [1]: <a href="https://www.reddit.com/r/haskell/comments/3qpefo/a_very_unfortunate_error_message/" rel="noreferrer" target="_blank">https://www.reddit.com/r/haskell/comments/3qpefo/a_very_unfortunate_error_message/</a><br>
> [2]: <a href="http://lpaste.net/714261956202070016" rel="noreferrer" target="_blank">http://lpaste.net/714261956202070016</a><br>
<br>
</div></div>see <a href="https://mail.haskell.org/pipermail/libraries/2015-October/026430.html" rel="noreferrer" target="_blank">https://mail.haskell.org/pipermail/libraries/2015-October/026430.html</a> and<br>
<a href="https://ghc.haskell.org/trac/ghc/ticket/10830" rel="noreferrer" target="_blank">https://ghc.haskell.org/trac/ghc/ticket/10830</a>.<br>
<br>
It seems we have the choice of either<br>
 1 keeping this as they are, with Data.List.maximumBy having changed behaviour<br>
   for the worse from 7.8 to 7.10<br>
 2 changing the behavior of Foldable.maximumBy (from foldr to foldl)<br>
   and changing the behavior of Data.List.maximumBy back to what it was before,<br>
   and arguably the “better” definition.<br>
 3 adding minimumBy/maximumBy as a class method and changing only the list instance.<br>
<br>
This also raises the question of whether using foldl over foldl' is the<br>
right thing to do, as I was under the impression that foldl will (at<br>
least for lists)  always just accumulate a large heap of thunks, and<br>
one would always want to use foldl' instead. I postulate that if foldl'<br>
had been in the report, then it would have been used for maximumBy.<br>
<br>
So this yields option 4:<br>
<br>
 4 changing maximumBy to use foldl'<br>
<span class=""><br>
<br>
BTW, why is there no fold' method in Foldable that leaves the<br>
associativity (left, right, or mixed in case of a tree) to the Foldable<br>
</span>instance, and just implements the “best” strictly accumulating fold for<br>
the given data structure?<br>
<div class="HOEnZb"><div class="h5"><br>
<br>
Greetings,<br>
Joachim<br>
<br>
--<br>
Joachim “nomeata” Breitner<br>
  <a href="mailto:mail@joachim-breitner.de">mail@joachim-breitner.de</a> • <a href="http://www.joachim-breitner.de/" rel="noreferrer" target="_blank">http://www.joachim-breitner.de/</a><br>
  Jabber: <a href="mailto:nomeata@joachim-breitner.de">nomeata@joachim-breitner.de</a>  • GPG-Key: 0xF0FBF51F<br>
  Debian Developer: <a href="mailto:nomeata@debian.org">nomeata@debian.org</a><br>
<br>
</div></div><br>_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org">Libraries@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
<br></blockquote></div><br></div>