classification
Title: Remove 'guarantee' that sorting only relies on __lt__ from sorting howto
Type: Stage: resolved
Components: Documentation Versions: Python 3.8
process
Status: closed Resolution: not a bug
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: docs@python, mjpieters, rhettinger, steven.daprano, tim.peters
Priority: normal Keywords:

Created on 2019-01-03 21:35 by mjpieters, last changed 2019-08-22 18:37 by rhettinger. This issue is now closed.

Messages (8)
msg332949 - (view) Author: Martijn Pieters (mjpieters) * Date: 2019-01-03 21:35
Currently, the sorting HOWTO at https://docs.python.org/3/howto/sorting.html#odd-and-ends contains the text:

> The sort routines are guaranteed to use __lt__() when making comparisons between two objects. So, it is easy to add a standard sort order to a class by defining an __lt__() method

Nowhere else in the Python documentation is this guarantee made, however. That sort currently uses __lt__ only is, in my opinion, an implementation detail.

The above advice also goes against the advice PEP 8 gives:

> When implementing ordering operations with rich comparisons, it is best to implement all six operations (__eq__, __ne__, __lt__, __le__, __gt__, __ge__) rather than relying on other code to only exercise a particular comparison.
>
> To minimize the effort involved, the functools.total_ordering() decorator provides a tool to generate missing comparison methods.

The 'guarantee' seems to have been copied verbatim from the Wiki version of the HOWTO in https://github.com/python/cpython/commit/0fe095e87f727f4a19b6cbfd718d51935a888740, where that part of the Wiki page was added by an anonymous user in revision 44 to the page: https://wiki.python.org/moin/HowTo/Sorting?action=diff&rev1=43&rev2=44

Can this be removed from the HOWTO?
msg332951 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2019-01-03 22:20
I don't know that the language needs to define this, but sticking to __lt__ was a wholly deliberate design decision for CPython.
msg332954 - (view) Author: Steven D'Aprano (steven.daprano) * (Python committer) Date: 2019-01-04 00:39
> That sort currently uses __lt__ only is, in my opinion, an implementation detail.

Its only an implementation detail until the language specification defines it as a guarantee of the language. Then it becomes part of the sorting API.

Personally, I think it is a nice feature that sorting works for objects which define only __lt__, and it sounds like Tim is happy for that to be part of the sort API.

This is documented under list.sort() but not sorted():

https://docs.python.org/3/library/stdtypes.html#list.sort

https://docs.python.org/3/library/functions.html#sorted

Rather than removing it from the HOWTO, I would rather document that fact under sorted() as well.

If you still want to argue that we should not document this as a language guarantee, for the sake of other implementations such as Jython and IronPython, you should raise it on Python-Dev. It would probably help if you had other implementation maintainers state that this was a burden on them.

For what it is worth, it seems that Jython 2.5 supports this feature too.
msg332958 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-01-04 02:38
I also prefer to leave this as is.  FWIW, heapq and bisect are also deliberately based on __lt__.  The PEP 8 advice (something I wrote) is primarily about making code less fragile and avoiding surprising behavior.
msg332959 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2019-01-04 03:33
Steven, thanks for noticing the docs!  I was surprised to hear it wasn't documented, but not surprised enough to check myself ;-)

This decision was suggested by me, and endorsed by Guido, when designing timsort looking ahead to Python 3, where __cmp__ was going to vanish.  The convenience of needing to add only a single method to support a custom sort order is considerable.

Since it's working as designed and dccumented, and I know for certain that code in the wild relises on it, I'm inclined to reject this report.  However, rather than add more words to `sorted()`, I'd suggest removing words from `sorted()`, pointing instead to the `.sort()` docs for all specification of `sorted()`'s sorting behavior.
msg332965 - (view) Author: Martijn Pieters (mjpieters) * Date: 2019-01-04 10:38
Well, if this is indeed by design (and I missed the list.sort() reference) then I agree the HOWTO should not be changed!

I'd be happy to change this to asking for more explicit mentions in the docs for sorted, heapq and bisect that using only < (__lt__) is a deliberate choice.
msg332966 - (view) Author: Martijn Pieters (mjpieters) * Date: 2019-01-04 10:39
(I have no opinion on this having to be a language feature however)
msg350224 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-08-22 18:37
> Well, if this is indeed by design (and I missed the
> list.sort() reference) then I agree the HOWTO should not be changed

It is in fact by design :-)
History
Date User Action Args
2019-08-22 18:37:15rhettingersetstatus: open -> closed
resolution: not a bug
messages: + msg350224

stage: resolved
2019-01-04 21:39:09terry.reedysetversions: + Python 3.8, - Python 3.6
2019-01-04 10:39:28mjpieterssetmessages: + msg332966
2019-01-04 10:38:44mjpieterssetmessages: + msg332965
2019-01-04 03:33:01tim.peterssetmessages: + msg332959
2019-01-04 02:38:31rhettingersetassignee: docs@python -> rhettinger
messages: + msg332958
2019-01-04 00:39:08steven.dapranosetnosy: + steven.daprano
messages: + msg332954
2019-01-03 22:20:37tim.peterssetnosy: + tim.peters
messages: + msg332951
2019-01-03 21:35:41mjpieterscreate