Post Title

The culprit

At some point I was minding my own business writing some type-annotated Python code when my type checker of trust did me dirty and hit me like a brick: it used words I had no recollection of having anything to do with typing.

error: Return type "list[A]" of "list_method" incompatible with return type "list[A | B]" in supertype "ParentClass"  [override]

Let’s provide some context. Let’s assume we have a simple inheritance from ParentClass to Childclass. Both classes only carry two methods: sequence_method and list_method. As the name suggests, one return a Sequence object, one returns alist object. Here comes the more or less subtle difference between both classes: the parent returns containers, in which every element can either be an instance of class A or class B. The child class narrows down this option space by only ever returning elements which are instances of class A in its containers.

Ok – enough of the prose – here comes some code:

from typing import Sequence
from dataclasses import dataclass

@dataclass
class A:
    field: str

@dataclass
class B:
    field: int

class ParentClass:

    def sequence_method(self, flip: bool) -> Sequence[A | B]:
        if flip:
            return [A("hey"), B(5)]
        return (A("hey"), B(5))

    def list_method(self) -> list[A | B]:
        return [A("hey"), B(5)]

class ChildClass(ParentClass):

    def sequence_method(self, flip: bool) -> Sequence[A]:
        if flip:
            return [A("hey"), A("ho")]
        return (A("hey"), A("ho"))

    def list_method(self) -> list[A]:
        return [A("hey"), A("ho")]

Since I was caught off guard when noticing that one of my pre-commit hooks – admittedly only run pro forma, overconfidently not expecting any issues – complained regarding typing, I wanted to be sure this wasn’t a type checking bug and ran a couple of type checkers.

mypy

error: Return type "list[A]" of "list_method" incompatible with return type "list[A | B]" in supertype "ParentClass"  [override]
Found 1 error in 1 file (checked 1 source file)

ty

error[invalid-method-override]: Invalid override of method `list_method`
  --> example.py:29:9
   |
27 |         return (A("hey"), A("ho"))
28 |
29 |     def list_method(self) -> list[A]:
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Definition is incompatible with `ParentClass.list_method`
30 |         return [A("hey"), A("ho")]
   |
  ::: example.py:19:9
   |
17 |         return (A("hey"), B(5))
18 |
19 |     def list_method(self) -> list[A | B]:
   |         -------------------------------- `ParentClass.list_method` defined here
20 |         return [A("hey"), B(5)]
   |
info: This violates the Liskov Substitution Principle
info: rule `invalid-method-override` is enabled by default

pyrefly

ERROR Class member `ChildClass.list_method` overrides parent class `ParentClass` in an inconsistent manner [bad-override]
  --> example.py:29:9
   |
29 |     def list_method(self) -> list[A]:
   |         ^^^^^^^^^^^
   |
  `ChildClass.list_method` has type `BoundMethod[ChildClass, (self: ChildClass) -> list[A]]`, which is not assignable to `BoundMethod[ChildClass, (self: ChildClass) -> list[A | B]]`, the type of `ParentClass.list_method`
 INFO 1 error

And so it had to be me, not them. Reason enough to take a step back and revisit the basics.

LSP

Let us recall Liskov’s substitution principle:

$$ C_1 \leq C_2 \rightarrow ( \forall o(C_2), \psi(o(C_2)) \rightarrow \forall o(C_2), \psi(o(C_2))) $$

where

• $C_1$ and $C_2$ are types
• $o(C_i)$ is an object instantiating type $C_i$
• $\psi$ is a provable property

In other words, if a type $C_1$ is a subtype of another, $C_2$, every property that is provable for $C_2$ is also provable for $C_1$.

Types meet classes

In Python,

Creating a new class creates a new type of object, allowing new instances of that type to be made

Source: https://docs.python.org/3/tutorial/classes.html

Yet, in general, inheritance does not guarantee substitutability.

Narrow vs wide

subset or superset of provable properties

subset/superset of possible runtime values

Overwriting methods

Combining the general LSP principle as well as the type-class correspondence in Python, we can conclude that when overwriting methods from a parent class,

Parameter types can only get broader (contravariance) Return types can only get narrower (covariance)

We could make the contravariance case by defining $\psi$ as follows:

$$\psi(o) := \mathbb{I}[\text{The method f(x: T) can deal with anything that behaves like the public API of type T}]$$

Similarly, we could make the covariance case by defining $\psi$ as follows:

$$\psi(o) := \mathbb{E}[\text{The method f(…) -> T TODO]$$

Example:

class Animal:
   def recreate(self, other: Animal) -> Animal | None: ...

biological perspective, no bueno

class Dog(Animal):
   def recreate(self, other: Dog) -> Dog | None: ...

kosher:

class Dog(animal):
   def recreate(self, other: Animal) -> Dog | None: ...

Footnote: in practice

class Dog(Animal):
   def recreate(self, other: Self) -> Self | None: ...

Variances¹²

Having encountered contravariance and covariance already, it is now time to talk about the third kind of variance: invariance. As the name suggests, if two types are invariant, we can’t say anything about their subtyping or substitutability properties.

Let’s recap our variances:

• Covariance: $C_1 \leq C_2 \rightarrow TC[C_1] \leq TC[C_2]$
• Contravariance: $C_1 \leq C_2 \rightarrow TC[C_1] \geq TC[C_2]$
• Invariance: $C_1 \leq C_2 \centernot\rightarrow TC[C_1] \leq TC[C_2] \wedge C_1 \leq C_2 \centernot\rightarrow TC[C_1] \geq TC[C_2]

where $TC$ is a ’type constructor’. A type constructor could, for instance, be the process of defining a method³ or the process of creating compound or container types.

Container types in Python

class A:
    def foo(self, x):
        print(x)

class B:
    def foo(self, x):
        print(f"~~~ {x} ~~~ ")

    def foo2(self, x):
        print(f" <<< {x} >>> ")

l = [A(), A(), A()]
l2: list[A | B] = [A(), B(), A()]
l3 = [B(), B(), B()]

# type checker not happy
l2 = l3
l2 += [A()]
# interpreter not happy
l3[-1].foo2("hi")


# type checker not happy
l2 = l3.copy()
l2 += [A()]
# interpreter happy
l3[-1].foo2("hi")

Sequence narrower than List

Inline formula \(\lambda = \omega\)