Quantcast

Proposal: Make minimumBy and maximumBy go through foldl1

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Proposal: Make minimumBy and maximumBy go through foldl1

David Laing
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

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Proposal: Make minimumBy and maximumBy go through foldl1

Edward Kmett-2
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 <[hidden email]> 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

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries



_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Proposal: Make minimumBy and maximumBy go through foldl1

Joe Hillenbrand
Would the (hopeful) imminent linear types extension help here?

On Wed, Jan 25, 2017 at 4:24 PM, Edward Kmett <[hidden email]> 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 <[hidden email]>
> 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
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>
>
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Proposal: Make minimumBy and maximumBy go through foldl1

David Feuer
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 <[hidden email]> wrote:

> Would the (hopeful) imminent linear types extension help here?
>
> On Wed, Jan 25, 2017 at 4:24 PM, Edward Kmett <[hidden email]> 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 <[hidden email]>
>> 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
>>> [hidden email]
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>
>>
>>
>> _______________________________________________
>> Libraries mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Proposal: Make minimumBy and maximumBy go through foldl1

Joe Hillenbrand
Would you care to elaborate?

On Wed, Jan 25, 2017 at 6:34 PM, David Feuer <[hidden email]> 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 <[hidden email]> wrote:
>> Would the (hopeful) imminent linear types extension help here?
>>
>> On Wed, Jan 25, 2017 at 4:24 PM, Edward Kmett <[hidden email]> 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 <[hidden email]>
>>> 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
>>>> [hidden email]
>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>>
>>>
>>>
>>> _______________________________________________
>>> Libraries mailing list
>>> [hidden email]
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>
>> _______________________________________________
>> Libraries mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: 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 <[hidden email]> wrote:

> Would you care to elaborate?
>
> On Wed, Jan 25, 2017 at 6:34 PM, David Feuer <[hidden email]> 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 <[hidden email]> wrote:
>>> Would the (hopeful) imminent linear types extension help here?
>>>
>>> On Wed, Jan 25, 2017 at 4:24 PM, Edward Kmett <[hidden email]> 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 <[hidden email]>
>>>> 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
>>>>> [hidden email]
>>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> Libraries mailing list
>>>> [hidden email]
>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>>
>>> _______________________________________________
>>> Libraries mailing list
>>> [hidden email]
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Proposal: Make minimumBy and maximumBy go through foldl1

Carter Schonwald
Agreed.  There's better ways of integrating linear types into core.  
On Wed, Jan 25, 2017 at 10:56 PM David Feuer <[hidden email]> wrote:
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 <[hidden email]> wrote:
> Would you care to elaborate?
>
> On Wed, Jan 25, 2017 at 6:34 PM, David Feuer <[hidden email]> 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 <[hidden email]> wrote:
>>> Would the (hopeful) imminent linear types extension help here?
>>>
>>> On Wed, Jan 25, 2017 at 4:24 PM, Edward Kmett <[hidden email]> 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 <[hidden email]>
>>>> 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
>>>>> [hidden email]
>>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> Libraries mailing list
>>>> [hidden email]
>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>>
>>> _______________________________________________
>>> Libraries mailing list
>>> [hidden email]
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Proposal: Make minimumBy and maximumBy go through foldl1

David Laing
In reply to this post by Edward Kmett-2
Hi,

Do the rest of the committee / folks on the list have any opinions either way on whether the stopgap measure should go into the next release?  I'm fine either way, but my understanding is that more input is better when it comes to proposals effecting `base`. 

I'll check back in two weeks from now and see if anyone has any additional thoughts / opinions / comments.

Cheers,

Dave

On Thu, Jan 26, 2017 at 10:24 AM, Edward Kmett <[hidden email]> 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 <[hidden email]> 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

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries




_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Proposal: Make minimumBy and maximumBy go through foldl1

Ben Gamari-2
David Laing <[hidden email]> writes:

> Hi,
>
> Do the rest of the committee / folks on the list have any opinions either
> way on whether the stopgap measure should go into the next release?  I'm
> fine either way, but my understanding is that more input is better when it
> comes to proposals effecting `base`.
>
> I'll check back in two weeks from now and see if anyone has any additional
> thoughts / opinions / comments.

Can the committee give a thumbs up/down on this? The window for merging
this to 8.2 is very nearly closed.

Cheers,

- Ben

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

signature.asc (497 bytes) Download Attachment
Loading...