python
Support generic upper bounds
Feature
Allow generic upper bounds such as:
class ClassA[T, S: Sequence[T]]: ...
Pitch
PEP 695 has an example that currently doesn't work, and alludes to a future extension to the typesystem that eliminates the limitation:
# The following generates no compiler error, but a type checker
# should generate an error because an upper bound type must be concrete,
# and ``Sequence[S]`` is generic. Future extensions to the type system may
# eliminate this limitation.
class ClassA[S, T: Sequence[S]]: ...
I ran into a usecase for this that I have no way of expressing with the current generics limitations, and generic upper bounds would solve it. I will provide a simpler version of it here so it's easier to discuss.
from typing import Callable, Iterable, Sequence
type CostFunction[T] = Callable[[T], float]
# Sequence[T] gives an error, because T is not concrete
def get_lowest_cost_sequence[T, S: Sequence[T]](
seqs: Iterable[S], item_cost: CostFunction[T]
) -> S:
def seq_cost(seq: S) -> float:
return sum(item_cost(t) for t in seq)
return sorted(seqs, key=seq_cost)[0]
In the example, we are working with sequences, and a cost function for each item in the sequences. The crux is that the function must return the same type as the original sequences. In other words this is an incorrect type signature:
# Return type Sequence[T] is looser, because it does not mean whatever is
# returned will be _the same type_ as what is passed in. Any users of this
# function would have to cast the result for it to expose the same functionality
# as what was in `seqs`.
def get_lowest_cost_sequence[T](
seqs: Iterable[Sequence[T]], item_cost: CostFunction[T]
) -> Sequence[T]:
...
I'm afraid this should go through PEP and typing spec first. This functionality has been requested several times, but type checkers should agree on it at least to some extent, so some prior coordination is necessary. Making this a mypy extension could cost very painful maintenance transitions later when this feature finally makes it to the core language.
More search keywords: HKT, higher-kinded types
I'm afraid this should go through PEP and typing spec first. This functionality has been requested several times, but type checkers should agree on it at least to some extent, so some prior coordination is necessary. Making this a mypy extension could cost very painful maintenance transitions later when this feature finally makes it to the core language.
More search keywords: HKT, higher-kinded types
Makes sense regarding PEP - what's the best way to propose this or contribute to any existing PEP discussions?
Btw, I don't think this requires higher-kinded types necessarily. Correct me if I am wrong. Higher-kinded types means that something can be parametrized on a "type constructor", such as some generic class like list that satisfies Sequence in this case. However, in the narrow case I've describe above, there is no need for that. In the end, all I care about are concrete types: The concrete type S, and also T, once S is inferred as Sequence[T]. I believe all of the inference is already possible, there just needs to be a way to refer to the final concrete type.
With some made-up syntax, where I can bind a type variable to some other type:
# Sequence[T] is inferred as usual, just refer to that type via `@S`
def get_lowest_cost_sequence[T, S](
seqs: Iterable[Sequence[T]@S], item_cost: CostFunction[T]
) -> S:
Obviously I'm not advocating for more syntax, just trying to demonstrate the difference with higher-kinded types.
Yes, you're right - your use case is conceptually easier. HKTs would be a solution to your problem (T = TypeVar("T"); S = TypeVar("S", bound="Sequence"); def fn(seqs: Iterable[S[T]], cost: Func[T]) -> S[T]), but they would be helpful in many other use cases as well.
I'm not sure if our inference infrastructure can already support this (and would rather guess "no"), but this is likely easier to implement than proper HKTs.
what's the best way to propose this or contribute to any existing PEP discussions
I'd suggest starting from Discourse (formerly a typing-sig mailing list, now at https://discuss.python.org/c/typing/32 - try to search there). Probably this idea was discussed there before, then you can join the discussion; otherwise this question is definitely worth a new topic. Drafting a PEP would be too cumbersome without an extended discussion before
Thanks, I referenced this discussion in an existing thread on the python typing Discourse here: https://discuss.python.org/t/generics-over-container-types/94944/6
