Proposal: make minimumBy/maximumBy go through foldl', not foldr1

[Roman Cheplyaka]

To clarify: the implementation I used in the benchmark is monomorphic.
(I could have used foldl1' from Data.List instead). A polymorphic
implementation could compose that with Data.Foldable.toList, unless
someone comes up with an even faster polymorphic version.

On 10/29/2015 05:34 PM, Roman Cheplyaka wrote:
> I just realized (thanks to this reddit thread[1]) that minimumBy is now
> implemented through foldr1. Previously (before FTP), minimumBy from Data.List
> used foldl1, while minimumBy from Data.Foldable used foldr1.
> 
> I think that the way these were merged was a mistake.
> 
> Let's admit that the absolute majority of use cases for minimumBy are numbers,
> for which the comparison functions are strict in both arguments. Even for
> something like Bool, where comparison could potentially be in one of the
> arguments, the standard compare method is derived and is strict.
> 
> Now, for Foldable, there isn't necesarily a connection between the direction and
> the way fold is performed. For example, for Data.Map.Map both folds are
> tail-recursive. Yet foldr is non-tail-recursive at least for:
> 
> - good old lists
> - anything that uses the same convention for foldl/foldr as lists
> - anything that defines its foldable instance through conversion to lists
> - anything that uses the default implementation of foldr/foldr1
> 
> I also put a simple microbenchmark[2] to show the difference in performance;
> on it, the proposed implementation is more than 20x faster than the current one.
> 
> [1]: https://www.reddit.com/r/haskell/comments/3qpefo/a_very_unfortunate_error_message/
> [2]: http://lpaste.net/714261956202070016
> 


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20151029/6c592ee8/attachment.sig>