Recursive types in Python and difficulties inferring the type of `type(x)(...)`

Question

Trying to build recursive types to annotate a nested data structure, I hit the following.

This code is correct according to mypy:

IntType = int | list["IntType"] | tuple["IntType", ...]
StrType = str | list["StrType"] | tuple["StrType", ...]


def int2str(x: IntType) -> StrType:
    if isinstance(x, list):
        return list(int2str(v) for v in x)
    if isinstance(x, tuple):
        return tuple(int2str(v) for v in x)
    return str(x)

But not this one, which should be equivalent:

IntType = int | list["IntType"] | tuple["IntType", ...]
StrType = str | list["StrType"] | tuple["StrType", ...]

def bad_int2str(x: IntType) -> StrType:
    if isinstance(x, (list, tuple)):
        return type(x)(bad_int2str(v) for v in x)  # error here
    return str(x)

The error message is

line 6: error: Incompatible return value type (
    got "list[int | list[IntType] | tuple[IntType, ...]] | tuple[int | list[IntType] | tuple[IntType, ...], ...]", 
    expected "str | list[StrType] | tuple[StrType, ...]"
)  [return-value]
line 6: error: Generator has incompatible item type 
    "str | list[StrType] | tuple[StrType, ...]"; 
    expected "int | list[IntType] | tuple[IntType, ...]"  [misc]

I would assume mypy could infer that type(x) is either list or tuple. Is this a limitation of mypy or is there something fishy with this code? If so, where does the limitation come from?

Answer 1

There's no type erasure for type(x).

What should mypy say about the following?

x: list[int] = [1]
reveal_type(type(x))

If we ask, it says:

Revealed type is "type[builtins.list[builtins.int]]"

So, when you ask for type(x)(some_strtype_iterator), it rightfully complains that you try to construct a list[StrType] | tuple[StrType, ...] from an iterable of IntType.

Both errors hint about that fact: mypy thinks that you return a list or tuple of IntType, because the error inside the expression does not make it lose an already known type. And it also points out that you can't build a list/tuple of IntType from a generator yielding StrType - you didn't intend to build IntType sequence, but type(x) mandates that.

I just started a discussion on the typing forum to clarify the reasons for not erasing the generics for type(x).