Data.List.maximumBy uses counter-intuitive ordering

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Data.List.maximumBy uses counter-intuitive ordering

Johannes Waldmann-2
Dear all,

this was brought up on the GHC tracker (not by me)

https://ghc.haskell.org/trac/ghc/ticket/15921

and it was suggested for discussion here.

my summary: Data.List.maximumBy is right-biased,
minimumBy is left-biased, and none of this is documented.

- J.W.

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

Re: Data.List.maximumBy uses counter-intuitive ordering

Eric Mertens
Hello,

My opinion on this issue is that code should not be relying on the ordering of the choice made by maximumBy or minimumBy.

If we changed something I’d prefer to document that it is undefined what element is chosen when two are considered equal by the comparison function.

Code that relies on a particular earlier or later bias should use a function that makes it clear in the name that that’s what it’s doing. Readers should not be required to memorize the behavior of minimumBy or maximumBy in this regard to understand the code they are reading.

Best regards,
Eric

> On Dec 28, 2018, at 7:18 AM, Johannes Waldmann <[hidden email]> wrote:
>
> Dear all,
>
> this was brought up on the GHC tracker (not by me)
>
> https://ghc.haskell.org/trac/ghc/ticket/15921
>
> and it was suggested for discussion here.
>
> my summary: Data.List.maximumBy is right-biased,
> minimumBy is left-biased, and none of this is documented.
>
> - J.W.
>
> _______________________________________________
> 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
|

Re: Data.List.maximumBy uses counter-intuitive ordering

Henning Thielemann
In reply to this post by Johannes Waldmann-2

On Fri, 28 Dec 2018, Johannes Waldmann wrote:

> Dear all,
>
> this was brought up on the GHC tracker (not by me)
>
> https://ghc.haskell.org/trac/ghc/ticket/15921
>
> and it was suggested for discussion here.
>
> my summary: Data.List.maximumBy is right-biased,
> minimumBy is left-biased, and none of this is documented.

Btw. Data.Semigroup exports Min and Max that are both left-biased:

Prelude Data.Semigroup> min (Arg 2 3) (Arg 2 2) :: Arg Int Int
Arg 2 3
Prelude Data.Semigroup> max (Arg 2 3) (Arg 2 2) :: Arg Int Int
Arg 2 3
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Data.List.maximumBy uses counter-intuitive ordering

Mario Blažević
In reply to this post by Johannes Waldmann-2
On 2018-12-28 8:18 a.m., Johannes Waldmann wrote:

> Dear all,
>
> this was brought up on the GHC tracker (not by me)
>
> https://ghc.haskell.org/trac/ghc/ticket/15921
>
> and it was suggested for discussion here.
>
> my summary: Data.List.maximumBy is right-biased,
> minimumBy is left-biased, and none of this is documented.
>

Already discussed at least twice:

https://mail.haskell.org/pipermail/haskell-cafe/2011-September/095150.html
https://mail.haskell.org/pipermail/libraries/2013-September/020721.html

There are justifications for the current behaviour, but documenting it
can't harm anybody.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Data.List.maximumBy uses counter-intuitive ordering

Dan Burton
I agree with the proposal to make maximumBy left-biased, and to document this bias for both maximumBy and minimumBy.

-- Dan Burton


On Thu, Jan 3, 2019 at 3:28 PM Mario Blažević <[hidden email]> wrote:
On 2018-12-28 8:18 a.m., Johannes Waldmann wrote:
> Dear all,
>
> this was brought up on the GHC tracker (not by me)
>
> https://ghc.haskell.org/trac/ghc/ticket/15921
>
> and it was suggested for discussion here.
>
> my summary: Data.List.maximumBy is right-biased,
> minimumBy is left-biased, and none of this is documented.
>

Already discussed at least twice:

https://mail.haskell.org/pipermail/haskell-cafe/2011-September/095150.html
https://mail.haskell.org/pipermail/libraries/2013-September/020721.html

There are justifications for the current behaviour, but documenting it
can't harm anybody.
_______________________________________________
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
|

Re: Data.List.maximumBy uses counter-intuitive ordering

Ryan Reich
In reply to this post by Eric Mertens
I think this is the right way to go: undefined when the maximum is duplicated. It is not implausible, for instance, that someone's mental model or even an alternate implementation of this function would, say, use the quicksort-like binary search for the maximum, and that really could give any of the options because quicksort is not stable.

There is no right answer to this question and therefore no answer should be demanded unless there is a compelling reason of efficiency.

Definitely document this, though.


On Fri, Dec 28, 2018, 07:27 Eric Mertens <[hidden email] wrote:
Hello,

My opinion on this issue is that code should not be relying on the ordering of the choice made by maximumBy or minimumBy.

If we changed something I’d prefer to document that it is undefined what element is chosen when two are considered equal by the comparison function.

Code that relies on a particular earlier or later bias should use a function that makes it clear in the name that that’s what it’s doing. Readers should not be required to memorize the behavior of minimumBy or maximumBy in this regard to understand the code they are reading.

Best regards,
Eric

> On Dec 28, 2018, at 7:18 AM, Johannes Waldmann <[hidden email]> wrote:
>
> Dear all,
>
> this was brought up on the GHC tracker (not by me)
>
> https://ghc.haskell.org/trac/ghc/ticket/15921
>
> and it was suggested for discussion here.
>
> my summary: Data.List.maximumBy is right-biased,
> minimumBy is left-biased, and none of this is documented.
>
> - J.W.
>
> _______________________________________________
> 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
|

Re: Data.List.maximumBy uses counter-intuitive ordering

Carter Schonwald
Does the inclusion of semi groups in base give another option? ?  There’s perfectly nice left and right biased min and max semigroups. Though I think we only provide one flavor each for min and max. 


Either it is useful to document the behavior as an artifact of current implementation but not commit to the exact same semantic in future versions so as not to preclude future innovations ?


One fuzzy thought: it almost seems like there’s two semigroup structures in play here: the aggregation / aka min or max in this case, plus implicitly a second structure that provides the tie breaking structure in the case of equality , which is usually a left or right bias, but could be some other mechanism.  Is there a useful notion of a semigroup transformer or the like? 

On Thu, Jan 3, 2019 at 3:50 PM Ryan Reich <[hidden email]> wrote:
I think this is the right way to go: undefined when the maximum is duplicated. It is not implausible, for instance, that someone's mental model or even an alternate implementation of this function would, say, use the quicksort-like binary search for the maximum, and that really could give any of the options because quicksort is not stable.

There is no right answer to this question and therefore no answer should be demanded unless there is a compelling reason of efficiency.

Definitely document this, though.


On Fri, Dec 28, 2018, 07:27 Eric Mertens <[hidden email] wrote:
Hello,

My opinion on this issue is that code should not be relying on the ordering of the choice made by maximumBy or minimumBy.

If we changed something I’d prefer to document that it is undefined what element is chosen when two are considered equal by the comparison function.

Code that relies on a particular earlier or later bias should use a function that makes it clear in the name that that’s what it’s doing. Readers should not be required to memorize the behavior of minimumBy or maximumBy in this regard to understand the code they are reading.

Best regards,
Eric

> On Dec 28, 2018, at 7:18 AM, Johannes Waldmann <[hidden email]> wrote:
>
> Dear all,
>
> this was brought up on the GHC tracker (not by me)
>
> https://ghc.haskell.org/trac/ghc/ticket/15921
>
> and it was suggested for discussion here.
>
> my summary: Data.List.maximumBy is right-biased,
> minimumBy is left-biased, and none of this is documented.
>
> - J.W.
>
> _______________________________________________
> 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
|

Re: Data.List.maximumBy uses counter-intuitive ordering

Theodore Lief Gannon
Data.Ord.Down does roughly the same thing as your tiebreaker, I think. (Different semantics, but sits in the same place.) Note that it has no need to be a semigroup on its own!

On Fri, Jan 4, 2019, 7:41 AM Carter Schonwald <[hidden email] wrote:
Does the inclusion of semi groups in base give another option? ?  There’s perfectly nice left and right biased min and max semigroups. Though I think we only provide one flavor each for min and max. 


Either it is useful to document the behavior as an artifact of current implementation but not commit to the exact same semantic in future versions so as not to preclude future innovations ?


One fuzzy thought: it almost seems like there’s two semigroup structures in play here: the aggregation / aka min or max in this case, plus implicitly a second structure that provides the tie breaking structure in the case of equality , which is usually a left or right bias, but could be some other mechanism.  Is there a useful notion of a semigroup transformer or the like? 

On Thu, Jan 3, 2019 at 3:50 PM Ryan Reich <[hidden email]> wrote:
I think this is the right way to go: undefined when the maximum is duplicated. It is not implausible, for instance, that someone's mental model or even an alternate implementation of this function would, say, use the quicksort-like binary search for the maximum, and that really could give any of the options because quicksort is not stable.

There is no right answer to this question and therefore no answer should be demanded unless there is a compelling reason of efficiency.

Definitely document this, though.


On Fri, Dec 28, 2018, 07:27 Eric Mertens <[hidden email] wrote:
Hello,

My opinion on this issue is that code should not be relying on the ordering of the choice made by maximumBy or minimumBy.

If we changed something I’d prefer to document that it is undefined what element is chosen when two are considered equal by the comparison function.

Code that relies on a particular earlier or later bias should use a function that makes it clear in the name that that’s what it’s doing. Readers should not be required to memorize the behavior of minimumBy or maximumBy in this regard to understand the code they are reading.

Best regards,
Eric

> On Dec 28, 2018, at 7:18 AM, Johannes Waldmann <[hidden email]> wrote:
>
> Dear all,
>
> this was brought up on the GHC tracker (not by me)
>
> https://ghc.haskell.org/trac/ghc/ticket/15921
>
> and it was suggested for discussion here.
>
> my summary: Data.List.maximumBy is right-biased,
> minimumBy is left-biased, and none of this is documented.
>
> - J.W.
>
> _______________________________________________
> 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