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 ContainerN
>>> from typing import TypeVar

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

>>> def to_str(container: Kind1[T, int]) -> Kind1[T, str]:
...     return container.map(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(container: Kind1[T, int]) -> Kind1[T, str]:
...     return container.map(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 ContainerN, 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!

Further reading

• Higher Kinded Types in Python

FAQ

Which types you can use with KindN?

The first position in all KindN types can be occupied by either Instance type or TypeVar with bound=.

Let’s see an example:

>>> from typing import TypeVar
>>> from returns.primitives.hkt import KindN, kinded
>>> from returns.interfaces.mappable import MappableN

>>> _FirstType = TypeVar('_FirstType')
>>> _SecondType = TypeVar('_SecondType')
>>> _ThirdType = TypeVar('_ThirdType')
>>> _MappableKind = TypeVar('_MappableKind', bound=MappableN)

>>> @kinded
... def works_with_interface(
...     container: KindN[_MappableKind, _FirstType, _SecondType, _ThirdType],
... ) -> KindN[_MappableKind, str, _SecondType, _ThirdType]:
...     return container.map(str)

This version of works_with_interface will work with any subtype of MappableN. Because we use _MappableKind in its definition. And _MappableKind is a TypeVar bound to MappableN. Arguments of non MappableN subtypes will be rejected by a type-checker:

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

>>> assert works_with_interface(Maybe.from_value(1)) == Maybe.from_value('1')
>>> assert works_with_interface(IO.from_value(1)) == IO.from_value('1')
>>> assert works_with_interface(Success(1)) == Success('1')

In contrast, we can work directly with some specific type, let’s say Maybe container:

>>> from returns.maybe import Maybe

>>> @kinded
... def works_with_maybe(
...     container: KindN[Maybe, _FirstType, _SecondType, _ThirdType],
... ) -> KindN[Maybe, str, _SecondType, _ThirdType]:
...     return container.map(str)

>>> assert works_with_maybe(Maybe.from_value(1)) == Maybe.from_value('1')

Function works_with_maybe will work correctly with Maybe instance. Other types will be rejected.

So, choose wisely which mechanism you need.

API Reference

        classDiagram
  Generic <|-- KindN
  KindN <|-- SupportsKindN
  Protocol <|-- Kinded
    

class KindN

Bases: Generic[_InstanceType_co, Unpack[_TypeVars]]

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_co of KindN to be Instance type or TypeVarType with bound=....

See also

• https://arrow-kt.io/docs/0.10/patterns/glossary/#higher-kinds

• https://github.com/gcanti/fp-ts/blob/master/docs/guides/HKT.md

• https://bow-swift.io/docs/fp-concepts/higher-kinded-types

• https://github.com/pelotom/hkts

Kind1

Type alias for kinds with one type argument.

alias of KindN[_InstanceType_co, _TypeArgType1_co, Any, Any]

Kind2

Type alias for kinds with two type arguments.

alias of KindN[_InstanceType_co, _TypeArgType1_co, _TypeArgType2_co, Any]

Kind3

Type alias for kinds with three type arguments.

alias of KindN[_InstanceType_co, _TypeArgType1_co, _TypeArgType2_co, _TypeArgType3_co]

class SupportsKindN

Bases: KindN[_InstanceType_co, Unpack[_TypeVars]]

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 typechecking phase.

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

SupportsKind1

Type alias used for inheritance with one type argument.

alias of SupportsKindN[_InstanceType_co, _TypeArgType1_co, Never, Never]

SupportsKind2

Type alias used for inheritance with two type arguments.

alias of SupportsKindN[_InstanceType_co, _TypeArgType1_co, _TypeArgType2_co, Never]

SupportsKind3

Type alias used for inheritance with three type arguments.

alias of SupportsKindN[_InstanceType_co, _TypeArgType1_co, _TypeArgType2_co, _TypeArgType3_co]

dekind(kind)

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

Should be used when you are left with accidental 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[TypeVar(_InstanceType_co, covariant=True), TypeVar(_TypeArgType1_co, covariant=True), TypeVar(_TypeArgType2_co, covariant=True), TypeVar(_TypeArgType3_co, covariant=True)])

Return type:

TypeVar(_InstanceType_co, covariant=True)

class Kinded(*args, **kwargs)

Bases: Protocol[_FunctionDefType_co]

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)

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 (TypeVar(_FunctionType, bound= Callable))

Return type:

Kinded[TypeVar(_FunctionType, bound= Callable)]