Generics over container types?

Python Help
1

Given that I have a function:

def process[T](collection: Sequence[T]) -> Sequence[T]

I want to express that, when the input is of type list[T], the return value will be list[T], when the input is of type tuple[T, ...], the return value will be tuple[T, ...]. Its means that the container type (list, tuple, Deque) of the return value is in accordance with the input.

How should I make type annotation?

2

That’s what upper bounds in a TypeVar are for, in your simple example, you should be able to express it like this:

def process[T: Sequence](collection: T) -> T: ...
3

Thank you, how to annotate the element type also, like Sequence[U]? Is this valid:

def process[T: Sequence[U]](collection: T) -> T: ...
4

No, this requires higher kinded types, which are not supported yet.

5

Technically speaking this isn’t HKT, but rather a generic type-parameter bound.

Also note that in this example U only appears once, so there is no need for it. So even if Python would support generic type-parameter bounds or HKT, then the above would be equivalent to:

def process[T: Sequence[object]](collection: T) -> T: ...

So this already works :slight_smile:

1 Like
6

Hi, I stumbled into a very similar usecase, and I do require knowing the element in a container. Here’s the example:

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]

I opened an issue in mypy for generic upper bounds: Support generic upper bounds · Issue #20293 · python/mypy · GitHub . Would be great to discuss them here :slight_smile:

Seems to me full HKT isn’t required for generic upper bounds to be possible/useful. Here’s my thinking:

  • If the generic upper bound is in the type parameter list, with the inner TypeVar also in the type parameter list, then all the types are concrete - we are just binding identifiers to different parts of the overall type.
  • So if all the TypeVars and upper bounds are “self contained” in this way, it seems possible to allow generic upper bounds.

How would one go about proposing this and/or proving it out?

1 Like