[Type Hints] basedpyright typing error in recursive flattening function

Python Help
,
1

I’ve got a function deep_flatten which takes a potentially nested list and flattens it. For instance: deep_flatten([1, [2, 3]]) returns [1, 2, 3].

I’m aware there are far better ways to go about it. This is just a toy example to experiment with Python typing and a few type checkers.

from collections.abc import Iterable

type NestedIter[T] = Iterable[T | NestedIter[T]]


def deep_flatten[T](input_iterable: NestedIter[T]) -> list[T]:
    flattened: list[T] = []
    for item in input_iterable:
        if isinstance(item, Iterable):
            flattened.extend(deep_flatten(item))
        else:
            flattened.append(item)
    return flattened


if __name__ == "__main__":
    res = deep_flatten([1, [2, 3]])
    print(res)

The example above doesn’t raise any warnings or errors both with mypy --strict and pyright. However, if I check it with basedpyright I get an error I’m struggling to make sense of:

/workspaces/flatten.py:10:30 - error: Argument of type "list[object]" cannot be assigned to parameter "iterable" of type "Iterable[T@deep_flatten]" in function "extend"
    "list[object]" is not assignable to "Iterable[T@deep_flatten]"
      Type parameter "_T_co@Iterable" is covariant, but "object" is not a subtype of "T@deep_flatten"
        Type "object" is not assignable to type "T@deep_flatten" (reportArgumentType)
1 error, 0 warnings, 0 notes

The error propagates from flattened.extend(deep_flatten(item)). The issue seems to be that the output of the recursive call, which is expected to be of type Iterable[T], is instead “evaluated” as list[object].

Is this an issue that can be solved? If so, I’d appreciate any suggestions on how to improve the typing in this example, an maybe a brief explanation as to why the output of the recursive call is not “evaluated” as I’d expect i.e. as Iterable[T].

2

this error is due to basedpyright’s stricter behavior for narrowing generics. when you do an isinstance check with a type that takes a generic, both mypy and pyright will fill in that generic with Any, which is unsafe. in many cases a more accurate type can be inferred eg. by using the the generic’s bound instead. more info in the docs.

you can disable this behavior by setting strictGenericNarrowing to false, which will make it behave the same way as pyright.

(fyi pyright will actually report an error in the same spot if you enable reportUnknownArgumentType. playground)

as for your example, the problem here is that isinstance(item, Iterable) isn’t a fool-proof way to determine whether the current item is nested or not. for example if the type bound to T is iterable, this check will return True for a non-nested item:

res: list[list[int]] = deep_flatten([[[1], [2, 3]]])
reveal_type(res) # list[list[int]]
print(res) # [1, 2, 3]

playground

here, T is bound to list[int] so we’re telling the type checker that an item of type list[list[list[int]]] will get flattened to list[list[int]], but list[list[int]] won’t get narrowed to list[int]. this information is not known at runtime which is why it’s unsafe.

3

First of all, thank you for taking the time to help @DetachHead, I couldn’t hope for a better person to chime in! Secondly, I really appreciate your efforts to provide an alternative to pyright.

Just to make sure I more or less get it: one of the issues here is that the type checker cannot really be sure what exactly an item is; checking with isinstance provides an hint but it doesn’t really tell us whether we’re dealing with a flat or nested Iterable. Correct?

Also, running reveal_type(deep_flatten(item)) I see that the type checker evaluates it as list[object], which seems to be exactly the root of the original error:

error: Argument of type "list[object]" cannot be assigned to parameter "iterable" of type "Iterable[T@deep_flatten]" in function "extend"

In the documentation page about “improved type narrowing” that you pointed me to, it says that

in cases where the generic is covariant, contravariant, or uses constraints, it can be narrowed more accurately.

So I tried to change my code as follows, bounding T to float, and indeed all errors and warnings are solved. However, I’m afraid I don’t quite get what’s going on.

from collections.abc import Iterable

type NestedIter[T] = Iterable[T | NestedIter[T]]

def deep_flatten[T: float](input_iterable: NestedIter[T]) -> list[T]:
    flattened: list[T] = []
    for item in input_iterable:
        if isinstance(item, Iterable):
            # reveal_type(item)
            # reveal_type(deep_flatten(item))
            flattened.extend(deep_flatten(item))
        else:
            flattened.append(item)
    return flattened

if __name__ == "__main__":
    res = deep_flatten([1, [2, 3]])
    print(res)

Also, both reveal_type(item) and reveal_type(deep_flatten(item)) now report the expected types:

# old outputs
Type of "item" is "Iterable[object]* | Iterable[T@deep_flatten | NestedIter[T@NestedIter]]"
Type of "deep_flatten(item)" is "list[object]"

# new outputs
Type of "item" is "Iterable[T@deep_flatten | NestedIter[T@NestedIter]]"
Type of "deep_flatten(item)" is "list[T@deep_flatten]"

I just have a couple more questions I’d appreciate your input on:

  1. Why bounding T to float was enough to help the type checker this much? In other words, how is this solving the original issue with the isinstance check not being “fool-proof”, and how does it help the type checker to correctly evaluate deep_flatten(item) as list[T@deep_flatten]?
  2. Is bounding T to float the same solution you’d have chosen?
4

First of all, thank you for taking the time to help @DetachHead, I couldn’t hope for a better person to chime in! Secondly, I really appreciate your efforts to provide an alternative to pyright.

thanks! i don’t often check this forum btw so it’s lucky i saw your post. in the future feel free to open an issue at https://github.com.detachhead/basedpyright if you have any more questions and i’d be happy to try to help, since i’ll be much more likely to see it

In the documentation page about “improved type narrowing” that you pointed me to, it says that

in cases where the generic is covariant, contravariant, or uses constraints, it can be narrowed more accurately.

So I tried to change my code as follows, bounding T to float, and indeed all errors and warnings are solved. However, I’m afraid I don’t quite get what’s going on.

what you have here is a bound, not a constraint. constraints are a completely different thing to regular generics. they are essentially fake generics that are more like overloads. a constrained generic is defined using tuple syntax (eg. foo[T: (int, str)]) whereas a regular generic bound just looks like foo[T: int | str]:

from typing import Literal, overload

# T is a constraint of either int or str:
def foo[T: (int, str)](value: T) -> T: ...

# but it can't be resolved to a subtype such as Literal[1], it can only be exactly int or str:
a: Literal[1] = 1
reveal_type(foo(a)) # int

# the above function is equivalent to:
@overload
def foo(value: int) -> int: ...
@overload
def foo(value: str) -> str: ...

more info about constraints here. honestly i think they are a really stupid, useless feature that does nothing but cause confusion to users who are trying to learn about generics. for your example, they aren’t relevant at all so you don’t need to worry about them.

def deep_flatten[T: float](input_iterable: NestedIter[T]) -> list[T]: ...

this fixes the issue because you’re ensuring that the generic can never be bound to an Iterable, so that isinstance check will now always only return True if the item is nested, because otherwise there’s no other way for an item to be Iterable.

when T has no bound (or if it’s bound to a type that can potentially be Iterable), that’s when it becomes unsafe. perhaps it might be a bit easier to visualize if we convert it to a class so we can explicitly specify the generic:

from collections.abc import Iterable
from typing import reveal_type

type NestedIter[T] = Iterable[T | NestedIter[T]]


class deep_flatten[T]:
    def __init__(self, input_iterable: NestedIter[T]):
        flattened: list[T] = []
        for item in input_iterable:
            if isinstance(item, Iterable):
                flattened.extend(deep_flatten(item).result)
            else:
                flattened.append(item)
        self.result: list[T] = flattened

if __name__ == "__main__":
    res = deep_flatten[Iterable[int]]([[1], [2, 3]])
    reveal_type(res) # deep_flatten[Iterable[int]]
    reveal_type(res.result) # list[Iterable[int]], actually list[int] at runtime

to summarize, the issue is that because you are allowed to specify T as Iterable[int], it means you are allowed to tell the type checker that you are flattening a list[list[Iterable[int]]] into a list[Iterable[int]] which is probably not what you want to do, and not what happens at runtime. ideally you would want to be able to enforce that T is any type that’s not iterable, but i don’t think it’s possible to do such a thing

1 Like