Higher Kinded Types

Higher Kinded Types is a new concept for Python developers. But, it is totally not new in general!

So, let’s start with the detailed explanation: what Higher Kinded Types are?

Regular types

We can start with the very basic example. Let’s say we have a function that transforms type A into a type B. These types A and B can be some specific ones, for example:

>>> def from_a_to_b(arg: int) -> str:
...      return str(arg)

>>> assert from_a_to_b(1) == '1'

That’s what we already know and use. Let’s scale things up!

Generics

The next thing we can do with types is to write generic types. What are generic types? Basically, they are some types that contain other types inside. Like List[int] is a list of integers: [1, 2, 3]. We know that List[int] has a shape of a list and contents of int.

We can also write functions that work with generics:

>>> from typing import List

>>> def all_to_str(arg: List[int]) -> List[str]:
...     return [str(item) for item in arg]

>>> assert all_to_str([1, 2]) == ['1', '2']

There’s one more thing about generics we want to notice at this point. Different generics do have different numbers of type arguments:

  • List has a single type argument: List[Value] or Maybe[Value]

  • Dict has two type arguments: Dict[Key, Value] or Result[Value, Error]

  • Generator has three type arguments: Generator[Yield, Send, Return] or RequiresContextResult[Value, Error, Env]

That’s what we call a kind. So, List and Maybe have a kind of 1, Dict and Result have kind of 2, Generator and RequiresContextResult have a kind of 3.

So, let’s go one level further.

Operations on generics

Let’s say you have a function that copies all values of a passed argument. We can define this function as:

>>> from typing import TypeVar
>>> ValueType = TypeVar('ValueType')

>>> def copy(arg: ValueType) -> ValueType:
...    ...

This function can work with any type. It receives something and then returns the same value back. That’s the whole point of copying!

But, there are different functions, that do different things with types. For example, we can write a function that converts a value inside any Container1 (a base class for all our containers) from int to str:

We can also write functions that work with generics:

>>> from returns.interfaces.container import Container1

>>> def to_str(container: Container1[int]) -> Container1[str]:
...     return container.map(str)

And here’s how it can be used:

>>> from returns.maybe import Maybe
>>> from returns.io import IO

>>> assert to_str(Maybe.from_value(1)) == Maybe.from_value('1')
>>> assert to_str(IO.from_value(1)) == IO.from_value('1')

It works just fine! But! It has a very important thing inside. All calls to to_str will return Container1 type, not something specific:

reveal_type(to_str(Maybe.from_value(1)))  # Container1[str]
reveal_type(to_str(IO.from_value(1)))     # Container1[str]

But, we know that this is not true. When we pass a Maybe in - we get the Maybe back. When we pass a IO in - we get the IO back.

How can we fix this problem? With @overload!

>>> from typing import overload
>>> from returns.maybe import Maybe
>>> from returns.io import IO

>>> @overload
... def to_str(arg: Maybe[int]) -> Maybe[str]:
...    ...

>>> @overload
... def to_str(arg: IO[int]) -> IO[str]:
...    ...

We kinda fixed it! Now, our calls will reveal the correct types for these three examples:

reveal_type(to_str(Maybe.from_value(1)))  # Maybe[str]
reveal_type(to_str(IO.from_value(1)))     # IO[str]

But, there’s an important limitation with this solution: no other types are allowed in this function anymore. So, you will try to use it with any other type, it won’t be possible.

Current limitations

To overcome current @overload decorators limitations, we can imagine a syntax like this:

from typing import TypeVar
from returns.interfaces.container import Container1

T = TypeVar('T', bound=Container1)

def all_to_str(arg: T[int]) -> T[str]:
    ...

Sadly, this does not work. Because TypeVar cannot be used with []. We have to find some other way.

Higher Kinded Types

So, that’s where returns saves the day!

Note

Technical note: this feature requires mypy plugin.

The main idea is that we can rewrite T[int] as Kind1[T, int]. Let’s see how it works:

>>> from returns.primitives.hkt import Kind1
>>> from returns.interfaces.container import Container1
>>> from typing import TypeVar

>>> T = TypeVar('T', bound=Container1)

>>> def to_str(arg: Kind1[T, int]) -> Kind1[T, str]:
...   ...

Now, this will work almost correctly! Why almost? Because the revealed type will be Kind1.

reveal_type(to_str(Maybe.from_value(1)))  # Kind1[Maybe, str]
reveal_type(to_str(IO.from_value(1)))     # Kind1[IO, str]

That’s not something we want. We don’t need Kind1, we need real Maybe or IO values.

The final solution is to decorate to_str with @kinded:

>>> from returns.primitives.hkt import kinded

>>> @kinded
... def to_str(arg: Kind1[T, int]) -> Kind1[T, str]:
...   ...

Now, it will be fully working:

reveal_type(to_str(Maybe.from_value(1)))  # Maybe[str]
reveal_type(to_str(IO.from_value(1)))     # IO[str]

And the thing about this approach is that it will be:

  1. Fully type-safe. It works with correct interface Container1, returns the correct type, has correct type transformation

  2. Is opened for further extension and even custom types

Kinds

As it was said Maybe[int], Result[str, int], and RequiresContextResult[str, int, bool] are different in terms of a number of type arguments. We support different kinds:

  • Kind1[Maybe, int] is similar to Maybe[int]

  • Kind2[Result, str, int] is similar to Result[str, int]

  • Kind3[RequiresContextResult, str, int, bool] is similar to RequiresContextResult[str, int, bool]

You can use any of them freely.

Later you will learn how to create your own types that support kinds!

API Reference

class KindN(*args, **kwds)[source]

Bases: typing.Generic

Emulation support for Higher Kinded Types.

Consider KindN to be an alias of Generic type. But with some extra goodies.

KindN is the top-most type for other Kind types like Kind1, Kind2, Kind3, etc.

The only difference between them is how many type arguments they can hold. Kind1 can hold just two type arguments: Kind1[IO, int] which is almost equals to IO[int]. Kind2 can hold just two type arguments: Kind2[IOResult, int, str] which is almost equals to IOResult[int, str]. And so on.

The idea behind KindN is that one cannot write this code:

from typing import TypeVar

T = TypeVar('T')
V = TypeVar('V')

def impossible(generic: T, value: V) -> T[V]:
    return generic(value)

But, with KindN this becomes possible in a form of Kind1[T, V].

Note

To make sure it works correctly, your type has to be a subtype of KindN.

We use a custom mypy plugin to make sure types are correct. Otherwise, it is currently impossible to properly type this.

We use “emulated Higher Kinded Types” concept. Read the whitepaper: https://bit.ly/2ABACx2

KindN does not exist in runtime. It is used just for typing. There are (and must be) no instances of this type directly.

Implementation details

We didn’t use ABCMeta to disallow its creation, because we don’t want to have a possible metaclass conflict with other metaclasses. Current API allows you to mix KindN anywhere.

We allow _InstanceType of KindN to be Instance type or TypeVarType with bound=....

Kind1

Type alias for kinds with one type argument.

alias of returns.primitives.hkt.KindN[_InstanceType, _TypeArgType1, Any, Any]

Kind2

Type alias for kinds with two type arguments.

alias of returns.primitives.hkt.KindN[_InstanceType, _TypeArgType1, _TypeArgType2, Any]

Kind3

Type alias for kinds with three type arguments.

alias of returns.primitives.hkt.KindN[_InstanceType, _TypeArgType1, _TypeArgType2, _TypeArgType3]

class SupportsKindN(*args, **kwds)[source]

Bases: returns.primitives.hkt.KindN

Base class for your containers.

Notice, that we use KindN / Kind1 to annotate values, but we use SupportsKindN / SupportsKind1 to inherit from.

Implementation details

The only thing this class does is: making sure that the resulting classes won’t have __getattr__ available during the typecheking phase.

Needless to say, that __getattr__ during runtime - never exists at all.

SupportsKind1

Type alias used for inheritance with one type argument.

alias of returns.primitives.hkt.SupportsKindN[_InstanceType, _TypeArgType1, NoReturn, NoReturn]

SupportsKind2

Type alias used for inheritance with two type arguments.

alias of returns.primitives.hkt.SupportsKindN[_InstanceType, _TypeArgType1, _TypeArgType2, NoReturn]

SupportsKind3

Type alias used for inheritance with three type arguments.

alias of returns.primitives.hkt.SupportsKindN[_InstanceType, _TypeArgType1, _TypeArgType2, _TypeArgType3]

dekind(kind)[source]

Turns Kind1[IO, int] type into real IO[int] type.

Should be used when you are left with accidential KindN instance when you really want to have the real type.

Works with type arguments of any length.

We use a custom mypy plugin to make sure types are correct. Otherwise, it is currently impossible to properly type this.

In runtime it just returns the passed argument, nothing really happens:

>>> from returns.io import IO
>>> from returns.primitives.hkt import Kind1

>>> container: Kind1[IO, int] = IO(1)
>>> assert dekind(container) is container

However, please, do not use this function unless you know exactly what you are doing and why do you need it.

Parameters

kind (KindN[+_InstanceType, +_TypeArgType1, +_TypeArgType2, +_TypeArgType3]) –

Return type

+_InstanceType

class Kinded(*args, **kwds)[source]

Bases: typing_extensions.Protocol

Protocol that tracks kinded functions calls.

We use a custom mypy plugin to make sure types are correct. Otherwise, it is currently impossible to properly type this.

kinded(function)[source]

Decorator to be used when you want to dekind the function’s return type.

Does nothing in runtime, just returns its argument.

We use a custom mypy plugin to make sure types are correct. Otherwise, it is currently impossible to properly type this.

Here’s an example of how it should be used:

>>> from typing import TypeVar
>>> from returns.primitives.hkt import KindN, kinded
>>> from returns.interfaces.bindable import BindableN

>>> _Binds = TypeVar('_Binds', bound=BindableN)  # just an example
>>> _Type1 = TypeVar('_Type1')
>>> _Type2 = TypeVar('_Type2')
>>> _Type3 = TypeVar('_Type3')

>>> @kinded
... def bindable_identity(
...    container: KindN[_Binds, _Type1, _Type2, _Type3],
... ) -> KindN[_Binds, _Type1, _Type2, _Type3]:
...     return container  # just do nothing

As you can see, here we annotate our return type as -> KindN[_Binds, _Type1, _Type2, _Type3], it would be true without @kinded decorator.

But, @kinded decorator dekinds the return type and infers the real type behind it:

>>> from returns.io import IO, IOResult

>>> assert bindable_identity(IO(1)) == IO(1)
>>> # => Revealed type: 'IO[int]'

>>> iores: IOResult[int, str] = IOResult.from_value(1)
>>> assert bindable_identity(iores) == iores
>>> # => Revealed type: 'IOResult[int, str]'

The difference is very clear in methods modules, like:

  • Raw returns.methods.bind.internal_bind() that returns KindN instance

  • User-facing returns.methods.bind.bind() that returns the container type

You must use this decorator for your own kinded functions as well.

Parameters

function (~_FunctionType) –

Return type

Kinded[~_FunctionType]