Hi everyone, I would love to share something I have been working on for the last year! I have implemented an emulation of Higher Kinded Types for mypy. Here I would love to describe how it works and (hopefully!) receive your feedback. Some context before we start: 1. What are Higher Kinded Types (or HKT)? It is basically a concept of "generics of generics". Here's the simplest example: ```python def build_new_object(typ: Type[T], value: V) -> T[V]: ... # won't work, because HKT is not natively supported ``` 2. What is "emulated" HKT support? There's a very popular approach to model HKT not as `T[V]` but as a `Kind[T, V]`. Original whitepaper: https://www.cl.cam.ac.uk/~jdy22/papers/lightweight-higher-kinded-polymorphis... 3. Why would anyone need this? That's a good question. HKT gives a lot of power. It is widely used with functional programming. You can find a full example here: https://sobolevn.me/2020/06/how-async-should-have-been With HKT one can rewrite `@overload`ed function for both async and sync use-cases as: ```python @kinded def fetch_resource_size( client_get: Callable[[str], Kind2[_IOBased, httpx.Response, Exception]], url: str, ) -> Kind2[_IOBased, int, Exception]: ... # implementation will be slightly different ``` 4. Is it ready for the production use? No! It is just an early prototype. There are a lot of things to polish. There are some known hacks and limitations right now (that can possibly stay forever). Now, let's dig into how it works! First of all, there's a new primitive to represent `Kind`, it is called `KindN` and has 3 (at the moment, it might change in the future) aliases `Kind1`, `Kind2`, `Kind3`. Why? Kind1 represents types with one type variable, like `List[X]` Kind2 represents types with two type variables, like `Result[Value, Error]` Kind3 represents types with three type variables, like `Generator[X, A, B]` KindN is a base type for all of them, it can possibly have any number of type variables. Source code: https://github.com/dry-python/returns/blob/master/returns/primitives/hkt.py Now, let's say I want to build a `map_` function to map a pure function over a `Functor` instance. How should I do that? I need to: 1. Implement `Mappable` (or `Functor`) interface 2. Implement some data type that implements your `Mappable` interface 3. Implement some hacks, that I've mentioned earlier, to make sure that you will be able to work with `KindN` values 4. Implement the `map_` function itself Let's start with the interface: ```python _MappableType = TypeVar('_MappableType', bound='MappableN') class MappableN(Generic[_FirstType, _SecondType, _ThirdType]): """ Allows to chain wrapped values in containers with regular functions. Behaves like a functor. See also: https://en.wikipedia.org/wiki/Functor """ @abstractmethod def map( # noqa: WPS125 self: _MappableType, function: Callable[[_FirstType], _UpdatedType], ) -> KindN[_MappableType, _UpdatedType, _SecondType, _ThirdType]: """Allows to run a pure function over a container.""" #: Type alias for kinds with one type argument. Mappable1 = MappableN[_FirstType, NoReturn, NoReturn] ``` Source: https://github.com/dry-python/returns/blob/master/returns/interfaces/mappabl... Tests: https://github.com/dry-python/returns/blob/master/typesafety/test_interfaces... This is pretty straight-forward. Some things to notice: - `_MappableType` must be bound to `MappableN`, we use this type to annotate `self`, this is required - It returns modified `KindN` instance, we work with the first type argument here - method is abstract, because we would need an actual implementation from the child types Now, let's write some real data type to satisfy this contract. I will just use the code from here: https://github.com/dry-python/returns/blob/01cf56e023e81f165f4a2b5c2c81a415a... Some things to notice: - We use `Kind1` as a supertype for our own data type, it means that we only have one type argument, this is required. Notice that we pass `'MyClass'` forward reference into `Kind1` - mypy makes sure that `map` method defintion exists and is correct, any violations of the type contract will make mypy to raise errors Now, let's try to implement the `map_` function for any `Mappable` and any pure function. Source: https://github.com/dry-python/returns/blob/master/returns/methods/map.py Tests: https://github.com/dry-python/returns/blob/master/typesafety/test_methods/te... That's how it will look like: ```python from returns.primitives.hkt import KindN, kinded _MappableKind = TypeVar('_MappableKind', bound=MappableN) @kinded def map_( container: KindN[_MappableKind, _FirstType, _SecondType, _ThirdType], function: Callable[[_FirstType], _UpdatedType], ) -> KindN[_MappableKind, _UpdatedType, _SecondType, _ThirdType]: ... ``` Things to note: - We need to mark this function as `@kinded`, because we need to tweak its return type with a custom plugin. We don't want `KindN[]` instances, we need real types! - We need to bound `_MappableKind` to our `MappableN` interface to make sure we will have an access to its methods (`.map` in our case) The only thing left is the implementation. The obvious way: `return container.map(function)` won't work. Because: 1. `KindN` does not have `.map` method, we need to somehow get to `MappableN` instead 2. It will have wrong return type: `KindN[MappableN, _UpdatedType, _SecondType, _ThirdType]` while we need `KindN[_MappableKind, _UpdatedType, _SecondType, _ThirdType]` (the difference is in the first type argument). So, we need to use the dirty hacks! ```python from returns.primitives.hkt import debound # ... new_instance, rebound = debound(container) return rebound(new_instance.map(function)) ``` What does it do? 1. It returns a proper `new_instance` with `MappableN` type 2. It also returns a callback to coerce the return type to the correct one The only thing left is to test it! Here are the tests: https://github.com/dry-python/returns/blob/master/typesafety/test_methods/te... They pass! To sum things up: 1. Current state of HKTs in Python allows defining complex type contracts 2. We are able to write `@kinded` methods and functions that do return the correct types in the end 3. We have some limitations: like max 3 type parameters at the moment 4. There are some minor API tweak when working with kinds: debound, dekind, Kinded[], @kinded 5. There are also some blockers from the mypy side to improve some API parts, like: https://github.com/python/mypy/issues/9001 That's it! I would love to answer any questions you have. And I hope to hear your feedback on my work. Best regards, Nikita Sobolev https://github.com/sobolevn