---

Background

As we've explored some features of Python that you may not have encountered before, a recurring theme has emerged. For the most part, the functions and classes built into Python and its standard library don't possess special abilities that aren't available within the code you write. Objects of pre-existing types can be context managers, but objects of your types can, too. Objects of many pre-existing types can be iterated using for loops, but so can objects of your types. You have to be aware of the mechanisms that make these things possible, but the important thing is that they are possible; most mechanisms the underlie Python are exposed and documented, which means your code can hook into them just as well as built-in code can. This is among the hallmarks of a well-designed programming language.

Collectively, the mechanisms that govern how Python objects interact with each other within a running Python program are known as the Python data model. Both in this course and your prior coursework, you'll already have seen some parts of this model, even if you've never heard it put into these terms before. Here are a few familiar ideas from the Python data model.

• When an object needs to be displayed in the Python shell, we see its representation, which is determined by a call to its __repr__ method.
• When a new object is created, it's initialized by way of a call to its __init__ method. Any arguments passed to its constructor are forwarded to its __init__ method.
• After the context expression of a with statement is evaluated, its result becomes a context manager, at which point its __enter__ method is called. When the with statement is exited, its __exit__ method is called.
• When we begin iterating an object that's iterable, its __iter__ method is called, which returns an iterator. That iterator, in turn, provides a __next__ method that is called to produce each value in the iteration, one at a time.
• When we call a method on an object, the call is transformed into a call to a function stored in an attribute of that object's class, with an extra argument (that we usually accept into a parameter named self) added before the others to represent the object on which the method was called. (There are some technical details that make this happen, too, and this is also something that you can modify when the need arises. Very few aspects of Python are magical.)

As we've seen before, all of the mechanisms described above rely on what we call protocols, which rely on the presence of one or more dunder methods, such as __init__, __enter__, __exit__, __iter__, __next__, and __get__. Virtually every time we interact with any object for any purpose in Python, at least one dunder method is called behind the scenes, even if we rarely call them ourselves. These dunder methods form the basis of how objects interact; their presence, alongside the fact that their meanings are documented and well-understood by seasoned Python programmers, ensures that we can modify most of what happens during those interactions when our designs require it. We can't change the fact that iterating an object causes __iter__ and __next__ methods to be called, but we can change what happens when they are, which means we can make iteration behave in any way we'd like. We can't change that the with statement requires __enter__ and __exit__ methods, but, by providing our own __enter__ and __exit__ methods, we can apply the concept of context management to any problem for which it's suited.

So, the key to improving our ability to design Python programs — writing programs that are "Pythonic," in the sense that using our functions and classes feels just like using the ones that are built in — is understanding as much of the Python data model as we can. We don't need every detail all the time, but every available detail is applicable to a problem we might have. When we solve problems the way Python does, we find that our functions and classes naturally "plug into" the things that are built in, and vice versa. When an entire community of programmers uses a programming language the same way, the community's ability to solve problems rapidly increases, because common problems are solved once and solved well, with the tools used to solve them combining naturally in ways that no one considered originally. We can stand on the shoulders of giants without losing our balance.

The price to be paid is that we have to learn the details. The payoff, though, is immense, so we'd be well-served to spend the time learning them. And, fortunately, the details rarely change, except to the extent that new details are added; once we know how iterators work, for example, that's how they'll likely continue to work for as long as we use Python. So, we at least want to be aware of what's available and the common threads that tie the features of Python's data model together. We can always look the details up again when we need them, even if we've forgotten some of them by then, but it's a lot harder to look things up when we don't know what we're looking for.

So, let's dive in and see what else we can find in the Python data model.

---

Lengths

In Python, we say that an object is sized if it can be asked for a length. The usual way to ask is to pass the object as an argument to the built-in len function. Strings, lists, tuples, ranges, sets, and dictionaries are all examples of sized objects, though not all objects are sized; integers, for example, are not.

>>> len('Boo')
    3
>>> len([1, 2, 3, 4, 5])
    5
>>> len(18)
    Traceback (most recent call last):
      ...
    TypeError: object of type 'int' has no len()

The MyRange class we wrote in a previous lecture is a good example of a class whose objects ought to be sized — if MyRange(10) comprises ten integers, then we could reasonably say its length is 10 — but this feature was missing from our implementation.

>>> len(MyRange(10))
    Traceback (most recent call last):
      ...
    TypeError: object of type 'MyRange' has no len()

Fortunately, there is a simple protocol by which we can add this feature to a class. All we need to do is write one extra method in our class:

• __len__(self), which returns an integer specifying the length of self.

Since a MyRange doesn't actually store any of its values, we'd need to iterate them if we wanted to count them, which means would could build a list of those values and then ask that list for its length.

class MyRange:
    ...

    def __len__(self):
        return len([x for x in self])

But we should be aware of the costs of our solutions; this works, but could we do substantially better? If there are n values in the range, this requires O(n) time to iterate through them, as well as O(n) memory to store them in a list. But if all we want to know is how many values are in our range, we have no need to store them; we just need to count them. What if we used a generator comprehension instead? Generators have no length, which rules out len(x for x in self), but we could transform each value into a 1 and then sum them up.

class MyRange:
    ...

    def __len__(self):
        return sum(1 for x in self)

If there are ten values in our range, we'll be summing the ten 1's that we generated, so this should produce the right answer. This technique reduces our memory usage to O(1), because we're now generating one value at a time, ignoring it (in favor of the value 1), and then adding 1 to a running sum. This is roughly equivalent to having written a loop instead.

class MyRange:
    ...

    def __len__(self):
        count = 0

        for value in self:
            count += 1

        return count

So, this is an improvement from a memory perspective, but we're still spending O(n) time, because we're still iterating the values in our range from beginning to end. A larger improvement would be to eliminate the iteration of the values altogether, though this would only be possible if we could find some other to deduce how many there are. Fortunately, the values in a MyRange follow a straightforward pattern, so we can instead calculate the length of a pattern with an arithmetic formula, by dividing the difference between stop and start by step, then applying a little bit of finesse to handle the edge cases properly.

class MyRange:
    ...

    def __len__(self):
        return max(0, math.ceil((self._stop - self._start) / self._step))

This version runs in O(1) time and uses O(1) memory. It's always made up of one subtraction, one division, one ceiling operation, and determining the maximum of exactly two integers. Whether the range is extremely long or very short, the sequence of operations is always the same, so its cost remains constant, regardless of the range's length.

Note, too, that if MyRange also supported negative step values, as well — ours didn't — then we'd need to adjust our formula some more, but it would still be possible to calculate a length in both constant time and memory.

---

Truthiness

There are many situations in Python where objects are treated as truth values, which is to say that they're considered either to be truthy (i.e., treated as though they're a boolean True) or falsy (i.e., like a boolean False). This is why the conditional expression of an if statement or a while loop can evaluate to any type of object, or why an iterable containing any types of objects can be passed to the built-in functions any or all.

Making that feature work requires a decision on the fundamental question: Which objects are considered truthy and which are considered falsy? The design of Python answers that question for its built-in types, including rules such as these.

• None is falsy.
• True is truthy, while False is falsy.
• Numbers that are zero are falsy, while others are truthy.
• Empty strings are falsy, while others are truthy.
• Empty lists are falsy, while others are truthy.

But what about objects of the classes we write? Under what conditions are they truthy? Under what conditions are they falsy? And, most importantly, can we decide those conditions, instead of leaving it to Python to decide?

>>> class Person:
...     def __init__(self, name):
...         self._name = name
...
>>> p1 = Person('Alex')
>>> bool(p1)
    True       # A Person with a non-empty name is truthy.
>>> p2 = Person('')
>>> bool(p2)
    True       # A Person with an empty name is also truthy.

From our experimentation, it appears that objects of our classes are always truthy, but there's more to the story than meets the eye, though. Given what we know already about the Python data model, we can reasonably expect that one or more dunder methods will allow us to alter this outcome.

How lengths impact truthiness

We saw previously that we can give objects a length by writing a __len__ method in their class. We've also seen that empty strings and empty lists — whose lengths are zero — are considered to be falsy. What happens to objects of our classes when they have lengths?

>>> len(MyRange(10))
    10
>>> bool(MyRange(10))
    True            # A MyRange with a non-zero length is truthy.
>>> len(MyRange(5, 5))
    0
>>> bool(MyRange(5, 5))
    False           # A MyRange with a zero length is falsy.

For objects that are sized (i.e., those that implement a __len__ method), their lengths can be used to determine truthiness. If calculating lengths is inexpensive, and if we're happy with that behavior — which is in line with objects that are built into Python, so we'd need a good reason to feel otherwise about it — then we're done. (This is one reason why implementing our methods efficiently is so important; it has a compounding benefit, since one method can often form the basis of others, as well, so that one fast operation becomes many fast operations.)

Still, not all objects are sized, but we might nonetheless want to control their truthiness. Or, we might be able to implement a way to determine truthiness that's cheaper than we're able to calculate a length. What do we do then?

Directly overriding truthiness

Adding a __bool__(self) method to a class directly overrides how its truthiness is determined, independent of whether it has a length. This means that determining the truthiness of an object is really a process that has as many as three steps.

• If the object has a __bool__ method, its result is used to determine the object's truthiness.
• Otherwise, if the object has a __len__ method, its result is used instead — with zero being falsy and anything non-zero being truthy.
• Otherwise, the object is always considered to be truthy.

This explains why objects of our previous Person class were always truthy: In the absence of __bool__ or __len__ methods in a class, this is Python's default. So, if we want to override that default, we'll need at least one of those methods.

>>> class Person:
...     def __init__(self, name):
...         self._name = name
...     def __bool__(self):
...         return self._name == 'Boo'
...
>>> p1 = Person('Boo')
>>> bool(p1)
    True          # Boo is truthy
>>> p2 = Person('Alex')
>>> bool(p2)
    False         # Everyone else is falsy

This is an aspect of Python's data model that we'll see play out repeatedly. It's often the case that providing one operation (in this case, a length) will automatically supply a default behavior for others (in this case, truthiness), though we can do something other than that default when it's appropriate from the perspectives of correctness or performance. This makes the common situations easier to implement, while still allowing us to implement things more carefully when we need to.

---

Indexing

Some kinds of objects in Python can be indexed, which generally means that we can think of them as containing other objects, but that they give us a way to uniquely identify each of those objects so that we can ask for them individually and know definitively which one we'll get back.

The simplest example of indexing is asking a list for one of its elements given an index. Since lists are designed around an indexing scheme where the first element has the index 0, the second element has the index 1, and so on, then when we ask for the element at a particular index, it's clear which one we're asking for. Strings and ranges have that same design characteristic, so they can be indexed similarly.

>>> values = [1, 3, 5, 7, 9]
>>> values[4]
    9   # ^^^ 4 is the index, in this case, so we want the fifth element.
>>> range(1, 100, 4)[3]
    13            # ^^^ Here, we want the fourth value in the range.
>>> 'Boo is happy'[0]
    'B'         # ^^^ We're looking for a string containing the first character of 'Boo is happy'.

Dictionaries can also be indexed, albeit in a somewhat different way. A dictionary contains unique keys, with a value associated with each of them. So, when you index a dictionary, you're asking a different question: What is the value associated with this key? Still, the syntax is the same, and the underlying idea is, too: Give me the value that's uniquely identified by this index (where, for a dictionary, those indices are really its keys).

>>> d = {'A': 27, 'B': 17, 'C': 0}
>>> d['B']
    17

For some kinds of objects that allow indexing — though not all kinds — we can also assign into those indexes. Again, the syntax is the same for all such indexed objects, and the underlying idea is also the same, though the implementation details differ from one type of object to another.

>>> values[3] = 13
>>> values
    [1, 3, 5, 13, 9]             # One object in the list has been replaced.
>>> d['B'] = 1
>>> d
    {'A': 27, 'B': 1, 'C': 0}    # The value associated with a key has been replaced.
>>> range(1, 100, 4)[3] = 10
    Traceback (most recent call last):
      ...
    TypeError: 'range' object does not support item assignment
                                 # Ranges are immutable, so we can't assign into them.

Those objects that allow assignment into indexes usually also allow deletion of an index, using the del statement.

>>> del values[3]
>>> values
    [1, 3, 5, 9]
>>> del d['A']
>>> d
    {'B': 1, 'C': 0}

That many kinds of objects support the same syntax with potentially different implementation details suggests again that dunder methods are being called behind the scenes here.

Dunder methods for implementing indexing

When we want objects to support indexing, we add at least one dunder method to their class.

• __getitem__(self, index), which returns the value associated with the specified index.

Note that the word "index" does not necessarily mean a non-negative integer, or even an integer at all. It's up to the __getitem__ method to decide what constitutes a valid index and what an index means. (This is what makes it possible to index lists with integers, while being able to index dictionaries with arbitrary hashable keys. Their __getitem__ methods are written differently.)

If we want to support assigning into an index and deletion of an index, there are additional dunder methods we can add alongside __getitem__.

• __setitem__(self, index, value), which assigns the specified value into the specified index.
• __delitem__(self, index), which deletes the value at the specified index.

Indexing is one feature that Python's built-in range provides that our MyRange class doesn't. Rectifying that would be a matter of adding a __getitem__ method to our MyRange class. (Since ranges are immutable, we wouldn't want to add __setitem__ or __delitem__.) Like our __len__ method, __getitem__ can calculate its answer in O(1) time using O(1) memory, so it would be best to do so.

class MyRange:
    ...

    def __getitem__(self, index):
        if type(index) is not int:
            raise TypeError(f'MyRange index must be int, but was {type(index).__name__}')
        elif index < 0 or index >= len(self):
            raise IndexError('MyRange index was out of range')

        return self._start + index * self._step

Since __getitem__ accepts a parameter other than self, but needs to perform calculations based on that parameter's value, some validation was necessary, so that non-integer indices and out-of-range indices would raise exceptions with descriptive error messages instead of returning invalid answers.

How the presence of indexing impacts other operations

When a class has both a __len__ method and a __getitem__ method that accepts non-negative indices, an interesting thing happens: Even without an __iter__ method, its objects become iterable automatically. This is because __len__ and __getitem__ combine together into something called the sequence protocol, which means that objects supporting that combination of methods are what we call sequences.

If we know that an object is a sequence, we know that it can be iterated without an __iter__ method, via calls to __getitem__ and __len__. To understand why, let's briefly experiment with a class that includes these methods.

>>> class ThreeSequence:
...     def __len__(self):
...         return 3
...     def __getitem__(self, index):
...         if 0 <= index < len(self):
...             return index * 3
...         else:
...             raise IndexError
...
>>> s = ThreeSequence()
>>> s[0]
    0        # If s can be indexed with integers, isn't 0 the first index?
>>> s[1]
    3        # In that case, isn't 1 the second index?
>>> s[2]
    6        # And isn't 2 the third?
>>> len(s)
    3        # Doesn't this tell us that s[3] would fail if we tried it?
>>> index = 0
>>> while index < len(s):
...     print(s[index])
...     index += 1
...          # Therefore, isn't this a reliable pattern for iterating such a sequence?
    0
    3
    6

So, as it turns out, when we iterate an object, there's a bit more to the story than we've seen.

• If the object has an __iter__ method, it's called, and its result is the iterator that will be used to manage the iteration.
• Otherwise, if the object has __len__ and __getitem__ methods, an iterator that runs something akin to the while loop above is executed instead, except that the values are returned to us individually instead of printed in the Python shell. (One way to implement that ourselves would be with a generator function, though Python handles the details internally for us.)
• Otherwise, the object is considered not to be iterable.

In fact, iteration works in the presence of a __getitem__ method that accepts non-negative indexes, even in the absence of a __len__ method, in which case successively larger indexes are passed to __getitem__ until it raises an IndexError, at which point the iteration is considered to have ended.

However, the __len__ method is useful in concert with __getitem__ for another reason: It also provides the automatic ability to iterate an object in reverse, since something akin to the following while loop can be used instead.

>>> index = len(s)
>>> while index > 0:
...     index -= 1
...     print(s[index])
...          # This is a reliable pattern for iterating a sequence in reverse, if we know its length.
...          # Without knowing the length, Python couldn't efficiently know where to start.
    6
    3
    0

Additionally, objects implementing indexing (with or without a __len__ method) have another similar automatically implemented behavior.

>>> [i in s for i in range(8)]
    [True, False, False, True, False, False, True, False]
                   # The 'in' operator can be used to see if they contain a value,
                   # though this will be done using iteration, which will take linear time
                   # for each use of the 'in' operator.

When we write a class that implements a sequence, we'll quite often want to provide our own implementations of these three features — iteration, reverse iteration, and "contains" — especially if we can do so more performantly than the default. If so, we could add these three dunder methods to a class.

• The __iter__(self) method we saw before would provide custom iteration, by returning an iterator. (Note that if __iter__(self) is written as a generator function, then its result will be an iterator automatically.)
• The __reversed__(self) method would provide reverse iteration. It returns a reverse iterator (i.e., an iterator that produces the values in reverse order).
• The __contains__(self, value) method would determine whether a value is part of the sequence, returning True if so or False otherwise.

MyRange would benefit from an implementation of __contains__, for example, since its result could then be determined in constant time using some straightforward arithmetic, rather than iterating every value in a potentially large range. There's no reason it should cost more to evaluate 100000 in MyRange(1000000) than it does to evaluate 0 in MyRange(1), but only a custom __contains__ method will make that possible. On the other hand, the automatic implementations of forward and reverse iteration arising from MyRange's indexing feature are probably fine.

So, it's worth knowing what features are provided automatically (and how they're provided automatically), because when these automatic implementations are performant enough for our needs, it means fewer features that we need to build, test, and maintain over time. Those positive decisions compound as programs and teams grow.

---

Slicing

Indexing allows us to obtain a single object within another, such as one element of a list or the value associated with a key in a dictionary. A variant of indexing that we've not yet considered is what Python calls slicing, which allows us to take a sequence of objects and obtain a subsequence, containing some of the objects while skipping others. The slice will usually be the same type — so, for example, a slice of a list will be a list, a slice of a string will be a string, and so on.

>>> values = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
>>> values[2:6]
    [5, 7, 9, 11]
>>> values[2:8:2]
    [5, 9, 13]
>>> values[:3]
    [1, 3, 5]
>>> values[7:]
    [15, 17, 19]
>>> 'Boo is happy today'[:3]
    'Boo'
>>> range(0, 20, 2)[3:7]
    range(6, 14, 2)
>>> 'Boo'[::]
    'Boo'

Syntactically, slicing looks a lot like indexing. If we start with an expression whose value can be sliced, we can follow that expression with brackets, in which we can write either two or three values separated by colons. Those three values, analogous to the values that describe a range, are named start, stop, and step. In the slice notation, all three values are optional.

This raises the question of what mechanism is used to implement slicing. We've seen previously that indexing is implemented via the __getitem__ dunder method, and we can see that slicing uses a similar bracket-surrounded notation, so is it safe for us to assume that __getitem__ does slicing, too? If so, how do we tell the difference between indexing and slicing? One way to find out is to experiment a bit.

>>> class Thing:
...     def __getitem__(self, index):
...         print(f'type(index) = {type(index)}')
...         print(f'index = {index}')
...         return None
...
>>> t = Thing()
>>> t[4]
    type(index) = <class 'int'>
    index = 4
>>> t[1:17:6]
    type(index) = <class 'slice'>
    index = slice(1, 17, 6)
>>> t[1:17]
    type(index) = <class 'slice'>
    index = slice(1, 17, None)
>>> t[:17]
    type(index) = <class 'slice'>
    index = slice(None, 17, None)
>>> t[::]
    type(index) = <class 'slice'>
    index = slice(None, None, None)

From this experimentation, we can deduce a few things:

• When we perform a slicing operation, the __getitem__ method is called, just like when we perform an indexing operation.
• When __getitem__ is called during a slicing operation, its parameter is a slice object.
• A slice object contains three values, which default to None when not explicitly specified.

So, if we want to implement slicing in a class, we'll need to add some functionality to our __getitem__ method to detect that its parameter is a slice and, if so, handle it specially. How do we interact with a slice object?

>>> s = slice(1, 17, 6)
>>> s.start, s.stop, s.step
    (1, 17, 6)        # We can access its start, stop, and step attributes.
>>> s.step = 100
    Traceback (most recent call last):
      ...
    AttributeError: readonly attribute
                      # Like ranges, slices are immutable.
>>> start, stop, step = s.indices(10)
>>> start, stop, step
    (1, 10, 6)        # We can ask it what the applicable start, stop, and step
                      # values would be for a given length.  In this case, we've asked this
                      # for a length of 10, which is why the applicable stop is less than
                      # the original one.
>>> defaulted = slice(None, None, None)
>>> [type(x) for x in (defaulted.start, defaulted.stop, defaulted.step)]
    [<class 'NoneType'>, <class 'NoneType'>, <class 'NoneType'>]
                      # When a slice is constructed with Nones, they aren't defaulted
                      # to anything; they remain Nones.
>>> dstart, dstop, dstep = defaulted.indices(10)
>>> dstart, dstop, dstep
    (0, 10, 1)        # Even if the start, stop, and step are all None, the
                      # indices method returns integer results.
>>> [index for index in range(*defaulted.indices(10))]
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
                      # If indices returns a tuple of three values, we can unpack it into
                      # three arguments (the start, stop, and step), pass them to range (which
                      # also understands the concept of a start, stop, and step), and we now have
                      # a range of the indices that make up our slice.

Now that we understand the building blocks available to us, we have an idea of how we might add slicing to our MyRange class, by reorganizing its __getitem__ method to allow the given index to either be an integer or a slice, then using the slice's indices method to help us figure out the appropriate result when given a slice.

class MyRange:
    ...

    def __getitem__(self, index):
        if type(index) is int:
            if 0 <= index < len(self):
                return self._start + index * self._step
            else:
                raise IndexError('MyRange index was out of range')
        elif type(index) is slice:
            start, stop, step = index.indices(len(self))

            start_value = self._start + start * self._step
            stop_value = min(self._start + stop * self._step, self._stop)
            step_value = step * self._step

            return MyRange(start_value, stop_value, step_value)
        else:
            raise TypeError(f'MyRange index must be int or slice, but was {type(index).__name__}')

It's also possible to assign to a slice of an object, as well as delete a slice. Implementing support for those operations requires similar modifications to __setitem__ and __delitem__, whose index parameter will be a slice object in these situations.

---

Hashing

Python draws a distinction between the objects that are hashable and those that aren't. Conceptually, hashable objects have two qualities that others don't.

• Hashable objects can boil their meaning down to a single integer value called a hash, which allows us to store them in a hash table, a data structure that arranges objects on the basis of where they're thought to belong, so we can find them again cheaply by knowing specifically where to look for them. An object's hash is used to determine where it belongs.
• Hashable objects ought to be immutable, so that if we hash them when deciding where to store them in such a data structure, hashing them again later will give us the same hash again, so that we can find them in the same place we stored them. (If hashes are determined based on an object's attributes, mutable attributes could cause the same object to hash differently afterward.)

If we want to hash an object, we can call the built-in Python function hash and pass it the object as an argument. The algorithm used to hash an object is not particularly important to us, but you'll notice how differently objects can hash even when their values are fairly similar to each other; this turns out not to be an accident, for reasons you'll learn more about in ICS 46.

>>> hash(3)
    3
>>> hash('Boo')
    -6365711242479792522
>>> hash('Boo!')
    -6359222305862117936
>>> hash((1, 2))
    -3550055125485641917
>>> hash((1, 2, 3))
    529344067295497451

If there are objects that are unhashable, we wouldn't expect to be able to pass them to the hash function. Mutable objects generally won't be hashable, so we wouldn't expect to be able to hash a list. Let's try it.

>>> hash([1, 2, 3])
    Traceback (most recent call last):
      ...
    TypeError: unhashable type: 'list'

How does the hash function know whether an object is hashable? As you likely expect, there is a dunder method called __hash__ that calculates an object's hash. Hashable objects are the ones that have a __hash__ method; unhashable objects are the ones that don't. The job of the __hash__ method is to combine the information in the object together into a single integer, taking all of that information into account, so that objects that are different in some way will be likely to hash differently. A simple but effective way to do that is to create a tuple containing all of the object's attributes, then pass those to the built-in hash function. This leads to a simple implementation of __hash__ for our MyRange class — whose objects are immutable, so we might reasonably expect to be able to hash them, as well.

class MyRange:
    ...

    def __hash__(self):
        return hash((self._start, self._stop, self._step))

Remember, though, that the reason we want to be able to hash objects is so we can store them in a hash table, which is to say that we want to be able to arrange them in a way that we can use their hashes to find them again easily. But hashes are not guaranteed to be unique; it's possible for two different objects to hash identically. So, just because we find an object that has a particular hash, we can't know whether it's the object we're looking for; we just know that it's an object that ended up in the same place. Because of that, when objects are hashable, there's one other important thing we'll need to be able to do with them: compare them to other objects to see if they're equivalent. To do that, we'll need to dig a little further into the Python data model.

---

Comparison operators

Python gives us the ability to compare objects in various ways, and its data model allows us to control how most of those comparisons are implemented when they involve objects of our classes. Before we can implement these kinds of comparisons, we ought to be sure we understand the kinds of comparisons that can be done, because there are some subtleties that we need to take into account. What should it mean for two objects to be "equal"? What should it mean for one object to be "less than" another?

Identity and equivalence

First, let's be sure we understand Python's idea of equality. When we compare two objects and ask "Are these the same?", what are we actually asking? Is there always one question we're trying to answer, or are there different ones?

Like many programming languages, Python's design distinguishes between two ideas of equality: identity and equivalence. Because we might be interested in knowing either of these things, a separate syntax exists for each of them.

>>> a = [1, 2, 3]
>>> b = [1, 2, 3]
>>> id(a), id(b)
    (1994268245696, 1994268381632)
                       # The id function returns an object's identity, which is
                       # unique to each object, even objects that have identical meaning.
>>> a is b
    False              # The is operator returns True only when two objects have
                       # the same identity, regardless of whether they have identical meaning.
>>> a == b
    True               # The == operator returns True when two objects have
                       # an equivalent meaning, even if they have different identities.

Neither of these operators is definitively better than the other; they're simply meant to solve different problems, so the key is knowing what problem you have, which will allow you to make the right choice for your needs.

• The is operator (and its opposite, is not) is likely to be the faster-running of the two, since it's likely implemented behind the scenes as an inexpensive comparison of two memory addresses. So, if identity is truly the only thing you want to check, using is would be the better choice. (You might have seen me compare types using the is operator for exactly this reason.)
• The == operator (and its opposite, !=) is capable of determining whether two objects are equivalent, even if their identities are different (or maybe even if their types are different). Because it asks a more complex question, it can take longer to run, but that's neither here nor there if the problem calls for it; fast is better than slow, but slow is better than incorrect. (In practice, I find that I use == more often than is, because it's more often that I'm interested in equivalence than identity.)

Python provides no way to override the built-in meaning of the is operator. The only circumstance in which a is b is True is when both a and b have the same identity. That's all there is to it, and all there can be: Either they're the same object or they aren't.

Equivalence, on the other hand, is something that would naturally need to be implemented differently in different classes; after all, what it means for two integers to be equivalent is very different from what it means for two lists of strings to be equivalent. Consequently, the Python data model provides a mechanism for us to specify what it means for two objects of our classes to be equivalent. Before we get to that, though, let's finish our conversation about comparisons in Python.

Relational comparisons

A common feature of programming languages allows us to compare two objects relationally, which means that we want to compare them on the basis of their natural ordering, so we can determine which (if any) is smaller than the other. Integers, for example, have a natural ordering that most of us learned when we were quite young: 2 is greater than 1, 5 is greater than 1, 6 is less than 17, and so on. So, it's unsurprising to most novice Python programmers to discover that there are operators that perform those kinds of comparisons.

>>> 2 > 1
    True
>>> 17 < 6
    False

For some types, their natural ordering is obvious enough that it hardly needs to be explained to us. For other types, there could potentially be more than one reasonable way to order them. For example, what rule causes the following behavior?

>>> [1, 2] < [1, 3]
    True
>>> [2, 3] < [1, 2]
    False
>>> [1, 2] < [1, 2, 3]
    True

The answer is that this is a well-known technique called lexicographical ordering, which is a fancy term for a simple idea:

• Compare the first element of each list. If one is less than the other, that determines how the lists compare.
• If the first elements were equivalent, compare the second element of each list. If one is less than the other, that determines how the lists compare.
• Continue until you either find an element that distinguishes one list from the other, or until one list runs out of elements. In that case, if both lists have run out of elements, the lists are equivalent; otherwise, the shorter list is less than the longer one.

(Note that this is the same algorithm we use to sort English words into alphabetical order, comparing one letter at a time until we find a difference, or until one word turns out to be a prefix of the other.)

For still other types — most types in a large program fit into this category — there's no natural way to order them at all; they simply don't have a notion of "less than" or "greater than" associated with them, so a sensible design would render such a comparison impossible altogether. (A good software design is as much about disallowing unreasonable things as it is about allowing reasonable ones.)

Since different types of objects will need to handle relational comparisons differently, Python's data model provides hooks for us to control how they behave, too. Now that we understand the problem we're solving in enough detail, all that remains are the implementation details. Bring on the dunder methods!

Implementing equality comparisons

If we want to provide a custom implementation of equivalence for the objects of a class, we can do so by adding an __eq__ method to its class.

• __eq__(self, other), which returns True if self is equivalent to other, False if self is inequivalent to other, or NotImplemented if the equality operation is not supported for the types of the arguments.

(NotImplemented — like True, False, and None — is a constant value in Python, whose type is NotImplementedType.)

Notably, if we don't write an __eq__ method, they still provide an implementation of equality automatically, but it's based only on identity (i.e., two objects are equal if and only if they have the same identity). So, if we want anything other than that, we'll need to implement an __eq__ method.

In our MyRange class, we might implement it by checking that the other object is also a MyRange, and that their _start, _stop, and _step attributes are equivalent.

class MyRange:
    ...

    def __eq__(self, other):
        if type(other) is MyRange:
            return self._start == other._start \
                   and self._stop == other._stop \
                   and self._step == other._step
        else:
            return NotImplemented

Let's try our implementation out.

>>> r1 = MyRange(0, 10)
>>> r2 = MyRange(0, 10)
>>> r3 = MyRange(0, 10, 2)
                    # r1 and r2 are equivalent but have different identities.
                    # r3 is not equivalent to either r1 or r2.
>>> r1 is r2
    False           # As expected, r1 and r2 have different identities.
>>> r1 == r2
    True            # As expected, r1 and r2 are equivalent, by our new definition.
>>> r1 == r3
    False           # r1 and r3 are not.
>>> r1 != r2, r1 != r3
    (False, True)   # Interestingly, the != operator seems to be working, as well.

The last of these expressions points us to something interesting: If we implement equality, we get an implementation of inequality automatically. Thinking about it conceptually, this seems sensible enough; if we've specified the conditions under which two objects are equivalent, then two objects are inequivalent under the opposite conditions. So, Python could reasonably implement r1 != r2 as not r1.__eq__(r2).

Still, as usual, Python provides a way for us to specify inequality, in case we could do it ourselves more performantly.

• __ne__(self, other), which returns True if self is inequivalent to other, False if self is equivalent to other, or NotImplemented if the inequality operation is not supported for the types of the arguments.

In practice, it will rarely if ever be the case that we'd want it to return a different result from not r1.__eq__(r2), but we might sometimes be able to find a more efficient way to calculate that result than checking for equivalence and then negating it. Similarly, we'd generally want __ne__ to return NotImplemented in the same circumstances in which __eq__ does (i.e., only objects that support equality also support inequality).

Strangely, adding an __ne__ method to a class without an __eq__ method does not automatically provide a meaning of equality. In other words, even though we know that r1.__eq__(r2) is the same as not r1.__ne__(r2), Python does not perform this conversion automatically. So, generally, we can think of __eq__ as necessary when customizing equivalence and __ne__ only as a potential optimization.

Clarifying the relationship between equality and hashing

There's one other thing worth noting about equality: For reasons we discussed in our conversation about hashing, classes that provide a __hash__ method must also provide an __eq__ method, because there's a vitally important correspondence that must be maintained between the meanings of equivalence and hashing.

• If two objects are equivalent, they must have the same hash.

That implication only applies in one direction: Two objects with the same hash will not necessarily be equivalent, even though we'd prefer that they are. The reason we can't make this happen is a practical one: Part of what we do when we hash an object is simplify it to a value that's lower-fidelity; some information will almost surely be lost, which means inequivalent objects will unavoidably have the same hash sometimes. While we'd like to make that as unlikely as possible, we can't avoid it in general.

Still, because of that implication, it's quite often the case that taking control over hashing or equality implies that we should take control of the other, as well, because their meanings are necessarily intertwined. Fortunately, there are some additional mechanics that help us to avoid writing classes that accidentally fail to meet these constraints, particularly because objects support both hashability and identity-based equality by default.

>>> class Thing:
...     pass
...
>>> hash(Thing())
    107648736801    # Objects are hashable by default
>>> Thing() == Thing()
    False           # Objects support equality (albeit using only their
                    # identities) by default.
>>> t1 = Thing()
>>> t2 = Thing()
>>> t1 == t2
                    # Since t1 and t2 refer to separate objects (with separate
                    # identities), they are not considered equivalent.
    False
>>> hash(t1) == hash(t2)
    False           # Inequivalent objects can have different hashes, which
                    # makes this answer allowable -- though True would be
                    # allowable, too.
>>> t1 == t1
    True
>>> hash(t1) == hash(t1)
    True            # Equivalent objects must have the same hash, which
                    # is correct by default.

The provided defaults meet the basic requirement, but this raises the question of what happens if we implement our own custom behavior for one of these operations without implementing the other. To determine the answer to that question, we'll need to think about both operations separately.

What happens if we implement hashing without equality?

>>> class HashableThing:
...     def __hash__(self):
...         return 999
...
>>> hash(HashableThing())
    999
>>> h1 = HashableThing()
>>> h2 = HashableThing()
>>> h1 == h2, hash(h1) == hash(h2)
    (False, True)   # Inequivalent objects are allowed to have the same hash.
>>> h1 == h1, hash(h1) == hash(h1)
    (True, True)    # Equivalent objects must have the same hash.

Essentially, nothing can go wrong here, as long as our __hash__ method is written in a way that uses only what's stored within the object, since the default behavior of equality is to use identity (i.e., no two different objects are equal). What we're trying to avoid is equivalent objects having different hashes; that can't happen when we implement __hash__, as long as we implement it properly.

On the other hand, what happens if we implement equality without hashing?

>>> class UnhashableThing:
...     def __init__(self, value):
...         self.value = value
...     def __eq__(self, other):
...         return isinstance(other, UnhashableThing) and self.value == other.value
...
>>> UnhashableThing(11) == UnhashableThing(7)
    False    # Objects storing different values are inequivalent.
             # We'd prefer their hashes to be different, but without
             # having implemented custom hashing behavior, how can we
             # affect the outcome?
>>> UnhashableThing(13) == UnhashableThing(13)
    True     # Objects storing the same values are equivalent.
             # Their hashes must be equivalent, but without having
             # implemented custom hashing behavior, how can we
             # force them to be?
>>> hash(UnhashableThing(13)) == hash(UnhashableThing(13))
    Traceback (most recent call last):
      ...
    TypeError: unhashable type: 'UnhashableThing'
             # Oh!  UnhashableThings aren't hashable at all!
>>> UnhashableThing.__hash__ is None
    True     # It's because UnhashableThing has no __hash__ method.

As a safety mechanism, when we write an __eq__ method in a class without a __hash__ method being written in that same class, Python automatically sets the value of __hash__ in the class dictionary to None, specifically to avoid the problem we otherwise would have created: Specifying a way for two objects to be equivalent without having ensured that their hashes would be the same.

Of course, this mechanism isn't fool-proof, since nothing prevents us from writing __eq__ and __hash__ methods that don't fit together properly, but there is at least a sensible default at work here, which prevents us from accidentally introducing a problem we hadn't considered thoroughly.

Implementing relational comparisons

Relational comparisons can also be customized in Python, and dunder methods will again be our tool of choice when performing that customization. But it's wise for us to begin by understanding the default; what happens if we don't customize relational comparisons in a class? If we don't specify the details, under what circumstances are objects "less than" other objects?

>>> class Thing:
...     pass
...
>>> t1 = Thing()
>>> t2 = Thing()
>>> t1 < t2
    Traceback (most recent call last):
      ...
    TypeError: '<' not supported between instances of 'Thing' and 'Thing'

Unlike equality comparisons, for which there is a default behavior if you don't specify one, relational comparisons have no default. If a class doesn't describe how its objects are to be compared relationally, they can't be. So, if we want relational comparisons for objects of our classes, we'll need to implement them ourselves. There are four kinds of relational comparisons (<, <=, >, and >=), so we can do this using (up to) four dunder methods that provide their implementations.

• __lt__(self, other), which returns True if self is less than other or False otherwise.
• __gt__(self, other), which returns True if self is greater than other or False otherwise.
• __le__(self, other), which returns True if self is less than or equal to other or False otherwise.
• __ge__(self, other), which returns True if self is greater than or equal to other or False otherwise.

As with equality, you don't need to implement all four methods to be able to perform all four comparisons, since there are known relationships between their results.

• Whenever t1.__lt__(t2) is True, we expect t2.__gt__(t1) to be True.
• Whenever t1.__le__(t2) is True, we expect t2.__ge__(t1) to be True.

Consequently, an implementation of either __lt__ or __gt__ can be used for both the < and > operators, and an implementation of either __le__ or __ge__ can be used for both the <= and >= operators.

>>> class Thing:
...     def __init__(self, value):
...         self.value = value
...     def __lt__(self, other):
...         print(f'__lt__: self.value = {self.value}, other.value = {other.value}')
...         return self.value < other.value
...
>>> t1 = Thing(3)
>>> t2 = Thing(9)
>>> t1 < t2
    __lt__: self.value = 3, other.value = 9
    True              # Here, __lt__ was called on t1, with t2 being other.
>>> t1 > t2
    __lt__: self.value = 9, other.value = 3
    False             # Here, __lt__ was called on t2, with t1 being other.

Even though the presence of both __eq__ and __lt__ could theoretically be enough to implement a <= operator, Python doesn't implement that conversion for us. So, if we want relational comparisons, we probably want at least these three dunder methods: __eq__, __lt__, and __le__, with the other three (__ne__, __gt__, and __ge__) providing a mechanism for optimization if we need it.

Mixed-type comparisons

Comparisons can be done between objects of different classes, which may then have different implementations of these same dunder methods. If we evaluate x == y, but x and y have different types, then whose __eq__ method is called? One way to find out is to experiment.

>>> class A:
...     def __eq__(self, other):
...         print('A.__eq__')
...         return True
...
>>> class B:
...     def __eq__(self, other):
...         print('B.__eq__')
...         return True
...
>>> a1 = A()
>>> b1 = B()
>>> a1 == b1
    A.__eq__
    True
>>> b1 == a1
    B.__eq__
    True

From our experimentation, it appears that the rule is simple: When we write x == y, x.__eq__(y) is called. But what happens if x's class has no __eq__ method, but y's does?

>>> class C:
...     pass
...
>>> c1 = C()
>>> c1 == b1
    B.__eq__
    True

In that case, Python is instead calling b1.__eq__(c1) instead, so that we can get a better answer than we might get if we relied instead on C's default equality (which is based only on identity).

It turns out that there's a little more to the underlying rule than this — we can flesh this out a bit further when we talk about inheritance and subclassing — but this is a good enough understanding for us to proceed with for now: The __eq__ method of the left-hand object is used, unless only the right-hand object has an __eq__ method.

---

Arithmetic operators

Another set of operators whose meaning we might like to redefine for our classes is the set of arithmetic operators. Consider which operators we can apply to integers in Python; below are many (but not all) of them.

>>> i = 40
>>> j = 16
>>> +i
    40             # The unary plus operator returns its operand unchanged.
>>> -i
    -40            # The unary minus operator returns the negation of its operand.
>>> (i + j, i - j, i * j)
    (56, 24, 640)  # We can add, subtract, and multiply two integers.
>>> (i / j, i // j, i % j)
    (2.5, 2, 8)    # There are two kinds of division, along with modulo.
>>> i ** 2
    1600           # We can exponentiate integers.

Once again, dunder methods form the basis of how these operators are actually implemented, so if we want to define the meaning of these operators when used on objects of our own classes, we can do so by implementing the appropriate dunder methods. They follow a few recurring patterns, so we'll stick with a couple of examples; you can read about the rest of them in the Python Data Model documentation when you need them.

The unary operators + and - have a single operand, so that suggests that they would best be implemented by dunder methods that accept a self parameter and no others.

• __pos__(self) implements the unary plus operator.
• __neg__(self) implements the unary minus operator.

>>> class Thing:
...     def __init__(self, value):
...         self.value = value
...     def __repr__(self):
...         return f'Thing({self.value})'
...     def __neg__(self):
...         return Thing(-self.value)
...
>>> t1 = Thing(17)
>>> -t1
    Thing(-17)     # Our result is negated.
>>> t1
    Thing(17)      # t1 is unchanged, as it should be.

That last expression points out something important: We don't expect the arithmetic operators to modify their operands, so we need to be sure to return new values instead of modifying the existing ones. This aligns the behavior of our classes with the types that are built into Python.

The various binary operators have two operands, so they might instead be implemented as dunder methods taking two parameters: a self and one other. We saw that pattern already when we implemented the comparison operators, and it recurs here.

• __add__(self, other) returns the sum of self and other.
• __sub__(self, other) returns the difference when subtracting other from self.
• __mul__(self, other) returns the product of self and other.
• __truediv__(self, other) returns the quotient of self and other, without taking the floor of the result.
• __floordiv__(self, other) returns the floor of the quotient of self and other.
• __pow__(self, other) returns the result of raising self to the power other.

Let's try implementing a simple __add__ method as a first example.

>>> class Thing:
...     def __init__(self, value):
...         self.value = value
...     def __repr__(self):
...         return f'Thing({self.value})'
...     def __add__(self, other):
...         return Thing(self.value + other.value)
...
>>> t1 = Thing(3)
>>> t2 = Thing(9)
>>> t1 + t2
    Thing(12)

In a complete implementation, any of these methods would best return NotImplemented when the operation is not supported on the types of the arguments. For example, if you want it to be possible to add objects of your class Money to other objects of the same class, but not others, then you would return NotImplemented whenever the other parameter has a type other than Money. This rule turns out not only to be hygenic, but it also forms the basis of additional automation; if Python knows that an operator isn't implemented, it might be able to try an equivalent alternative instead.

Reflected arithmetic operators

When we redefine arithmetic operators, the usual rule is that the operation x ? y turns into a call to the equivalent dunder method, with x being the first argument (i.e., passed into self) and y being the second (i.e., passed into other). So, for example, when evaluating x + y, Python attempts to call x.__add__(y), the result of which becomes the result of the addition.

However, when x.__add__(y) is not supported, Python makes one more attempt to add x and y, by instead calling into a reflected version of the operator. In the case of addition, that reflected operation is implemented by the dunder method __radd__, so if x.__add__(y) is unsupported, Python attempts to call y.__radd__(x) instead. The mechanism it uses to determine whether x.__add__(y) is supported is simple: If the __add__ method doesn't exist, or if it returns NotImplemented, it's unsupported.

There's a reason why the reflected arithmetic operators need to be implemented separately: Not all of these operators are commutative. We would expect x + y and y + x to return the same result — in many cases, but certainly not all! — but we would not expect the same from x - y and y - x. So, if Python is going to reverse the order of the arguments, we'll also need to know that we need to perform the reverse of the usual operation, so a different dunder method is called.

• __radd__(self, other) returns the sum of other and self.
• __rsub__(self, other) returns the difference when subtracting self from other.
• __rmul__(self, other) returns the product of other and self.
• __rtruediv__(self, other) returns the quotient of other and self, without taking the floor of the result.
• __rfloordiv__(self, other) returns the floor of the quotient of other and self.
• __rpow__(self, other) returns the result of raising other to the power of self.

So, why is it so important for us to have this ability? Let's suppose that we have our own class called Thing, and that we want to be able to add Thing objects to integers. We might start by writing this.

>>> class Thing:
...     def __init__(self, value):
...         self.value = value
...     def __repr__(self):
...         return f'Thing({self.value})'
...     def __add__(self, other):
...         if type(other) is Thing:
...             return Thing(self.value + other.value)
...         elif type(other) is int:
...             return Thing(self.value + other)
...         else:
...             return NotImplemented
...
>>> t = Thing(17)
>>> t + 1
    Thing(18)       # So far, so good!
>>> 1 + t
    Traceback (most recent call last):
      ...
    TypeError: unsupported operand type(s) for +: 'int' and 'Thing'
                    # This is why we need __radd__!

At this point, there are two ways we might think about solving the problem.

• Modify the __add__ method in the int class, so that it is able to add integers to Things.
• Write an __radd__ method in the Thing class, which performs reflected addition of an integer to a Thing.

And, of course, the first option isn't actually a choice we have, because we can't (and shouldn't) modify Python's built-in int class. So, ultimately, our only option is reflected addition.

>>> class Thing:
...     def __init__(self, value):
...         self.value = value
...     def __repr__(self):
...         return f'Thing({self.value})'
...     def _add_values(self, other):
...         if type(other) is Thing:
...             return self.value + other.value
...         elif type(other) is int:
...             return self.value + other
...         else:
...             return None
...     def __add__(self, other):
...         new_value = self._add_values(other)
...         return Thing(new_value) if new_value is not None else NotImplemented
...     def __radd__(self, other):
...         new_value = self._add_values(other)
...         return Thing(new_value) if new_value is not None else NotImplemented
...
>>> t = Thing(17)
>>> t + 1
    Thing(18)
>>> 1 + t
    Thing(18)       # Problem solved!

Augmented arithmetic operators

There is one more variation on arithmetic operators that we need to consider, as well. Python provides augmented arithmetic operators, which have the job of modifying an existing object rather than building a new one. For immutable objects, this is a distinction without a difference, but when objects are mutable, there can be a substantial performance benefit in implementing the augmented arithmetic operators differently from the others. Lists provide a good example of this.

>>> values = [1, 2, 3, 4, 5]
>>> values + [6, 7, 8]
    [1, 2, 3, 4, 5, 6, 7, 8]
>>> values
    [1, 2, 3, 4, 5]              # The + operator left values intact.
>>> values += [6, 7, 8]
>>> values
    [1, 2, 3, 4, 5, 6, 7, 8]     # But += changed it.

You've probably been previously acquainted with the conceptual difference between values + [6, 7, 8] and values += [6, 7, 8], but a little asymptotic analysis tells us that there's a significant performance difference here, as well.

• values + additional must leave values intact, meaning that it must build an entirely new list. This means all of the elements of values need to be copied into that new list, followed by all of the ones that we're adding to the end of it. If there are n elements in values and m elements in additional, we'll spend O(n + m) time on this operation (i.e., linear, but proportional to the sum of the lengths of the two lists).
• values += additional appends each value in additional to the end of values directly. This means it doesn't matter how many elements are in values, because none of them will need to be relocated; it only matters how many elements are in additional. If there are n elements in values and m elements in additional, we'll spend O(m) time on this operation. It's still linear, but it's linear with respect to the length of one list, rather than the sum of the lengths of both. This difference can be quite large in practice, as it's not uncommon to add a small number of elements to a large list.

So, there can certainly be a performance benefit in implementing the augmented arithmetic operators separately from the others.

For immutable objects, we won't want to implement them, because the default behavior — make a new object with the new value — is exactly what we'd want. For example, our most recent Thing class supports += already, since Python will automatically turn t += 3 into the equivalent t = t + 3 instead.

>>> t = Thing(17)
>>> id(t)
    2008047601600
>>> t += 3
>>> t
    Thing(20)
>>> id(t)
    2008047602800    # The id has changed here, because t + 3 built a new Thing object.

If Thing objects are intended to be mutable — we never decided about that, since we're just noodling — then we might instead want to implement augmented addition, so they'd be modified directly. (This is especially true if constructing Thing objects was more expensive than filling in a single integer attribute; it's for types like lists where this distinction matters the most.) Augmented arithmetic operators, like the others, are implemented using dunder methods.

• __iadd__(self, other), which adds other to self in-place (i.e., modifying self).
• __isub__(self, other), which subtracts other from self in-place.
• __imul__(self, other), which multiplies self by other in-place.
• __itruediv__(self, other), which divides self by other in-place, without taking the floor of the result.
• __ifloordiv__(self, other), which floor-divides self by other in-place.
• __ipow__(self, other), which raises self to the power of other in-place.

These methods return the updated result, which will usually just be self (albeit with modifications), or they'll return NotImplemented when the types of the operands are not supported.

Implementing augmented addition in our Thing class might look like this, then.

class Thing:
    ...

    def __iadd__(self, other):
        new_value = self._add_values(other)

        if new_value is not None:
            self.value = new_value
            return self
        else:
            return NotImplemented

Note, too, that there are no reflected versions of the augmented arithmetic operators, for the simple reason that the object on the left-hand side of the operation is always the one being modified, so we would expect its class to be the one to know how to implement that modification.