Skip to content

Python: Implementing rich comparison the correct way.

December 13, 2010

Since quite some time the so called “rich comparison methods”, ie __lt__, __le__, __eq__, __ge__, __gt__ and __ne__, has been around in Python and preferred to the old __cmp__, and in Python 3 __cmp__ is gone, so you must use the rich methods. That’s six methods instead of one, so most people try to avoid doing that, and use some mixin or other technique to only implement one. But that is surprisingly tricky, and is in fact so tricky that the official Python documentation points to a recipe that is incorrect. Even worse, this incorrect recipe has been included into Python 2.7! (If I knew this was planned, I would have written this post earlier).

The recipe in question is the “Total Ordering” recipe, in Python 2.7 included as functools.total_ordering. And the fault it makes is that it flips the comparison around. If the class you implement doesn’t implement the greater than method, __gt__ it will add a method to your class that asks the other object to do a less than comparison. In practice it does this:

__gt__ = lambda self, other: other < self

That sounds extremely reasonable. The problem is that your comparison methods can indicate that they don’t know how to compare self to the other object. They do this by returning NotImplemented. Python will then ask the other object. In other words,  Python will do exactly this “reversal” of comparisons all by itself. What happens then if you use the total_ordering deocrator, and then compare self to an object that doesn’t know how to compare itself to you?

  1. You ask a if it is less than b.
  2. The total_ordering methods will ask b if it is greater than a.
  3. b will return NotImplemented, hence telling Python that is does not know how to compare itself to a.
  4. Python will then ask a if it is less than b.
  5. And you got infinite recursion!

Here is code that will demonstrate this in Python 2.7:

>>> class MinimalOrdering(object):
...     
...     def __init__(self, value):
...         self._value = value
...         
...     def __lt__(self, other):
...         try:
...             return self._value < other._value
...         except AttributeError:
...             # I don't know how to compare to other
...             return NotImplemented
... 
>>> from functools import total_ordering
>>> @total_ordering
... class TotalOrder(object):
...     
...     def __init__(self, value):
...         self.value = value
...         
...     def __lt__(self, other):
...         return self.value < other.value
... 
>>> total = TotalOrder(1)
>>> mini = MinimalOrdering(2)
>>> total > mini
Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
 File "/opt/python27/lib/python2.7/functools.py", line 56, in <lambda>
 '__lt__': [('__gt__', lambda self, other: other < self),
....waaaaaayyyyyyy later....
File "/opt/python27/lib/python2.7/functools.py", line 56, in <lambda>
 '__lt__': [('__gt__', lambda self, other: other < self),
RuntimeError: maximum recursion depth exceeded

In short: never, ever in your rich comparison methods, ask the other object to do the comparison.

Here is the recipe I use instead. (Or well, I don’t, I used something more complicated, but a comment from Martin von Löwis started a process in my head that ended up in this, much simplified version. So this is the recipe I *will* use, in the future). It’s a mixin. If you are allergic to multiple inheritance you can make it into a class decorator instead, but I like mixins.

class ComparableMixin(object):
    def _compare(self, other, method):
        try:
            return method(self._cmpkey(), other._cmpkey())
        except (AttributeError, TypeError):
            # _cmpkey not implemented, or return different type,
            # so I can't compare with "other".
            return NotImplemented

    def __lt__(self, other):
        return self._compare(other, lambda s,o: s < o)

    def __le__(self, other):
        return self._compare(other, lambda s,o: s <= o)

    def __eq__(self, other):
       return self._compare(other, lambda s,o: s == o)

    def __ge__(self, other):
        return self._compare(other, lambda s,o: s >= o)

    def __gt__(self, other):
        return self._compare(other, lambda s,o: s > o)

    def __ne__(self, other):
        return self._compare(other, lambda s,o: s != o)

Not so difficult. Note how instead of delegating to the other object, I delegate to a _cmpkey() method (that was Martins brilliant idea) and if the other object does not have a _cmpkey() method, or returns a different type from what your class does, it will return NotImplemented, and Python will then delegate to the other object. This is how it’s designed to work.

You use this by subclassing from the mixin and implementing the _cmpkey() method:

class Comparable(ComparableMixin):
    def __init__(self, value):
        self.value = value

    def _cmpkey(self):
        return self.value

Which is simple enough. You don’t even need to implement one comparison method, you just return a key that can be compared. Suddenly all need to think when implementing comparison is gone. :-)

Feedback on this is welcome!

About these ads

From → plone, python, python3

8 Comments
  1. jörgen permalink

    self.value < self.value

    should be:

    self.value < other.value

    ?

  2. Right. (Although the method isn’t called in my example).

  3. I just ran into this very issue with total_ordering. I wrote up a proper implementation of total_ordering that takes NotImplemented into account. It’s written in terms of __lt__ (and __eq__), but I imagine it could be extended to support the other three rich comparison functions as well.

    It will also generate __ne__ from __eq__ if __ne__ doesn’t exist.

    def sane_total_ordering(cls):
    def __ge__(self, other):
    lt = self.__lt__(other)
    if lt is NotImplemented:
    return NotImplemented
    return not lt
    def __le__(self, other):
    lt = self.__lt__(other)
    if lt is NotImplemented:
    return NotImplemented
    eq = self.__eq__(other)
    if eq is NotImplemented:
    return NotImplemented
    return lt or eq
    def __gt__(self, other):
    le = __le__(self, other) # NOTE we’re using the __le__ defined above
    if le is NotImplemented:
    return NotImplemented
    return not le
    ops = [(f.__name__, f) for f in [__ge__, __le__, __gt__]]
    predefined = set(dir(cls))
    if “__lt__” not in predefined:
    raise ValueError(“Must define __lt__”)
    for opname, opfunc in ops:
    if opname not in predefined:
    setattr(cls, opname, opfunc)
    if “__eq__” in predefined and “__ne__” not in predefined:
    setattr(cls, “__ne__”, lambda self, other: not (self == other))
    return cls

  4. Hm, my comment somehow got flattened. I’ve put the function up at http://www.opengroove.org/sane_total_ordering.txt for reference.

  5. Note your __lt__ in TotalOrdering is incorrectly defined (it doesn\’t return a value, and also does not include the type check on other). Also (more importantly) note that in Python 3.2, the total_ordering issue is not present — running the example code fails on an AttributeError (because of the lack of type checking in TotalOrder\’s __lt__).

  6. The link for the total_ordering recipe is also incorrect, it’s Raymond Hettinger’s recipe that’s actually used: http://code.activestate.com/recipes/576685/

  7. Don’t forget to implement __ne__, as the total ordering does NOT do this for you.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,320 other followers

%d bloggers like this: