Comparison contracts in Python

Why this matters

Sorting, sets and heaps (a structure that always gives out its smallest item first) all ask your code one question many times: which of these two items comes first, or are these two items the same? Your code answers with a method, and Python trusts the answer. If the answers break a few simple rules, Python does not always stop with a clear error. Sometimes a list comes back in the wrong order. Sometimes a set keeps two items that are equal, or cannot find an item that is in it. Sometimes a TypeError or an AttributeError appears in a line that looks innocent.

The rules are called the comparison contract. A contract is an agreement. Your method promises to behave in a certain way, and the library depends on that promise. This lesson states the promise in plain words, gives you a checklist, and shows real output from programs where the promise is broken.

The arrays and comparators lesson covered sorted(), key functions and stability. This lesson is about the rules that any comparison must follow. The next lesson in this module, Partial sorting, is about finding the top few items without sorting everything.

The idea in plain words

A comparison method takes two items and answers a question. In Python, the sort and the heap only ask one question: "is this item less than that one?" That question is the method __lt__, which stands for "less than." It returns True or False. A comparison function, used with functools.cmp_to_key, answers a different way: it returns a negative number, zero or a positive number, as the arrays and comparators lesson showed.

Think of a referee at a chess tournament. The referee decides who wins each game. If the referee says A beats B, and then says B beats A for the same pair, the tournament cannot be run. If the referee says A beats B, B beats C, and C beats A, nobody can be ranked. A sort is a tournament that ranks every item, and it needs the referee to be consistent.

The comparison contract lists what consistent means. There are five rules, and the next sections explain each one with an example.

Less than: a class with one natural order

Many classes have an obvious order. Students can be ordered by score, dates by time, words by letters. A class can say so by defining __lt__. Python's sorted, min and heapq call __lt__ when they compare two items, and max calls __gt__, which total_ordering provides, so one method gives the class its natural order.

Writing all six comparison operators by hand is tedious. The decorator functools.total_ordering fills in the rest from __eq__ and __lt__. The program below defines a Student that sorts by score and uses total_ordering. It then sorts the students and compares some pairs.

The output is:

[Dev(60), Asha(72), Ravi(91)]
max: Ravi(91)
a == b: True a < b: False b < a: False
Ravi > Asha: True

The method __lt__ returns self.score < other.score, which is a plain comparison of two numbers. The method __eq__ says two students are equal when their scores match, so Asha and Meera are equal under this rule even though their names differ. The total_ordering decorator adds >, <= and >=, and it uses __eq__ and __lt__ to do so.

A class can define only one __lt__, so it has only one natural order. If you need other orders, pass a key to sorted, such as key=lambda s: s.name for alphabetical order. The __lt__ method is the default, and the key is the extra.

Python's sort uses __lt__ only. It never asks "is this item greater?" If __lt__ is written correctly, every other comparison follows from it.

The five rules

The Python documentation describes the contract in general terms. The rules below are the same ideas in plain words.

Rule 1: swapping the two items flips the answer

If a < b is true, then b < a must be false. If a and b are equal, both answers must be false. A comparison that says a is smaller and also says b is smaller breaks this rule. The sort does not know which one to put first.

For a comparison function that returns a number, the rule is the same: the sign of cmp(a, b) must be the opposite of the sign of cmp(b, a). If both answers are zero, that is also consistent, because both are equal.

Rule 2: the order must chain

If a comes before b, and b comes before c, then a must come before c. This is called transitivity, which is a long word for "the chain holds."

A rock-paper-scissors rule breaks this rule. Rock beats scissors, scissors beats paper, and paper beats rock. So rock comes before scissors, scissors comes before paper, and paper comes before rock. The chain loops, and no full order exists.

Rule 3: equal items behave the same against every third item

If a and b are equal for this rule, then any third item c must compare to a and to b in the same way. Otherwise a and b are not really the same to the sort.

The Version example later in this lesson follows this rule. It treats 1.0 and 1 as equal, and every other version compares to both of them in the same way.

Rule 4: the answer must not change while the data stays the same

A comparison must give the same answer every time you ask with the same two items. Do not use random numbers, the clock or input from a user inside a comparison method. Also, the fields that decide the order, and the fields that decide the hash (a number Python computes from an item to find it in a set or dictionary), must not change while the object is inside a set or a dictionary. If they do, the set keeps the object in the place it had before the change, and the lookup fails.

Rule 5: equal should mean equal, and equal items need equal hashes

A set or a dictionary uses two methods. The hash function, __hash__, picks a bucket for the item, and the equality method, __eq__, decides whether two items are the same. Two items that are equal must have the same hash. If they do not, the set can keep both of them, because it looks in the wrong bucket to find the other one.

Python has a special rule here. If a class defines __eq__ and does not define __hash__, Python sets __hash__ to None, and the objects can no longer go in a set. The safe choice is to define both methods with the same fields.

A checker you can run

Reading the rules is not enough to find a broken comparison. A small checker program can test the rules on a few sample items. The function check_contract takes a list of sample items and a comparison function that returns a number. It returns None when it finds no problem, and a short text when it does.

The output is:

natural order: None
rock-paper-scissors: transitivity fails for rock, scissors, paper
one-sided: antisymmetry fails for rock and paper

The first call returns None, which means no broken rule was found. The checker reports the first failure it finds, with the two or three items that caused it.

The expression (cmp(x, y) > 0) - (cmp(x, y) < 0) turns any number into 1, -1 or 0. Python treats True as 1 and False as 0, so subtracting two booleans gives the sign. This is the same sign trick the checker needs, and it works for any number the function returns.

The first loop checks that an item compared with itself gives zero. The second loop tests rule 1, the swap rule. The third loop tests rule 2, the chain rule. It looks at every triple of items, so the cost grows fast with the number of items. That is fine for a test, and you should not use it on large lists in real code.

The checker does not test rules 3, 4 and 5 fully. Those depend on the fields of the class, such as whether a field changes, and a comparison function alone does not show that.

The checker is only as good as the sample items you give it. If the sample misses the case that breaks the rule, the checker says None and the comparison may still be wrong. Use samples that include equal items, items with missing fields and items at the edges of the range.

What happens when a rule breaks

Broken rules often do not crash. The program keeps running and gives a wrong answer. The next three examples show the usual forms.

Sorting can give a wrong order without an error

The next program sorts 50 and 200 random numbers with three comparison functions. The first always says "the first item is bigger." The second says "the first item is bigger" for every pair that is not less, which includes equal numbers. The third gives a random answer.

The output is:

always 1 n=50: no error, sorted=False
a < b ? -1 : 1 n=50: no error, sorted=True
random n=50: no error, sorted=False
always 1 n=200: no error, sorted=False
a < b ? -1 : 1 n=200: no error, sorted=True
random n=200: no error, sorted=False

Three things stand out. The "always 1" comparison returns without an error, and the list is not sorted. The a < b ? -1 : 1 comparison returns a sorted list here. That is luck. The comparison still breaks rule 1 for equal items, because it says a is larger when a and b are equal. It works on this data and may fail on other data. The random comparison also finishes with no error, and the list is wrong.

Python does not check the contract while it sorts. Java can stop with Comparison method violates its general contract! in some of these cases, but Python gives no warning at all. The only protection is your own check, such as the function is_sorted in this program, and a test on sample items.

A set can keep items that are equal, or lose them

The next program has a Person class whose equality uses only the name. Its hash uses the age, which breaks rule 5. The two people are equal, but the set does not know that.

The output is:

bad hash: 2 {Asha/41, Asha/30}
equal? True
good hash: 1 {Asha/30}

The second line says the two people are equal, and the set still holds both. That is the broken case. The hash uses the age, so the two people land in different buckets, and the set never compares them with each other. The third line uses a hash of the name, which matches the equality rule, and the set keeps one Asha.

In the broken class, equal objects both stay in the set. In a real program, a set used to remove duplicates would keep duplicates silently. The fix is to make __hash__ use only the fields that __eq__ uses.

The next example shows a set that can no longer find an item after a change. The fields that decide the hash must not change while the object is in the set.

The output is:

contains box after change: False
contains a new Box(0): False
contains a new Box(7): False

The set put box into the bucket for hash 7. After the program changed box.size to 0, the set still looks for box in the bucket for 7, because that is where it was stored. The new hash is for 0, so the lookup goes to the wrong bucket and does not find it. Even a new Box(0) is not found, because the set has no item in the bucket for 0. The object is still in the set, but the set cannot find it. The fix is to avoid changing a field that decides the hash while the object is in a set or a dictionary. If you must change it, remove the object, change it, and add it again.

A null value stops the comparison

A Student class like the one in the first example does not handle None. Sorting a list that holds a None makes the comparison look for .score on None, and that raises an error inside the method:

The output is:

Traceback (most recent call last):
  File "/path/to/null.py", line 12, in <module>
    print(sorted([None, Student("A", 1)]))
          ~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/path/to/null.py", line 7, in __lt__
    return self.score < other.score
                        ^^^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'score'

The last line says None has no attribute named score. The error comes from inside __lt__, not from the sort. The method does not check the type of other, so it assumes other is a Student. Decide early whether None is allowed in your collection. If it is not, check for it in the method or before you add it. A method that handles None returns NotImplemented for other types, which lets Python decide. The common mistakes section shows the message for a class without __lt__.

A worked example: version numbers

The next example is harder. Version numbers like 1.10 and 1.9 are a common trap. As text, 1.10 comes before 1.9, because the character 1 is compared, then ., then 1 is compared against 9. As version numbers, 1.10 is newer than 1.9, because 10 is larger than 9.

The class below stores the numbers as a list of integers. Missing parts count as zero, so 1 and 1.0 have the same meaning. The rules from this lesson shape the code. The comparison pads the shorter list with zeros. The __eq__ method and the __hash__ method use the same meaning of equal, and the hash ignores trailing zeros.

The output is:

sorted: [1.0, 1.2.9, 1.2.10, 1.9, 1.9.1, 1.10, 2]
1.0 == 1: True
set size: 1
tuple compare (1, 10) > (1, 9): True
text compare '1.10' < '1.9': True

Walk through the parts that follow the rules. The _compare method pads the shorter list with zeros, so 2 and 2.0 are compared as the same. The comparison goes part by part, from left to right, and stops at the first difference. This is how 1.2.10 ends up after 1.2.9: the third part is compared as the number 10 against the number 9.

The last two lines show why the parts are stored as numbers, not text. Python's tuples compare their items in order, so (1, 10) > (1, 9) is True. The text "1.10" is less than "1.9", because the character "1" comes before "9". The text comparison is the trap that the class avoids.

The __hash__ method ignores trailing zeros. This matters for rule 5. Two equal versions, such as 1.0 and 1, must have the same hash, because a set uses the hash to find items first. The method removes trailing zeros before it hashes, so both versions give the same hash. The output set size: 1 shows that the set treats them as one item.

The checker from the earlier section can test this class too. Give it the list of versions and the comparison lambda a, b: (a > b) - (a < b), and it returns None.

A third example: the hidden tie

The last example shows a broken equality that looks reasonable. A task has an id and a priority. A busy team keeps tasks in a set, and the first version treats two tasks as the same when they share a priority.

The output is:

broken set: [T3(p1), T1(p2)] size 2
fixed set size: 4

The broken version says that tasks 1, 2 and 4 are equal, because they share priority 2. The set keeps only the first of them, and it drops the other two without an error. The program had four tasks and the set holds two. The priority looks like a reasonable key, which makes this easy to miss.

The fixed version breaks the tie with the id. Now equal means the same task, and the set keeps all four. The lesson is that when two different objects can have the same key, the equality must add a second field that makes them different. This is the idea from the multi-key sorting lesson, which builds keys from several fields.

Checklist for a comparison method

Use this list each time you write or change __lt__, __eq__, __hash__ or a comparison function.

1. The method returns True or False for __lt__, and a negative number, zero or a positive number for a comparison function.
2. Swapping the two items flips the answer, so a < b and b < a cannot both be true.
3. The order chains. If a comes before b and b comes before c, then a comes before c.
4. Equal for this rule means equal for every third item.
5. If __eq__ is defined, __hash__ is defined too, and it uses the same fields. Equal objects must have equal hashes.
6. The fields that decide the order and the hash do not change while the object is inside a set, a dictionary or a heap.
7. The method does not use random numbers, the clock or input from the user.
8. The method handles None or another type on purpose, by returning NotImplemented or by raising an error with a clear message.
9. __lt__ returns True or False, never a difference of numbers. The Common mistakes section shows what goes wrong.
10. You ran the checker on items that include equal items, items with missing fields and items at the edges of the range.

Common mistakes

These are the mistakes that show up most often, with the messages Python prints. Each message is taken from a real run, and the file paths and caret marks (the ^ and ~ lines) depend on the Python version and where you save the program.

Returning a number from __lt__

A __lt__ method must return a true or false value. A common slip is to return the difference of two numbers, which looks like a comparison function. Python does not refuse the number. It treats any nonzero number as true, and zero as false, so the sort reads the answers wrongly:

The output is:

sorted with subtraction __lt__: [2, 1, 3]

The list is not in order, and no error appeared. The result for 3 and 1 is 2, which is true, so the sort reads 3 as "less than" 1. The fix is to return the comparison itself, return self.score < other.score. The subtraction form belongs in a comparison function used with cmp_to_key, where the sign is what the sort reads.

Defining __eq__ without __hash__

If a class defines __eq__ and not __hash__, Python makes the class unhashable. Its objects cannot go into a set or be used as a dictionary key:

The output is:

Traceback (most recent call last):
  File "/path/to/nohash.py", line 9, in <module>
    print({PersonNoHash("Asha", 30)})
          ^^^^^^^^^^^^^^^^^^^^^^^^^^
TypeError: cannot use 'PersonNoHash' as a set element (unhashable type: 'PersonNoHash')

The last line says the class cannot be an element of a set, because it has no hash. The fix is to define __hash__ with the same fields as __eq__, for example return hash(self.name).

Sorting objects that do not define an order

If the class does not define __lt__, sorted cannot compare two items. The error appears when the first comparison runs:

The output is:

Traceback (most recent call last):
  File "/path/to/dog.py", line 6, in <module>
    print(sorted(dogs))
          ~~~~~~^^^^^^
TypeError: '<' not supported between instances of 'Dog' and 'Dog'

The message says that the < comparison has no meaning for two Dog objects. The fix is to define __lt__ on the class, or to give sorted a key, such as key=lambda d: d.name.

Putting objects with no order into a heap

The heapq module needs its items to compare with <. Pushing the first two items of a class with no __lt__ fails on the second push, because the heap has to compare them:

The output is:

Traceback (most recent call last):
  File "/path/to/heap.py", line 9, in <module>
    heapq.heappush(h, Item(2))
    ~~~~~~~~~~~~~~^^^^^^^^^^^^
TypeError: '<' not supported between instances of 'Item' and 'Item'

The first push works, because a heap with one item needs no comparison. The second push compares the new item with the first one, and that fails. The fix is the same as for sorted: define __lt__, or store tuples such as (priority, count, item) in the heap, where count is a number that is never repeated, so the numbers always decide the order.

Writing a comparison that does not always give the same answer

A comparison that uses random numbers or reads a changing field can make the result different on each run. The random comparison in the sorting example gave a wrong list with no warning. The fix is to remove the randomness. If you need a random order, shuffle the list yourself before sorting, and use a comparison that is fixed.

Forgetting __hash__ in a class with a custom __eq__

If __eq__ says two objects are equal and __hash__ uses other fields, the set keeps both of them, as the PersonBadHash example showed. The fix is to make __hash__ use only the fields that __eq__ uses, or to make __eq__ use the same fields as the hash.

Changing a field inside a set

The Box example shows the result. The set still holds the object in the old bucket, so a lookup fails after the change. The fix is to remove the object, change it, and add it back.

Practice

Try each exercise in a file first. Check your answer after you have made an attempt.

1. Is this comparison correct for check_contract? It compares two strings by length. Write the answer as a short paragraph, and say which rule it breaks, if any.

by_length = lambda a, b: 1 if len(a) > len(b) else 0

Show the answer

The comparison breaks rule 1. For "ab" and "abc", the length of "ab" is not greater, so the answer is 0. For "abc" and "ab", the length is greater, so the answer is 1. The answers 0 and 1 are not opposite signs, so the checker prints antisymmetry fails for ab and abc. A correct version returns a negative number when the first length is smaller, such as (len(a) > len(b)) - (len(a) < len(b)).

2. A class has a method that uses random.random() to break ties between items with equal scores. Explain which rule it breaks and what a user would see.

Show the answer

It breaks rule 4, because the answer changes on each call with the same two items. A user would see a list where items with equal scores appear in a different order each time the program runs. The fix is to break ties with a fixed field, such as a name or an id.

3. Write a Book class with __lt__ that orders books by author, and then by title. Use the built-in string comparison for both fields. Check that two books are equal only when both fields match.

Show the answer

class Book:
    def __init__(self, author, title):
        self.author = author
        self.title = title
 
    def __lt__(self, other):
        if self.author != other.author:
            return self.author < other.author
        return self.title < other.title
 
    def __eq__(self, other):
        return (self.author, self.title) == (other.author, other.title)
 
    def __hash__(self):
        return hash((self.author, self.title))

The __eq__ method compares both fields, and __hash__ uses the same two fields, so equal books have equal hashes. The __lt__ method checks the author first and only compares titles when the authors match.

4. Predict the output of check_contract for the strings ["a", "bb", "ccc"] with the comparison lambda x, y: len(x) - len(y). Then run it and compare your answer with the output.

Show the answer

The output is None. The comparison returns the difference of the lengths, which gives a negative number when the first string is shorter, a positive number when it is longer, and zero when the lengths are equal. Swapping the items flips the sign, and the chain holds, because length order is a simple number order. The subtraction works here because the sort reads only the sign of the result.

5. Give an example of two objects that are equal under __eq__ but have different hashes, and say what a set does with them. Then fix the class so both rules agree.

Show the answer

A Person with a name and an age is one example. If __eq__ compares only the name and __hash__ uses the age, two people named Asha with different ages are equal but land in different buckets. A set keeps both of them, as the PersonBadHash example shows. The fix is to make __hash__ use the name, the same field as __eq__.

Summary

• A comparison contract is a set of rules that __lt__, __eq__, __hash__ and comparison functions must follow, so that sorting, sets, dictionaries and heaps give correct results.
• The main rules are: swapping the items flips the answer, the order chains, equal means equal for every third item, the answer never changes for the same data, and equal items have equal hashes.
• A broken rule often gives a wrong answer without an error. A set can keep two equal items, and a sort can return a list in the wrong order.
• Define __hash__ whenever you define __eq__, and use the same fields in both.
• Break ties with a second field, and let __lt__ return a true or false value, not a number.
• Run the checker on sample items that include equal values and edge cases, and treat a None result as a sign, not a proof.