Kinded type behaving differently from non-kinded type in an invariant wrapper

[pradeep90]

Hi Nikita, long time! Thanks for the interesting library bringing Haskell-like FP patterns to Python.

Bug report

What's wrong

I'm trying to extract the type T from a Kind1 type (say, Foo[T]) that is wrapped in an invariant type, e.g., list[Foo[T]]. However, that's leading to some unexpected behavior.

Repro:

from typing import Any, TypeVar

from returns.primitives import hkt

T = TypeVar("T")


class Foo(hkt.SupportsKind1["Foo[Any]", T]):
    pass


# These are just helper functions to extract the type `T`.
def expect_list_foo(foo_list: list[Foo[T]]) -> list[T]:
    return []


@hkt.kinded
def expect_list_foo__kinded(foo_list: list[hkt.Kind1[Foo[Any], T]]) -> list[T]:
    return []


@hkt.kinded
def expect_tuple_foo__kinded(foo_tuple: tuple[hkt.Kind1[Foo[Any], T], str]) -> list[T]:
    return []


def inferred_types(foo_list: list[Foo[int]], foo_tuple: tuple[Foo[int], str]) -> None:
    x = expect_list_foo(foo_list)

    y = expect_list_foo__kinded(foo_list)  # <-- Problem

    z = expect_tuple_foo__kinded(foo_tuple)

    reveal_type(x)
    reveal_type(y)
    reveal_type(z)

    print(x, y, z)

How is that should be

I expected all three calls to work and return list[int].

Actual output:

30: error: Argument 1 to "expect_list_foo__kinded" has incompatible type "list[Foo[int]]"; expected "list[KindN[Foo[Any], int, Any, Any]]"  [arg-type]
30: note: "List" is invariant -- see https://mypy.readthedocs.io/en/stable/common_issues.html#variance
30: note: Consider using "Sequence" instead, which is covariant
34: note: Revealed type is "builtins.list[builtins.int]"
35: note: Revealed type is "builtins.list[builtins.int]"
36: note: Revealed type is "builtins.list[builtins.int]"
Found 1 error in 1 file (checked 1 source file)

Seems like list[Foo[int]] is not treated as compatible with list[hkt.Kind1[Foo[Any], T]]. tuple[Foo[int], str] is treated as compatible with tuple[hkt.Kind1[Foo[Any], T], str]. So, it seems like this might be due to the invariance of list.

Is this expected behavior? How can I get this to work?

System information

• python version: 3.10.8

• returns version: 0.24.0

• mypy version: 1.15.0

• hypothesis version (if any):

• pytest version (if any):

[sobolevn]

Hi, @pradeep90! Great to see you 😊

Is this expected behavior? How can I get this to work?

Well, this is a very hard question, actually. I've never expirienced this before.

Several ideas that I have right now:

• KindN with @kinded fully eleminates itself, so in this context list[hkt.Kind1[Foo[Any], T]] is list[Foo[T]]
• But maybe in contexts where we don't have @kinded there might be a different logic?

You are very welcome to investigate further. I would love to get a PR with the fix / docs update :)

[pradeep90]

Hi, @pradeep90! Great to see you 😊

Is this expected behavior? How can I get this to work?

Well, this is a very hard question, actually. I've never expirienced this before.

Thanks for getting back. I appreciate it.

Several ideas that I have right now:

* `KindN` with `@kinded` fully eleminates itself, so in this context `list[hkt.Kind1[Foo[Any], T]]` is `list[Foo[T]]`

* But maybe in contexts where we don't have `@kinded` there might be a different logic?

You are very welcome to investigate further. I would love to get a PR with the fix / docs update :)

I dug into the code and found the root cause :)

We are passing an argument of type list[Foo[int]] to a parameter of type list[Kind1[Foo, T]]. The type checker needs to check whether the argument type is compatible. The way it checks depends on the variance of the container:

• For a covariant type like tuple, it just checks the inner types in one direction: Is Foo[int] compatible with Kind1[Foo, int]? That is true since Foo is a descendant of Kind1[Foo, Int].
• For an invariant type like list, it also checks the inner types in the other direction: Is Kind1[Foo, int] compatible with Foo[int]. This fails because KindN[Foo, int] is not a descendant of Foo[int] :|

In short, the returns Mypy plugin adds HKT support in one direction not the other. So, Foo[int] and Kind1[Foo, int] are not truly substitutable for each other :| The same problem will occur any time we have an invariant or contravariant container (e.g., Callable) around a kinded type.

Some options I can think of to fix this:

• Remove the spurious error emitted by Mypy: It is stored in ctx.api.errors.error_info_map. However, this would be hacky.
• Deeper fix: Somehow tell Mypy that KindN[IO, int] is a "subclass" of or in some way compatible with IO[int]. I couldn't find a way to express that using the Mypy plugin API, but others may know a way.

If you have any ideas, let me know. If not, I'll probably not be digging further, but I'll leave this root-cause information here for future use.

[sobolevn]

Hm, thank you for indepth analysis, maybe we should use two types? Like KindN which is a supertype and SubKindN which will be subtype? This is also an open question.

[pradeep90]

Hm, thank you for indepth analysis, maybe we should use two types? Like KindN which is a supertype and SubKindN which will be subtype? This is also an open question.

Hmm... Interesting direction. I'm not clear how that would help solve Kind1[IO, int] <: IO[int], though. Perhaps you could clarify that.

Another option: Dynamically add one overload per HKT that is in scope. This is the old idea from your blog post, but generating the overloads dynamically in the Mypy plugin instead of hardcoding them. This would be a principled solution and would work as expected, but it could explode the number of overloads :) If there is a way to get the argument type in the method call, it should be doable to specialize the method with overloads for just the possible HKTs that are in the argument type.

However, get_method_signature_hook is called before argument types are available, and get_method_hook is called after the error has been added. So, I don't know of a clean solution here.

[sobolevn]

Another option: Dynamically add one overload per HKT that is in scope.

This is cool! It can work indeed.