[issue39210] Sorting falls back to use __gt__ when __lt__ is not present
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> _______________________________________
participants (4)
-
Mark Dickinson -
Steven D'Aprano
-
Tim Peters
-
Yan Mitrofanov