# Equality

Figuring out whether two things are the same or not might seem like it should be the easiest job in the world. Unfortunately that's not the case. Equality, identity, and comparisons are surprisingly complicated topics in any programming language. Python is no exception.

Our goal in this class is to introduce some of the subtleties that come up when talking about these topics. The approaches to handling these subtleties, and the syntax we'll use, are specific to Python. While they might present in different ways, these issues appear in any programming language, so let's try not to get too bogged down in Python specifics!

## Equality vs identity (on literals)

Python integers, strings, and boolean values are *literals*: they're immutable values stored directly in memory. If we assign

a = 365
b = 365

Then, in our memory model, we've put the value `365` at `loc 0`, and the value `365` at `loc 1`. Our program dictionary directs `a` to `loc 0` and `b` to `loc 1`.

`a` and `b` are equal, according to the `==` operator:

>>> a == b
True

This operator, on integers, compares their literal values. But there's at least one difference between `a` and `b`: the locations that they point to in memory. Python's `id` function lets us inspect this.

>>> id(a)
140670548369360
>>> id(b)
140670547931312

There's a fundamental operator in Python, `is`, that compares two expressions by the location that each occupies in memory. `a is b` will return `True` only when `a` and `b` have the same `id`.

>>> a == b
True
>>> a is b
False
>>> a is a
True

We often call `==` the *equality* operator, and `is` the *identity* operator. Equality is a function that takes two arguments and returns a boolean. Its implementation depends on what class the inputs belong to. Identity also takes two arguments and returns a boolean, but its implementation is always the same: check that the two locations in memory match.

We sometimes use the terminology *relational equality* for `==` and *reference equality* for `is`.

Checking identity is always very fast. Consider two strings, each 100,000 characters long, that differ only on the last character. Checking relational equality would involve comparing each corresponding pair of characters, and wouldn't return `False` until after checking all 100,000 pairs. Checking identity, on the other hand, involves just one comparison of two integers.

On the other hand, identity is a very precise thing to check. Most of the time we're really interested in equality.

## Subtleties with identity on literals

Let's modify our example above just a bit:

>>> a = 255
>>> b = 255
>>> a == b
True
>>> a is b
True

What? Why is the behavior for 255 different from the behavior for 365?

Unsurprisingly, small integers are used more often in practice than large ones. Python knows this, and so it can optimize certain kinds of computations by automatically loading the integers -5 to 256 into locations in memory. Assigning `a = 255` points `a` to this pre-loaded location, and similarly for `b`, so `a` and `b` are referentially equal.

This process is called *interning*. Python does something similar for strings; the details of which string literals get interned vary, depending on which version of Python you're using and how you run your code. This means you shouldn't write code whose correctness depends on certain things being identical! Interning is a useful optimization, but not something you should assume.

There's another thing that gets interned: `None`. Any two `None`s should always be identical. This is something you *can* assume, that has real effects, as we'll see in a minute!

## Equality on classes

Let's define a new class, with nothing special in it yet.

class Book:
    def __init__(self, author: str, title: str, edition: int):
        self.author  = author
        self.title   = title
        self.edition = edition

It's natural to want to compare books. But how does relational equality work on our custom class?

>>> book1 = Book("Emily Bronte", "Wuthering Heights", 1)
>>> book2 = Book("Emily Bronte", "Wuthering Heights", 1)
>>> book1 is book2
False
>>> book1 == book2
False
>>> book1 == book1
True

We've created two different "copies" of Wuthering Heights and stored them at different locations in memory. It's no surprise that they aren't identical. But we never told Python how to compare books; it doesn't know how to check equality, so it falls back to checking identity.

We need to add a class method to `Book` that computes this equality.

class Book:
    def __init__(self, author: str, title: str, edition: int):
        self.author  = author
        self.title   = title
        self.edition = edition

    def __eq__(self, other):
        return self.author  == other.author \ 
           and self.title   == other.title \
           and self.edition == other.edition

Evaluating `book1 == book2` is exactly the same as evaluating `book1.__eq__(book2)`.

Note: among other things, dataclasses will take care of the `__eq__` method for us, defining it in the obvious way.

@dataclass
class Movie:
    title: str 
    director: str 

>>> Movie("Parasite", "Bong Joon-ho") == Movie("Parasite", "Bong Joon-ho")
True

## Redefining equality

There's another catch. What if I tried to do a comparison `book1 == None`? `None` doesn't have an `author` field, so this will throw an exception. We could check in our `__eq__` method that the objects we're comparing have the same type:

    def __eq__(self, other):
        if isinstance(other, Book):
            return self.author  == other.author \ 
               and self.title   == other.title \
               and self.edition == other.edition
        else:
            return False

But since `None` is always interned, it's often safer and more predictable to test identity: check for `book1 is None` instead of `book1 == None`. `is` will never crash, and will always behave correctly here.

You might find it surprising to change `_eq__` in this way: we're refining our notion of what equality is. But this is the power of relational equality: Python doesn't impose any rules about how we implement it. In some applications, we might want to consider two books to be equal regardless of whether their edition numbers match.

    def __eq__(self, other):
        if isinstance(other, Book):
            return self.author  == other.author \ 
               and self.title   == other.title 
        else:
            return False

>>> Book("Emily Bronte", "Wuthering Heights", 1) == Book("Emily Bronte", "Wuthering Heights", 2)
True

Or maybe we want to go crazy:

import random

class IntWrapper:
    def __init__(self):
        self.val = random.randint(0, 1000)

    def __lt__(self, other):
        return self.val < other.val 

    def __gt__(self, other):
        return self.val > other.val 

    def __eq__(self, other):
        return random.randint(0, 1) == 0 

    def __repr__(self):
        return repr(self.val)

iw = IntWrapper()

>>> iw == iw
False
>>> iw == iw
True
>>> iw == iw
True
>>> iw == iw
False
>>> iw == iw
True

But think about how much this would break. Lots of things depend on a "sensible" implementation of `eq`. Remember `quick_sort`:

def quick_sort(l: list) -> list:
    if len(l) <= 1:
        return l[:]
    pivot = l[0] # many other choices possible
    smaller = [x for x in l if x < pivot]
    larger = [x for x in l if x > pivot]
    same = [x for x in l if x == pivot]
    smaller_sorted = quick_sort(smaller)
    larger_sorted = quick_sort(larger)
    return smaller_sorted + same + larger_sorted

>>> rand_list = [IntWrapper() for i in range(10)]

>>> rand_list
[236, 22, 190, 289, 124, 90, 197, 462, 607, 113]

>>> quick_sort(rand_list)
[22, 190, 124, 197, 113, 90, 113, 90, 113, 190, 124, 197, 190, 289, 124, 90, 462, 607, 113, 289, 607, 607]

So what does "sensible" mean? Think about it!

<details>
<summary><B>Think, then Click!</B></summary>

* Equality should always be *reflexive*: everything is equal to itself. You may even wonder what "itself" could mean here, but we have a notion for that: identity. So to refine this thought: *if `a is b` returns `True`, then `a == b` should return `True`*.

* Equality should be *symmetric*: if `a == b`, then `b == a`.

* Equality sould be *transitive*: if `a == b` and `b == c`, then `a == c`.

You may have heard the term *equivalence relation* to describe a relation that is reflexive, symmetric, and transitive. Indeed, `__eq__` can be read as `equivalent` instead of `equal`!

Furthermore:

* Equality should be *deterministic*. Our use of `random` is probably not a good idea.

* If we define other operators like `__lt__` as we did above, equality should interact in a reasonable way with these.

</details>

## Morals

Most programming languages have this same distinction between identity and equality. Depending on the language, it's rare that you *need* to think about identity. But understanding the concept can help you debug confusing behavior, and with careful use, you can use it to write very efficient code.

Similarly, most languages give us a lot of freedom when it comes to defining equality. (In languages that don't, we often see other complications.) But with this freedom comes the responsibility not to abuse it! Bad equivalences can be a huge source of bugs.