Mypy: List[T] concatenation is incompatible to List[Optional[T]]

[tueda]

mypy --strict-optional (version 0.550) gives an incompatible-type error for

from typing import List, Optional
a = [1, 2]
b = [3, 4]
c = []  # type: List[Optional[int]]
c = list(a + b)  # OK
c = a + b        # ERROR

foo.py:6: error: Incompatible types in assignment (expression has type "List[int]", variable has type "List[Optional[int]]")

I believe a + b always creates a new list (even if one of them is empty) and so equivalent to list(a + b). Actually, reveal_type gives builtins.list[builtins.int*] for the both.

[gvanrossum]

This is because List is invariant. See http://mypy.readthedocs.io/en/latest/common_issues.html#invariance-vs-covariance

The reason that c = list(a + b) passes is subtle -- the list.__init__() constructor's argument is Iterable[T] and that is covariant.

[JelleZijlstra]

I'm not sure that's right. This code is actually type safe, because it creates a new list.

This is prohibited because of invariance:

a: List[int]
b: List[Optional[int]]
a += b  # error, because a can't have Nones

But this is safe and I think should be allowed (and it's what the OP wants to do):

a: List[int]
b: List[Optional[int]]
c = a + b # now c should be a List[Optional[int]]

Typeshed's signature for list.__add__ is currently def __add__(self, x: List[_T]) -> List[_T]: .... If I change that to def __add__(self, x: List[_S]) -> List[Union[_T, _S]]: ..., the OP's example works, but mypy complains that the signatures for __add__ and __iadd__ are incompatible. To make this work, we'll therefore need special casing in mypy.

[gvanrossum]

I believe that whether c = a + b is safe depends on things that cannot be expressed in the type system, in particular that a + b always returns a new list. I'm not in favor of special-casing List in mypy -- variance is a nasty topic but people will just have to learn about it. Usually the right solution is to switch from List to Sequence anyway.

[JelleZijlstra]

Sequence doesn't even support __add__ though.

[gvanrossum]

(Yeah in this particular case it doesn't work. But this special case isn't enough to convince me to change the rules.)

[tueda]

Thanks. Now I understand why mypy complains. The reason why I was using List instead of Sequence for c was because my original code used None as a kind of "visited" flag and so actually I needed a mutable list:

a: Sequence[SomeClass]
b: Sequence[SomeClass]
c = list(a) + list(b)  # type: List[Optional[SomeClass]]
while some_loop_condition():
    for i, x in enumerate(c):
        if x is not None:
            if some_condition(x):
                consume_this_element(i, x)
                c[i] = None
                break

But putting the concatenation into list surely works, and probably anyway I should rethink to write the above code in a smarter way.