Why list[Dog] is not a list[Animal]

This is the error message that makes people give up on Python typing:

error: Argument 1 to "summarise" has incompatible type "list[dict[str, str]]";
       expected "list[dict[str, object]]"
note: "list" is invariant -- see https://mypy.readthedocs.io/en/stable/common_issues.html#variance
note: Consider using "Sequence" instead, which is covariant

The reaction is almost always the same: add a cast, or widen every dict in the caller to dict[str, object], or give up and annotate the parameter Any. All three suppress a real soundness hole instead of fixing a real signature.

The mutation argument, first

Forget the vocabulary. Ask what could go wrong if list[Dog] were a list[Animal]:

def add_a_cat(animals: list[Animal]) -> None:
    animals.append(Cat())

dogs: list[Dog] = [Dog()]
add_a_cat(dogs)        # if this were allowed...
dogs[0].fetch()        # ...this would be an AttributeError on a Cat

The callee did nothing wrong. It was handed a list[Animal] and appended an Animal. The unsoundness is entirely in the call. So a mutable container cannot be covariant in its element type — that is not a limitation of Python’s type system, it is arithmetic.

Now the three words:

• Covariant — C[Dog] is a C[Animal]. Safe when you can only read out.
• Contravariant — C[Animal] is a C[Dog]. Safe when you can only write in.
• Invariant — neither. Required when you can do both.

And the stdlib’s choices follow directly:

Mapping being covariant in the value but invariant in the key is the detail people miss. Keys are used for lookup — they appear in a parameter position of __getitem__ — which is why they cannot be covariant.

The task

def summarise(records: Sequence[Mapping[str, object]]) -> dict[str, int]:
def solve(records: list[list[list[object]]]) -> tuple[list[str], list[int], list[int]]:

solve receives each record as an ordered list of [key, value] pairs and rebuilds it into a dict[str, object] before handing the batch to summarise. First-seen order is part of summarise‘s contract, and the key order of a JSON object is not something you may rely on: a dict preserves insertion order, but the insertion order of a mapping that arrived over a wire is whatever the encoder and the store in the middle decided. A pair list has exactly one order, and it is the one that was written down.

summarise counts the non-None values per key, across all records, and returns a dict whose keys are in first-seen order. A key that appears only with None values is still present, with a count of 0 — it was seen, it just never had a value. Falsy-but-present values (0, "", [], False) count; only None does not, so the test must be is not None, not truthiness.

solve returns (keys in order, counts in the same order, witnesses), where witnesses is summarise(NARROW_RECORDS) and summarise(WIDE_RECORDS) concatenated. Those two module constants are declared

NARROW_RECORDS: Final[list[dict[str, str]]]
WIDE_RECORDS: Final[tuple[dict[str, int], ...]]

and calling summarise on either is the entire exercise. With the correct signature both calls type-check: a list is a Sequence, a tuple is a Sequence, dict[str, str] and dict[str, int] are both Mapping[str, object] because Mapping is covariant in its value. With the starter’s signature — list[dict[str, object]] — both fail, and no amount of fixing the call sites helps.

The keys and counts are returned as two parallel lists rather than as a dict, because dict comparison ignores order and first-seen order is part of the contract.

The rule to take away

Accept broad, return narrow. Take Sequence[T] if you index or need len, Iterable[T] if you iterate once, Mapping[K, V] if you only read. Return list[T] and dict[K, V] — the caller can always widen what you give them.

The exception is real and worth stating: if you mutate the argument, list[T] is the correct annotation and its invariance is doing exactly the job it exists to do. Reaching for Sequence there would be a bug, not a generalisation.