Why is a list of lists not a list of sequences?

I've created the following example:

from typing import List, Sequence

class Circle:
    pass

def foo(circle: Circle) -> Sequence[Circle]:
    return_value: List[Circle] = [circle]
    return return_value

def bar(circle: Circle) -> List[Sequence[Circle]]:
    # Incompatible return value type (got "List[List[Circle]]", expected "List[Sequence[Circle]]")
    return_value: List[List[Circle]] = [[circle]]
    return return_value

Why is it okay to return a List[Circle] when it's expecting a Sequence[Circle], but not a List[List[Circle]] when it's expecting a List[Sequence[Circle]]?

More specifically, why is this not okay when the value is a return value? I think I understand why it's not okay as a parameter, but I don't get why this value is not accepted as a return value.

The docs give a great example displaying why Lists are invariant:

class Shape:
    pass

class Circle(Shape):
    def rotate(self):
        ...

def add_one(things: List[Shape]) -> None:
    things.append(Shape())

my_things: List[Circle] = []
add_one(my_things)     # This may appear safe, but...
my_things[0].rotate()  # ...this will fail

Here, the idea is if you take your List[Subclass] and pass it to something that thinks it's a List[Superclass], the function can edit your List[Subclass] so that it contains Superclass elements, so it becomes a List[Superclass] after the function is run.

However, as a return value, I don't see why this is an issue. Once it exits that function, everyone will treat it as a List[Sequence[Circle]], which it is, so there should be no issues.

Solution

Once again, while typing up this question, I think I have figured out an answer to it.

Consider the following case:

from typing import List, Sequence

class Circle:
    pass

def baz(circle_list_matrix: List[List[Circle]]) -> List[Sequence[Circle]]:
    # Incompatible return value type (got "List[List[Circle]]", expected "List[Sequence[Circle]]")
    return circle_list_matrix

Here, Mypy is absolutely right to raise the error, because the other functions that are using the circle_list_matrix may depend on it being a List[List[Circle]], but other functions afterwards may modify it to be a List[Sequence[Circle]].

In order to determine which case we're in, Mypy would have to keep track of when our variables were declared, and ensure that nothing ever depends on treating the return value as a List[List[Circle]] after the function returns (even though it is typed as such) before allowing us to use it as a return value.

(Note that treating it like a List[List[Circle]] before the function returns shouldn't be a bad thing, since it is a List[List[Circle]] at those points. Also if it was always treated like it was a List[Sequence[Circle]], then we could just type it as such with no problem. The question arises when something treats it like a List[List[Circle]], for example with circle_list_matrix[0].append(Circle()), so we have to type it as a List[List[Circle]] in order to do that operation, but then it's treated as a List[Sequence[Circle]] every single time after the function returns.)

The bottom line is that Mypy doesn't do that sort of analysis. So, in order to let Mypy know that this is okay, we should just cast it.

In other words, we know that the return value will never be used as a List[List[Circle]] again, so baz should be written as:

def baz(circle_list_matrix: List[List[Circle]]) -> List[Sequence[Circle]]:
    # works fine
    return cast(List[Sequence[Circle]], circle_list_matrix)

where cast is imported from typing.

The same casting technique can be applied to bar in the question code.