Higher-Kinded TypeVars

[tek]

aka type constructors, generic TypeVars

Has there already been discussion about those?
I do a lot of FP that results in impossible situations because of this. Consider an example:

A = TypeVar('A')
B = TypeVar('B')
F = TypeVar('F')

class M(Generic[F[X], A]):
    def x(fa: F[A], f: Callable[[A], B]) -> F[B]:
        return map(f, fa)

M().x([1], str)

I haven't found a way to make this work, does anyone know a trick or is it impossible?
If not, consider the syntax as a proposal.
Reference implementations would be Haskell, Scala.
optimally, the HK's type param would be indexable as well, allowing for F[X[X, X], X[X]]

---

Summary of current status (by @smheidrich, 2024-02-08):

• @JelleZijlstra has indicated interest in sponsoring a PEP, conditional on a prototype implementation in a major type checker and a well-specified draft PEP.
• Drafting the PEP takes place in @nekitdev's fork of the peps repo. The stub PEP draft so far contains a few examples of the proposed syntax.
• That same repo's GitHub Discussions forum forum has been designated as the place to discuss the PEP (and presumably the prototype implementation?). Some limited further discussions have taken place there.
  • If you want to be notified of new discussion threads, I think you have to set the whole repo as "watched" in GitHub?

[ilevkivskyi]

I think this came up few times in other discussions, for example one use case is python/mypy#4395. But TBH this is low priority, since such use cases are quite rare.

[tek]

damn, I searched very thoroughly but did not find this one! 😄
So, consider this my +1!

[gvanrossum]

Adding your +1 is all fine, but who's going to do the (probably pretty complicated) implementation work?

[tek]

are you approving the feature?

[gvanrossum]

I am neither approving nor disapproving. Just observing that it may be a lot of work for marginal benefits in most codebases.

[tek]

awfully pragmatic. Where's your sense of adventure? 😄
anyways, I'll work on it, though it's gonna take a while to get into the project.

[landonpoch]

Similar to microsoft/TypeScript#1213

Not sure if the discussion over there provides any useful insights to the effort over here.

[rcalsaverini]

Hi @tek. I'm also very interested in this, so I'd like to ask if you had any progress with this and volunteer to help if you want.

[tek]

@rcalsaverini sorry, I've been migrating my legacy code to haskell and am abandoning python altogether. but I wish you great success!

[rcalsaverini]

Oh, sad to hear but I see your point. Thanks.

[syastrov]

Just to add another use case (which I think relates to this issue):

Using Literal types along with overloading __new__, along with higher-kinded typevars could allow implementing a generic "nullable" ORM Field class, using a descriptor to provide access to the appropriate nullable-or-not field values. The descriptor wouldn't have to be reimplemented in subclasses.

It is one step closer to being possible due to the most recent mypy release's support for honoring the return type of __new__ (python/mypy#1020).

Note: this is basically a stripped-down version of Django's Field class:

# in stub file

from typing import Generic, Optional, TypeVar, Union, overload, Type
from typing_extensions import Literal

_T = TypeVar("_T", bound="Field")
_GT = TypeVar("_GT")

class Field(Generic[_GT]):
    # on the line after the overload: error: Type variable "_T" used with arguments
    @overload
    def __new__(cls: Type[_T], null: Literal[False] = False, *args, **kwargs) -> _T[_GT]: ...
    @overload
    def __new__(cls: Type[_T], null: Literal[True], *args, **kwargs) -> _T[Optional[_GT]]: ...
    def __get__(self, instance, owner) -> _GT: ...

class CharField(Field[str]): ...
class IntegerField(Field[int]): ...
# etc...

# in code

class User:
  f1 = CharField(null=False)
  f2 = CharField(null=True)

reveal_type(User().f1) # Expected: str
reveal_type(User().f2) # Expected: Union[str, None]

[samuelcolvin]

I wonder if this is what I need or if there's currently a work around for my (slightly simpler) case?:

I'm building an async redis client with proper type hints. I have a "Commands" class with methods for all redis commands (get, set, exists, strlen ... and hundreds more). Normally each of those methods should return a future (actually coroutine) to the result, but in pipeline mode they should all return None - the commands are added to the pipeline to be executed later.

This is easy enough to implement in python, but not so easy to type hint correctly.

Basic example:

class Redis:
    def execute(self, command) -> Coroutine[Any, Any, Union[None, str, int, float]]:
        return self.connection.execute(...)

    def get(self, *args) -> Coroutine[Any, Any, str]:
        ...
        return self.execute(command)

    def set(self, *args) -> Coroutine[Any, Any, None]:
        ...
        return self.execute(command)

    def exists(self, *args) -> Coroutine[Any, Any, bool]:
        ...
        return self.execute(command)

    # ... and many MANY more ...


class RedisPipeline(Redis):
    def execute(self, command) -> None:
        self.pipeline.append(command)

I tried numerous options to make Coroutine[Any, Any, xxx] generic, but nothing seems to work.

Is there any way around this with python 3.8 and latest mypy? If not a solution would be wonderful - as far as I can think, my only other route for proper types is a script which copy and pastes the entire class and changes the return types in code.

[gvanrossum]

@samuelcolvin I don't think this question belongs in this issue. The reason for the failure (knowing nothing about Redis but going purely by the code you posted) is that in order to make this work, the base class needs to switch to an Optional result, i.e.

    def execute(self, command) -> Optional[Coroutine[Any, Any, Union[None, str, int, float]]]:

[samuelcolvin]

I get that, but I need all the public methods to definitely return a coroutine. Otherwise, if it returned an optional coroutine, it would be extremely annoying to use.

What I'm trying to do is modify the return type of many methods on the sub-classes, including "higher kind" types which are parameterised.

Hence thinking it related to this issue.

[gvanrossum]

Honestly I have no idea what higher-kinded type vars are -- my eyes glaze over when I hear that kind of talk. :-)

I have one more suggestion, then you're on your own. Use a common base class that has an Optional[Coroutine[...]] return type and derive both the regular Redis class and the RedisPipeline class from it.

[samuelcolvin]

Okay, so the simple answer is that what I'm trying to do isn't possible with python types right now.

Thanks for helping - at least I can stop my search.

[gvanrossum]

I suspect that the reason is that it simply isn't type-safe, and you couldn't do it (using subclassing) in any other typed language either.

[samuelcolvin]

humm, but the example above under "Basic example" I would argue IS type-safe.

All the methods which end return self.execute(...) return what execute returns - either a Coroutine or None.

Thus I don't see how this as any more "unsafe" than normal use of generics.

[jab]

@gvanrossum, I can relate!

I wonder if bidict provides a practical example of how this issue prevents expressing a type that you can actually imagine yourself needing.

>>> element_by_atomicnum = bidict({0: "hydrogen", 1: "helium"})
>>> reveal_type(element_by_atomicnum)  # bidict[int, str]
# So far so good, but now consider the inverse:
>>> element_by_atomicnum.inverse
bidict({"hydrogen": 0, "helium": 1})

What we want is for mypy to know this:

>>> reveal_type(element_by_atomicnum.inverse)  # bidict[str, int]

merely from a type hint that we could add to a super class. It would parameterize not just the key type and the value type, but also the self type. In other words, something like:

KT = TypeVar('KT')
VT = TypeVar('VT')

class BidirectionalMapping(Mapping[KT, VT]):
    ...
    def inverse(self) -> $SELF_TYPE[VT, KT]:
        ...

where $SELF_TYPE would of course use some actually legal syntax that allowed composing the self type with the other parameterized types.

[gvanrossum]

Okay, I think that example is helpful. I recreated it somewhat simpler (skipping the inheritance from Mapping and the property decorators):

from abc import abstractmethod
from typing import *

T = TypeVar('T')
KT = TypeVar('KT')
VT = TypeVar('VT')

class BidirectionalMapping(Generic[KT, VT]):
    @abstractmethod
    def inverse(self) -> BidirectionalMapping[VT, KT]:
        ...

class bidict(BidirectionalMapping[KT, VT]):
    def __init__(self, key: KT, val: VT):
        self.key = key
        self.val = val
    def inverse(self) -> bidict[VT, KT]:
        return bidict(self.val, self.key)

b = bidict(3, "abc")
reveal_type(b)  # bidict[int, str]
reveal_type(b.inverse())  # bidict[str, int]

This passes but IIUC you want the ABC to have a more powerful type. I guess here we might want to write it as

    def inverse(self: T) -> T[VT, KT]:  # E: Type variable "T" used with arguments

Have I got that?

[jab]

Exactly! It should be possible to e.g. subclass bidict (without overriding inverse), and have mypy realize that calling inverse on the subclass gives an instance of the subclass (with the key and value types swapped as well).

This isn’t only hypothetically useful, it’d really be useful in practice for the various subclasses in the bidict library where this actually happens (frozenbidict, OrderedBidict, etc.).

Glad this example was helpful! Please let me know if there’s anything further I can do to help here, and (can’t help myself) thanks for creating Python, it’s such a joy to use.

[gvanrossum]

Ah, so the @abstractmethod is also a red herring.

And now I finally get the connection with the comment that started this issue.

But I still don't get the connection with @samuelcolvin's RedisPipeline class. :-(

[sobolevn]

I would also say that this example is really simple, common, but not supported:

def create(klass: Type[T], value: K) -> T[K]:
     return klass(value)

We use quite a lot of similar constructs in dry-python/returns.

As a workaround I am trying to build a plugin with emulated HKT, just like in some other languages where support of it is limited. Like:

• Swift and bow: https://bow-swift.io/docs/fp-concepts/higher-kinded-types/
• TypeScript and fp-ts: https://github.com/gcanti/fp-ts/blob/master/src/HKT.ts

Paper on "Lightweight higher-kinded polymorphism": https://www.cl.cam.ac.uk/~jdy22/papers/lightweight-higher-kinded-polymorphism.pdf

TLDR: So, instead of writing T[K] we can emulate this by using HKT[T, K] where HKT is a basic generic instance processed by a custom mypy plugin. I am working on this plugin for already some time now, but there's still nothing to show. You can track the progress here: https://pypi.org/project/kinds/ (part of dry-python libraries)

[jorenham]

Like @sobolevn mentioned almost 4 years ago, the closest you can get to a solution, is by using the approach that's used in python-returns:

Their approach to e.g.

from typing import TypeVar
from returns.interfaces.container import Container1

T = TypeVar('T', bound=Container1)

def all_to_str(arg: T[int]) -> T[str]:
    ...

is to wrap everythin in "containers" (i.e. monads, but don't say that out loud, monads must remain esoteric for some reason):

>>> from returns.primitives.hkt import Kind1, kinded
>>> from returns.interfaces.container import ContainerN
>>> from typing import TypeVar

>>> T = TypeVar('T', bound=ContainerN)

>>> @kinded
... def to_str(container: Kind1[T, int]) -> Kind1[T, str]:
...     return container.map(str)

However, this requires a mypy plugin to work, so it almost surely will not work with e.g. pyright.

See https://returns.readthedocs.io/en/latest/pages/hkt.html for more info.

[omer54463]

Like @sobolevn mentioned almost 4 years ago, the closest you can get to a solution, is by using the approach that's used in python-returns:

It would work. It's also pretty ugly and counterintuitive. I really don't want to introduce returns into an existing company's codebase out of fear of the termination of my employment.

I'm suggesting making the syntax I mentioned a supported feature - is this not an appropriate place for that?

[jorenham]

@omer54463 Perhaps I wasn't clear about this, but I meant to show that the currently best "solution" to HKT will probably require significant changes to your codebase, requires you to use mypy and a third-party mypy-plugin, and results in verbose and difficult to read code.

The syntax you mentioned earlier uses typing.TypeVar, instead of the new PEP 695 syntax.

I guess that the desireable HKT syntax would look like either

from returns.interfaces.container import Container1

# explicit notation
def all_to_str[T[V]: Container1[V]](arg: T[int]) -> T[str]:
    ...

# implicit notation
def all_to_str[T: Container1](arg: T[int]) -> T[str]:
    ...

or some combination of the two.

[omer54463]

@jorenham I roughly agree about the syntax.
However, there is still a distinction I want to make:

Your intentions seem to be to simulate something like this:

T = TypeVar("T")
V = TypeVar("V")

def f(value: T[V]):
    ...

This makes no sense to me.
T can be any type, not all types receive type arguments.
I am not saying this could not be checked and supported, but it's a much bigger feature.

However, look at this.

T = TypeVar("T")

class MyProtocol(Protocol[T]):
    ...

P = TypeVar("P", bound=MyProtocol)

def f(value: P[T]):
    ...

It's trivial that P gets a generic parameter. It's not because we dictate that when using P, but because the bound type has to be generic.

Is P technically an HKT? I'm pretty sure it is. But it's a much simpler case.

[jorenham]

@omer54463 I don't know what you mean with the first example. It makes me suspect that you don't understand PEP 695, so let me "backport" my previous example into the pre- PEP 695 era:

from typing import TypeVar
from returns.interfaces.container import Container1


V = TypeVar("V", covariant=True)

# implicit notation
T = TypeVar("T", bound=Container1)
# explicit notation
T = TypeVar("T", bound=Container1[V], params=[V])


def all_to_str(arg: T[int]) -> T[str]: ...

The explicit TypeVar syntax here, is just an illustrative example I came up with from the top of my head.

---

In your last example, P denotes the parameter that is bound to some kind of higher type, so I'd consider its use in f: P[T] -> ? as HKT.

[jorenham]

A slightly more involved, realistic example of what HKT could look like in Python:

from collections.abc import Awaitable, Callable


type Maps1[V, R] = Callable[[V], R]

def map_async[V, R, T: Awaitable](fn: Maps1[V, R], aval: T[V]) -> T[R]: ...

# for example:
# map_async(str, asyncio.Task[int]) -> asyncio.Task[str]

This example made me realise that the "explicit notation" from my earlier post isn't going to work.
I can think of two "explicit notations":

• map_async[R, T: Awaitable[V]](fn: Maps1[V, R], aval: T[V]): T[R] - V occurs in both fn and aval, but is bound to V@Awaitable
• map_async[V, R, T: Awaitable[V]](fn: Maps1[V, R], aval: T[V]): T[R] - V is bound to V@Awaitable and to itself, implying equivalence of T[V] and T[R], but V and R need not be equivalent

Both cases are self-contractictory, making my earlier proposal for an "explicit notation" a bad idea.

This leaves the "implicit notation", i.e. which I used in this post's example (i.e. map_async[V, R, T: Awaitable](fn: Maps1[V, R], aval: T[V]) -> T[R]).
As far as I can tell, it doesn't have any of the problems that the explicit variant has.
Additionally, it has the benefit that there is only one obvious to do it (and coincidentally, I'm dutch).

[omer54463]

We can support an explicit syntax similar to the ones you mentioned without contradictions.

1. If we have [X, Y, T: Awaitable], we can use T[X], T[Y], and so on. Let's call this "implicit".
2. If we have [X, T: Awaitable[X]] we can use T, but T[X] makes no sense anymore. Let's call this "explicit".

The signature of the function you gave would then be either:

1. def map_async[V, R, A: Awaitable](fn: Maps1[V, R], aval: A[V]) -> A[R]: ... - implicit, same Awaitable.
2. def map_async[V, R, AV: Awaitable, AR: Awaitable](fn: Maps1[V, R], aval: AV[V]) -> AR[R]: ... - implicit, different Awaitable.
3. def map_async[V, R, AV: Awaitable[V], AR: Awaitable[R]](fn: Maps1[V, R], aval: AV) -> AR: ... - explicit, different Awaitable.

Though I am not sure "explicit" is the right term here.

[jorenham]

@omer54463 Your 2nd and 3rd signature specifications with 4 type parameters are invalid.
To see why, consider the map_async(str, asyncio.Task[int]) example:

• Maps1[V, R] matches str: Any -> str
  • V binds to Any
  • R binds to str
• AV[V] binds to asyncio.Task[V]
  • V binds to int, because and int <: Any
• AR[R] is narrowed to AR[str]
• AR cannout be bound

So a type checker has no way of inferring the type of AR, unless you consider Awaitable to be its default, in which case it will always return an Awaitable[R], which defeats the purpose of HKT in this example.

[smheidrich]

The important points about the status of this feature and how to contribute have scrolled out of GitHub's very limited window of comments visible on page load by now, which makes them hard for newcomers to this issue to find. So here is a summary again:

• @JelleZijlstra has indicated interest in sponsoring a PEP, conditional on a prototype implementation in a major type checker and a well-specified draft PEP.
• Drafting the PEP takes place in @nekitdev's fork of the peps repo. The stub PEP draft so far contains a few examples of the proposed syntax.
• That same repo's GitHub Discussions forum forum has been designated as the place to discuss the PEP (and presumably the prototype implementation?). Some limited further discussions have taken place there.
  • If you want to be notified of new discussion threads, I think you have to set the whole repo as "watched" in GitHub?

Maybe @tek or someone else who is allowed to edit it can put this in the original issue so new arrivals find it quickly?

[JelleZijlstra]

Good point, I'll put this summary in the top post.

[Badg]

• Drafting the PEP takes place in @nekitdev's fork of the peps repo. The stub PEP draft so far contains a few examples of the proposed syntax.

I wanted to post this on the linked PEP draft, but I'm getting a 404. Did it maybe move? (cc: @nekitdev)

---

At any rate, I'm pretty sure I have another use case. I'm currently writing an asset management system that supports the idea of presentation variants, and each presentation variant has a metadata dict. However, the exact format of the metadata dict is determined by the kind of one of the arguments to its constructor. More specifically, I've implemented multiple asset builder classes, which all inherit from a base Builder, and may then themselves be subclassed further. Each of the Builder subclasses define their own required metadata keys, but the PresentationVariantInfo is generic with respect to the actual Builder subclass. Simplifying a lot, it looks something like this:

class StaticNoopBuilderMetadata(TypedDict):
    static_renders: dict[ContentVariantInfo, str]


class StaticNoopBuilder[MD: StaticNoopBuilderMetadata](Builder):

    def build(self, metadata: MD) -> bytes:
        ...


@dataclass
class PresentationVariantInfo[B: Builder]:
    builder: B
    metadata: dict

However, what I really want is something like this:

@dataclass
class PresentationVariantInfo[B: Builder]:
    builder: B
    metadata: B.MD

Where the type of the metadata can reference the kind of the nested generic B.

---

Unnecessary details:

Actually, in my case, I actually need both HKT and an intersection type (cross ref here, though this is a different example I didn't include there). In reality, the AMS supports both a build step (always static for any given asset version, for example, reading a template file into memory) and a render step (actually rendering out the asset, for example, rendering a jinja template). Because both the builder and the renderer specify metadata keys, I really need the intersection of both of their typed dicts. So in that case it would look something like this:

class Builder[MD]:
    ...


class Renderer[MD]:
    ...


class PresentationVariantInfo[B: Builder, R: Renderer]:
    builder: B
    renderer: R
    # The intersection of the MD type argument for both the builder and the
    # renderer
    metadata: B.MD & R.MD

[nekitdev]

Hey! Yeah, sorry, I messed up sync with the upstream so had to reclone. I'll push the draft shortly.
Edit: here is the updated link.

[Badg]

Awesome, thanks!

To be completely honest, theoretical typing discussions are... a bit too abstract for me at times. So I'm not 100% sure that my use case above is actually and example of HKT. But if it is, feel free to use it!

[purepani]

I think libraries like einops would also benefit greatly from this. It would be pretty useful to be able to get shape information both into and out of any sort of array manipulation function.

[finite-state-machine]

I'm not sure if further motivating examples are useful, but here's a simple function, not involved in type checking, that I don't believe can be described today:

# sketch -- not carefully checked

T = TypeVar('T')
C = TypeVar('C', bound='Collection[T]')

def filter_and_count_dups(c: C[T]) -> Tuple[C[T], Counter[T]]:
    '''copy any 'Collection' w/o duplicates, counting what's omitted

    Args:
        c: any collection of elements
    Returns:
        (c_wo_dups, dup_counts), where...
        c_wo_dups: a copy of 'c', with the 2nd and subsequent
            appearances of any given element omitted
        dup_counts: counts removed duplicates
    '''
    seen: Set[T] = set()
    ret_list: List[T] = []
    ret_counter = Counter[T]()
    for elem in c:
        if elem in seen:
            ret_counter[elem] += 1
        else:
            ret_list.append(elem)
            seen.add(elem)

    ret_wo_dups = type(c)(ret_list)
    return (ret_wo_dups, ret_counter)


r1 = filter_and_count_dups((1, 2, 4, 3, 4, 4, 2, 1))
reveal_type(r1) # ≈ Tuple[Tuple[int, ...], Counter[int]]
print(repr(r1)) # ≈ ((1, 2, 4, 3), Counter({4: 2, 2: 1, 1: 1}))

r2 = filter_and_count_dups(list('alphabet'))
reveal_type(r2) # ≈ Tuple[List[str], Counter[str]]
print(repr(r2)) # ≈ (['a', 'l', 'p', 'h', 'b', 'e', 't'], Counter({'a': 1}))

[nerodono]

One more use case, consider the following code:

class Handler[I, O](Protocol):
    def __call__(self, input: I, /) -> O: ...

class Modify(Protocol):
    def modify[O](self, f: Callable[[Self], O], /) -> O: ...

# Mixing styles since idk how to properly express it in 695
M = TypeVar("M", bound="Modify")

class Ext[Inner]:
    inner: Inner

    def modify[O](self: Ext[M], f: Callable[[M], O], /) -> Ext[O]:
        return Ext(f(self.inner))

I can extend Ext, with something like:

class MyExt[Inner](Ext[Inner]):
    def another_method(self) -> MyExt[SomeOtherType]:
        return self.modify(xxx)

However, since Ext.modify is defined to return Ext[Inner], not MyExt[Inner], my type will be erased and I'll lose all extended methods. To fix this, Ext.modify needs to be defined like that:

class Ext[Inner]:
    def modify[O](self: Self[M], f: Callable[[M], O]) -> Self[O]:
        return type(self)(self.inner.modify(f))

I have encountered that limitation when writing syntactic sugar for my library for handlers. Handlers can be combined, and handlers can be specialized, like this:

class Predicate[I](Handler[I, bool], Protocol):
    ...

Here, we specialize Predicate as Handler which returns boolean value, for this specialized version we could add some methods in Ext:

class PredicateExt[P](Ext[P]):
    def and_[I](self: PredicateExt[Predicate[I]], rhs: Predicate[I]) -> PredicateExt[Predicate[I]]:
        return self.modify(lambda lhs: And(lhs, rhs))

... but there's no way to do that without triggering type-checker, unless we had HKTs

[jorenham]

I'm starting to think that by simply making types.GenericAlias generic, we can get HKT "for free".

With this, we could write some HKT function f: (T[int]) -> T[str] with T: Sequence as:

from collections.abc import Sequence
from types import GenericAlias

def f[T: Sequence](x: GenericAlias[T, int], /) -> GenericAlias[T, str]: ...

_{Note that type-checkers might complain about the missing type argument in T: Sequence, which I omitted for the sake of clarity}

---

So to be a little bit more specific, the generic GenericAlias could look something like

class GenericAlias[T, *Ps]:
    @property
    def __origin__(self) -> type[T]: ...
    @property
    def __args__(self) -> tuple[*Ps]: ...
    ...  # etc

_{Note that because a variadic type-parameter like *Ps cannot be covariant (at the time of writing), this might not work out-of-the-box for all HKT use-cases.}

Through the __class_getitem__ method of generic classes, you'd then have e.g. Spam.__class_getitem__(T) -> GenericAlias[Spam, T], which is equivalent to Spam[T].

---

But there's one big problem with this approach:

>>> type(list[str])
<class 'types.GenericAlias'>
>>> class Spam[T]: ...
... 
>>> type(Spam[str])
<class 'typing._GenericAlias'>

There are two generic aliases!
... but this is probably not the right place to be discussing this, so I'll keep my rant short :)