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

[Carter Schonwald]

I'd definitely like a fold' , it'd have more laws / be more portable than
the others, at least for associative computations.  Would that be a strict
version of fold map?

On Sunday, February 7, 2016, Joachim Breitner <mail at joachim-breitner.de>
wrote:

> Dear List,
>
> the following discussion stalled:
>
> Am Donnerstag, den 29.10.2015, 17:34 +0200 schrieb Roman Cheplyaka:
> > 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
>
> see https://mail.haskell.org/pipermail/libraries/2015-October/026430.html
>  and
> https://ghc.haskell.org/trac/ghc/ticket/10830.
>
> It seems we have the choice of either
>  1 keeping this as they are, with Data.List.maximumBy having changed
> behaviour
>    for the worse from 7.8 to 7.10
>  2 changing the behavior of Foldable.maximumBy (from foldr to foldl)
>    and changing the behavior of Data.List.maximumBy back to what it was
> before,
>    and arguably the “better” definition.
>  3 adding minimumBy/maximumBy as a class method and changing only the list
> instance.
>
> This also raises the question of whether using foldl over foldl' is the
> right thing to do, as I was under the impression that foldl will (at
> least for lists)  always just accumulate a large heap of thunks, and
> one would always want to use foldl' instead. I postulate that if foldl'
> had been in the report, then it would have been used for maximumBy.
>
> So this yields option 4:
>
>  4 changing maximumBy to use foldl'
>
>
> BTW, why is there no fold' method in Foldable that leaves the
> associativity (left, right, or mixed in case of a tree) to the Foldable
> instance, and just implements the “best” strictly accumulating fold for
> the given data structure?
>
>
> Greetings,
> Joachim
>
> --
> Joachim “nomeata” Breitner
>   mail at joachim-breitner.de <javascript:;> •
> http://www.joachim-breitner.de/
>   Jabber: nomeata at joachim-breitner.de <javascript:;>  • GPG-Key:
> 0xF0FBF51F
>   Debian Developer: nomeata at debian.org <javascript:;>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20160210/7425a0bf/attachment.html>