Proposal + Feedback Wanted: `typing.RelatedTypes`, `typing.Relation`; enables type-hinting variadic `compose`, etc

Typing
1

Motivation

In functional programming land, there’s a popular building block that’s a real struggle to type-hint, named compose.

As a quick summary example:

  • compose(f, g) is roughly the same as lambda *args, **kwargs: f(g(*args, **kwargs)),
  • compose(f, g, h) is roughly the same as lambda *args, **kwargs: f(g(h(*args, **kwargs))),
  • and so on.

A general-purpose, variadic compose is worth having good type-hinting support for it. I don’t have time to write a defense of that claim right now, so I’ll just gesture at multiple repos where different developers have independently asked for a way to add type hints to compose over the years:

  1. in the popular toolz library
  2. in MyPy
  3. there are two examples instances in my compose package (I’d link, but An error occurred: Sorry, new users can only put 2 links in a post.)

As far as I know, the best we’ve been able to figure out so far is writing out a typing.overload for each arity we wish to support. (And if your compose implementation supports async, you need at least twice as many type hint overloads.)

Idea

  1. The generic need here is a way to specify a relationship between types in a variadic tuple of types: T1 is somehow related to T2, T2 is related to T3, and so on.

  2. I think something inspired by “base case and induction step” approaches of recursive functions and inductive proofs might work really well here.

  3. So as an initial building block, I imagine typing.Relation[T1, T2], where T1 and T2 are type hints which contain one or more of the same typevars.

  4. Then, I imagine a typing.RelatedTypes[*types_or_relations], which represents multiple types (similar to typing.TypeVarTuple), and takes one or more type hints and relations.

Example

The type hint for compose (two or more arguments and no async support for simplicity) can now be expressed like this:

P = ParamSpec('P')
R = TypeVar('R')
R1 = TypeVar('R1')
R2 = TypeVar('R2')

@override
def compose(*functions: RelatedTypes[Callable[[Any], R], Relation[Callable[[R1], R2], Callable[..., R1]], Callable[P, R1]) -> Callable[P, R]:
    ...

Details

I would love to hear thoughts from implementers of type checkers on this! Did I miss some reason why this is infeasible/horrible/inefficient to implement?

  1. If I didn’t miss anything, a type checker could match RelatedTypes to values (in arguments, but maybe also in lists, etc) in one left-to-right pass (no backtracking, O(number_of_values) time and O(1) space).

  2. Types in RelatedTypes[...] match exactly one value.

  3. Relations in RelatedTypes[...] match two or more values. (A separate override or union with RelatedTypes can cover the one/zero value cases. This avoids some problems - consider how tricky the spec would be if we had to define a sensible thing for the RelatedTypes of compose to do when called with just one argument!)

  4. Relations overlap for one value on each side if there’s another type or relation specified on that side within the RelatedTypes.

In other words, given a signature like def f(*args: RelatedTypes[T0, Relation[T1, T2], T3]): ...:

  • a call like f(foo, qux), foo must pass for both T0 and T1, and qux must pass T2 and T3, and

  • a call like f(foo, bar, qux), foo must pass for both T0 and T1, bar must pass both T1 and T2, and qux must pass T2 and T3.

2 Likes
2

As a user of typing, these feels too complicated for little gain. Writing a generator script for like, 10 argument forms isn’t that hard, it’s cleared to the user of the API (since this will be exposed in IDE tooltips) and it’s easier to understand (although potentially hard to modify) for maintainers.

Can you list other potential usecases of this? For example, I don’t see an obvious way to type zip with this.

If we get such complicated typing features, I would much prefer a universal macro system of some kind that executes a subset of python to generate the type hints for the corresponding function call.