Improve support for infinite and recursive types
There seem to be two characteristics (among several) we can use to categorise types:
- By their cardinality:
- finite
- infinite
- By their “referential-ness”:
- Self-referential
- Non self-referential.
I would like to propose some support for correctly typing these objects, and possibly also inspecting/querying these properties on instantiated objects.
Most of what follows naturally applies to iterables and containers, so I’ll limit my discussion to these for convenience.
To ease discussion, let’s suppose the following helper functions exist:
def is_finite(something) -> bool: ...
def is_self_referential(something) -> bool: ...
Some illustrative examples
- A finite list
x = [1,2,3]
assert is_finite(x)
- An infinite iterable, such as the following generator
def all_integers() -> Generator[int]:
i = 1
while (i := i + 1):
yield i
x = all_integers()
assert not is_finite(x)
Note: We would need to determine this without iterating through the container or relying on a maximum recursion exception being raised.
- A self referential list
x = x[0] = [None] # x = [[...]]
assert is_self_referential(x)
- A non self referential list
x = [1, 2, 3]
assert not is_self_referential(x)
Some motivating examples
These sort of structures do arise naturally. Consider trying to type hint something a bit like a JSON
type JSONLike = dict[str: int | JSONLike]
Python (and tools like MyPy) support recursive types (cf. link and link).
Similarly, there is support in Python for nicely handling self referential data structures, especially in the repr method (link).
Additionally, anyone who has written a flatten function (example from NumPy) is at risk of encountering a self referential list.
Possible solutions
Some form of annotation or a predicate could be ideal for assessing the cardinality:
from typing import Finite, Infinite, Annotated
# Using Finite as an annotation
type Finite[JSONLike] = dict[str: int | Finite[JSONLike]]
def all_integers() -> Infinite[Generator, int]: ...
# Using Finite as a predicate
type Annotated[JSONLike, Finite] = dict[str: int | Annotated[JSONLike, Finite]]
def all_integers() -> Annotated[Generator[int], Infinite]: ...
# Using is_finite as a predicate
from annotated_types import Predicate
JsonLike = Annotated[JSONLike, Predicate(is_finite)]
I could imagine very similar functionality for the self referential types.
Not all infinite objects are self referential, and hence the two are distinct. Consider for example:
def integer_sequences() -> Generator[Generator[int]]:
def all_integers(i) -> Generator[int]:
k = i
while (k := k + 1):
yield k
yield (all_integers(i=j) for j in all_integers(1))
all_integer_sequences = integer_sequences()
# all_integer_sequences -> [[1,2,3,...], [2,3,4,...], [3,4,5,...], ...]
In this example, all_integer_sequences is infinite, but it is not self referential.
Similarly, we can construct a self referential object which is finite, consider
"""
linked_list =
a -> b -> c
^ |
| V
e <- d
"""
linked_list: SelfReferential[Finite[LinkedList]] = ...
linked_list: Annotated[LinkedList, Finite, SelfReferential] = ...
assert len(linked_list) == 5
assert is_finite(linked_list)
assert is_self_referential(linked_list)
Benefits of possible solutions
As mentioned with the JSON example, this allows us to represent the types “more correctly” and closer to the intention of the developer without having to worry about all the corner cases of Python.
Likewise, it can enable us to detect dead code, infinite loops, etc.
It enables us to detect and raise proper exceptions. With the flatten example, if we had access to the is_finite method, we could easily raise some appropriate exception to the caller rather than getting caught in an infinite recursion.
Which is best?
Based on the examples given, I think there is utility in both the type annotations and also the run-time methods.
I appreciate there are lots of corner cases, especially surrounding efficient runtime checking of these properties, or statically analysing the consequences of some of these properties, but nonetheless I think there is utility is the added expressiveness this offers for expressing the intent and the desired constraints on the types.