New submission from Yan Mitrofanov mmxlviii@mail.ru:
Sorting documentation claims that sorting algorithm is only using < comparisons https://docs.python.org/3/howto/sorting.html#odd-and-ends https://docs.python.org/3/library/stdtypes.html#list.sort
When __lt__ implementation is missing, you get an exception class Foo: pass sorted([Foo(), Foo(), Foo()]) TypeError: '<' not supported between instances of 'Foo' and 'Foo'
However, if implement __gt__ method, you doesn't get an exception class Foo: def __gt__(self, other): return False sorted([Foo(), Foo(), Foo()]) # ok
Is it supposed to work like this? Or is it lack of documentation?
---------- assignee: docs@python components: Documentation messages: 359293 nosy: docs@python, yanmitrofanov priority: normal severity: normal status: open title: Sorting falls back to use __gt__ when __lt__ is not present versions: Python 3.8
_______________________________________ Python tracker report@bugs.python.org https://bugs.python.org/issue39210 _______________________________________
Steven D'Aprano steve+python@pearwood.info added the comment:
The `<` comparison uses `__lt__` dunder if it exists, otherwise it falls back on `__gt__`.
---------- nosy: +steven.daprano
_______________________________________ Python tracker report@bugs.python.org https://bugs.python.org/issue39210 _______________________________________
Mark Dickinson dickinsm@gmail.com added the comment:
To be precise, when doing `a < b`, either `a.__lt__` or `b.__gt__` can be used, since `__gt__` is considered the reversed / reflected version of `__lt__` (analogous to `__add__` and `__radd__`).
class A:
... def __lt__(self, other): return False ...
class B:
... def __gt__(self, other): return True ...
A() < B()
False
B() < A()
Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: '<' not supported between instances of 'B' and 'A'
sorted([A(), B()])
Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: '<' not supported between instances of 'B' and 'A'
sorted([B(), A()])
[<__main__.B object at 0x10dc4cca0>, <__main__.A object at 0x10dc68ca0>]
Presumably in the normal case, all the objects being sorted have the same type, and so in that case it's enough that the type implements at least one of __lt__ and __gt__.
---------- nosy: +mark.dickinson
_______________________________________ Python tracker report@bugs.python.org https://bugs.python.org/issue39210 _______________________________________
Yan Mitrofanov mmxlviii@mail.ru added the comment:
I got your point. So it seems that two pieces of documentation are not equivalent:
https://docs.python.org/3/howto/sorting.html#odd-and-ends
The sort routines are guaranteed to use __lt__() when making comparisons between two objects.
https://docs.python.org/3/library/stdtypes.html#list.sort
This method sorts the list in place, using only < comparisons between items.
----------
_______________________________________ Python tracker report@bugs.python.org https://bugs.python.org/issue39210 _______________________________________
Mark Dickinson dickinsm@gmail.com added the comment:
Right, the HOWTO language could possibly be improved. The intended and practical message is that you *only* need to provide __lt__ everywhere for sort to work.
---------- nosy: +rhettinger, tim.peters
_______________________________________ Python tracker report@bugs.python.org https://bugs.python.org/issue39210 _______________________________________
Tim Peters tim@python.org added the comment:
It's hard to be clearer without being annoyingly wordy. The truth is that sort does all comparisons by calling the CAPI:
PyObject_RichCompareBool(v, w, Py_LT)`
Sorting doesn't know (or care) how `PyObject_RichCompareBool()` is implemented. The closest Python equivalent is:
bool(v < w)
although then you also have to be clear that `bool` refers to the builtin function of that name.
Regardless, the sorting docs certainly aren't the place to explain how `v < w` is implemented. For example, that it _may_ end up calling `w.__gt__(v)` has nothing to do with sorting - instead that's about the semantics of comparison operators, regardless of context.
Since, best I can recall, nobody has asked about this before, perhaps the docs don't need "improvement" ;-) If they do, then I'm with Mark: the _intent_ was to say "if you want a class to implement its own sorting order, then it's sufficient to implement `__lt__` alone, and then sorting will use only that comparison operator if the list contains only instances of that class".
----------
_______________________________________ Python tracker report@bugs.python.org https://bugs.python.org/issue39210 _______________________________________
Steven D'Aprano steve+python@pearwood.info added the comment:
On Sun, Jan 05, 2020 at 02:19:49AM +0000, Tim Peters wrote:
Since, best I can recall, nobody has asked about this before
See discussion here:
https://mail.python.org/archives/list/python-dev@python.org/message/5AQMG6AD...
which followed from discussions on sort order. I was asked to provide a PR, but I have technical difficulties with github.
I think it's sufficient to say that sorting relies only on the `<` operator, and link to the section of the docs that map special dunders to comparison operators, namely here:
https://docs.python.org/3/reference/datamodel.html#object.__lt__
where it goes into detail about reflected methods and such.
----------
_______________________________________ Python tracker report@bugs.python.org https://bugs.python.org/issue39210 _______________________________________
-
Mark Dickinson -
Steven D'Aprano
-
Tim Peters
-
Yan Mitrofanov