Proposal: Make minimumBy and maximumBy go through foldl1

[David Feuer]

I do not like the idea of linearity being a *syntactic* construct
rather than part of the type system. It seems likely to end up
limiting us in confusing ways. Also, I like types. But that's really
not relevant to this discussion.

On Wed, Jan 25, 2017 at 10:31 PM, Joe Hillenbrand <joehillen at gmail.com> wrote:
> Would you care to elaborate?
>
> On Wed, Jan 25, 2017 at 6:34 PM, David Feuer <david.feuer at gmail.com> wrote:
>> I doubt it very much, and some of us have serious doubts about the
>> extension as it stands.
>>
>> On Wed, Jan 25, 2017 at 8:58 PM, Joe Hillenbrand <joehillen at gmail.com> wrote:
>>> Would the (hopeful) imminent linear types extension help here?
>>>
>>> On Wed, Jan 25, 2017 at 4:24 PM, Edward Kmett <ekmett at gmail.com> wrote:
>>>> The current intent based on the ghc ticket traffic is to switch the
>>>> implementation to foldl1 for the next release as a stopgap, but leave the
>>>> door open to do something smarter in the future.
>>>>
>>>> The current foldr1 implementation is simply never a win, and a monoidal
>>>> version devolves to a right fold for lists with the same bad behavior.
>>>>
>>>> If we later on figure out a way to efficiently exploit a strict monoidal
>>>> accumulator for monoids that don't benefit from short-circuiting then a
>>>> number of current Foldable combinators could benefit including this one, so
>>>> we definitely want to leave the door open to doing things better in the
>>>> future, but for now the left fold is an easy improvement over the status
>>>> quo.
>>>>
>>>> -Edward
>>>>
>>>> On Wed, Jan 25, 2017 at 6:50 PM, David Laing <dave.laing.80 at gmail.com>
>>>> wrote:
>>>>>
>>>>> Hi all,
>>>>>
>>>>> I'm proposing that the implementations of minimumBy and maximumBy be
>>>>> changed from using foldl1 to foldr1.
>>>>>
>>>>> I found this in a GHC trac ticket[0] labelled 'Newcomer' that has more
>>>>> details / discussion on that.
>>>>>
>>>>> The points that stand out to me are:
>>>>> - the Haskell report says that those methods should be implemented in
>>>>> terms of foldl1 (although as instance methods of Foldable there might be
>>>>> some wiggle room there)
>>>>> - it helps solves a space leak (which at first glance feels like it might
>>>>> be a more common problem than the options that foldl1 removes)
>>>>> - from the discussion on the ticket, it seemed to be an agreeable middle
>>>>> ground
>>>>>
>>>>> As a side note: there have been a few proposals in the past to switch
>>>>> these functions to use foldl', which seemed to have stalled.  I don't know
>>>>> what the etiquette is around bringing up minor variations on old proposals
>>>>> again, so I apologise if I've breached some kind of protocol here.
>>>>>
>>>>> Although I guess I've already breached one protocol by pushing a  patch to
>>>>> Phabricator for review without getting sign-off from the Core Libraries
>>>>> Committee, so at least I'm being even handed with my clumsiness :)
>>>>>
>>>>> Cheers,
>>>>>
>>>>> Dave
>>>>>
>>>>> [0] https://ghc.haskell.org/trac/ghc/ticket/10830
>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> Libraries mailing list
>>>>> Libraries at haskell.org
>>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> Libraries mailing list
>>>> Libraries at haskell.org
>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>>
>>> _______________________________________________
>>> Libraries mailing list
>>> Libraries at haskell.org
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries