# Python Invariance: list vs. Sequence

## Key Terms

1. **Covariant**: If A is a subtype of B, then Container[A] is a subtype of Container[B].
2. **Contravariant**: If A is a subtype of B, then Container[B] is a subtype of Container[A].
3. **Invariant**: Neither covariant nor contravariant. Container[A] and Container[B] are not related, even if A and B are.

## The Case of list

In Python, `list` is invariant. This means a `list[Dog]` is not considered a subtype of `list[Animal]`, even though `Dog` is a subtype of `Animal`.

### Why list is Invariant

To understand why `list` is invariant, let's consider what could happen if it were covariant:

class Animal:
    def make_sound(self):
        pass

class Dog(Animal):
    def make_sound(self):
        print("Woof!")
    
    def bark(self):
        self.make_sound()

class Cat(Animal):
    def make_sound(self):
        print("Meow!")

def add_cat(animals: list[Animal]):
    animals.append(Cat())

# If list were covariant (which it's not in Python):
dogs: list[Dog] = [Dog(), Dog()]
add_cat(dogs)  # This would be allowed, but shouldn't be!

# Later in the code:
for dog in dogs:
    dog.bark()  # Oops! One of these will fail because it's actually a Cat

If `list` were covariant:
1. We could pass a `list[Dog]` to a function expecting `list[Animal]`.
2. That function could add a `Cat` to the list.
3. Now our `dogs` list contains a `Cat`, which breaks our assumption.
4. This could cause unexpected behavior or errors later in the code.

By making `list` invariant, Python prevents this kind of mistake. It forces you to be explicit about what types of objects can be in your list, making your code safer and less prone to runtime errors.

## The Case of Sequence

Unlike `list`, `Sequence` is covariant in Python. This means you can use a `Sequence[Dog]` where a `Sequence[Animal]` is expected.

### Why Sequence can be Covariant

`Sequence` is a read-only protocol. This means you can't add or remove items from a `Sequence`. This key difference makes it safe for `Sequence` to be covariant:

from typing import Sequence

def process_animals(animals: Sequence[Animal]):
    for animal in animals:
        animal.make_sound()
    # We can't add to the sequence here

dogs: list[Dog] = [Dog(), Dog()]
process_animals(dogs)  # This works fine

Key points:
1. You can pass a `list` to a function expecting a `Sequence`. This is because `list` implements the `Sequence` protocol.
2. The function receiving a `Sequence` can't add to it. `Sequence` is a read-only protocol.
3. You can't write an `add_cat` function for `Sequence`:

def add_cat(animals: Sequence[Animal]):
    animals.append(Cat())  # This would cause an error

This function would fail because `Sequence` doesn't have an `append` method.

## Conclusion

The invariance of `list` and the covariance of `Sequence` in Python serve different purposes:
- `list` being invariant prevents type errors that could occur from modifying the list.
- `Sequence` being covariant allows for more flexible use of read-only sequences, without the risk of modification-related type errors.

Understanding these differences helps in writing more type-safe and flexible Python code.