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_me... [2]: http://lpaste.net/714261956202070016