# Pythonで高カインド型を表現できない理由と回避策

## 高カインド型とは

高カインド型（higher-kinded type）とは、`list[int]`の`int`だけでなく、`list`に当たるコンテナの種類も型変数にするための概念である。
要素に関数を適用し、戻り値も元のコンテナの種類のままになる`fmap`のような関数の型を、1つのシグネチャで表現するために必要になる。
Pythonの型ヒントには高カインド型の構文がなく、型変数に型引数を指定すると、型チェッカーのmypyとpyrightの両方がエラーにする。

- 高カインド型がないと`list`と自作のコンテナに対応する`fmap`の型を、1つのシグネチャでは正確に表現できない
  - コンテナごとに別のシグネチャが必要になる
  - Protocolを経由すると、戻り値の型が元のコンテナではなくProtocolの型になる
- 型変数`F`に対する`F[A]`は、mypyとpyrightのどちらでもエラーで、注釈を評価すると実行時も`TypeError`になる
  - Pythonの型変数は`list`のように型引数が必要なものの代わりにならない
  - Python 3.12の型パラメータの構文でも同じである
- この記事で比較する回避策は、対応するコンテナを列挙する`@overload`、コンテナ側のメソッド、returnsライブラリの`Kind`の3つである
  - `@overload`は列挙していないコンテナを引数にできない
  - returnsの`Kind`はmypyのプラグインが前提で、pyrightでは要素の型が`Any`になる

## 前提となるジェネリクスの概念

### 型コンストラクタ

型コンストラクタは型引数の指定で型を生成するものである（`list`、`set`、`dict`など）。
以降の説明では要素の型を指定する前の`list`と、指定した後の`list[int]`を区別する。
`T = TypeVar("T")`の`T`の値は`int`や`list[int]`だが、`T[int]`のように後から型引数を指定する対象にはならない。

### kind

kindは型の種類で、型引数の個数と種類の組み合わせで区別される。
`int`や`list[int]`のkindは`*`、型引数を1つ必要とする`list`のkindは`* -> *`と表記する。
この記事の対象はkindが`* -> *`の型コンストラクタが型変数になる場合である。
[TypeScriptとHigher Kinded Type](https://kdot.co.jp/kdotdev/typescript-higher-kinded-type) では、`* -> *`より上の段階のkindもこの記法で説明している。

## コンテナごとに別のシグネチャが必要になる

コード例の`Box`は説明用に定義したクラスで、値を1つ保持する。
この節の`Box`は空の状態（`None`）も保持できる。
`class Box[A]`や`def fmap[A, B]`の構文を使用する例は、Python 3.12以降で動作する。
`list`と`Box`の要素に関数を適用する関数は、次のように型ごとに定義することになる。

```python
from collections.abc import Callable
from dataclasses import dataclass
from typing import Generic, TypeVar

A = TypeVar("A")
B = TypeVar("B")

@dataclass
class Box(Generic[A]):
    value: A | None

def list_map(f: Callable[[A], B], xs: list[A]) -> list[B]:
    return [f(x) for x in xs]

def box_map(f: Callable[[A], B], box: Box[A]) -> Box[B]:
    return Box(None if box.value is None else f(box.value))
```

`list_map`と`box_map`は、コンテナの引数と戻り値の型が、それぞれ`list`と`Box`で異なる。
コンテナの種類を型変数`F`にできれば、次の1つのシグネチャで両方を表現できる。

```python
F = TypeVar("F")

def fmap(f: Callable[[A], B], fa: F[A]) -> F[B]:
    raise NotImplementedError
# mypy
# error: Type variable "F" used with arguments  [valid-type]
# pyright
# error: TypeVar "type[F@fmap]" is not subscriptable (reportGeneralTypeIssues)
```

この`fmap`のように、要素を変換してもコンテナの種類を維持する操作に対応したコンテナを、HaskellなどではFunctorと呼ぶ。

## 型変数に型引数を指定できない理由

型変数`F`はkindが`*`の型の代わりになる変数なので、`F[A]`のように型引数を指定する対象にならない。
mypyは`valid-type`、pyrightは`reportGeneralTypeIssues`のエラーにする。
Pythonの型システムには、型変数のkindを`* -> *`と宣言する構文がない。

実行時も注釈を評価した時点で`TypeError: 'typing.TypeVar' object is not subscriptable`になる。
上の`fmap`は、Python 3.13以前では関数の定義の時点で注釈が評価されるので、定義そのものが失敗する。
Python 3.14以降は [注釈の評価が遅延される](https://docs.python.org/3/whatsnew/3.14.html#pep-649-pep-749-deferred-evaluation-of-annotations) ので、定義は成功し、`typing.get_type_hints`などで注釈を評価した時点で失敗する。

[PEP 695](https://peps.python.org/pep-0695/) の型パラメータの構文（Python 3.12以降）でも型チェッカーの診断は同一である。

```python
def fmap[F, A, B](f: Callable[[A], B], fa: F[A]) -> F[B]:
    raise NotImplementedError
# mypy
# error: Type variable "F" used with arguments  [valid-type]
# pyright
# error: TypeVar "type[F@fmap]" is not subscriptable (reportGeneralTypeIssues)
```

型変数に型引数を指定できるようにする提案は、[python/typingのissue](https://github.com/python/typing/issues/548) で2018年から議論されていて、採用されたPEPはない。

## Protocolを経由すると戻り値がProtocolの型になる

コンテナの種類を抽象化する別の方法は、`map`メソッドを要求するProtocolである。
次の`Functor`は`map`の形だけを要求し、`ListF`はそれを実装する、説明のために定義したクラスである。
Protocolの判定の規則は [PythonのProtocolと構造的部分型](https://kdot.co.jp/kdotdev/python-protocol-structural-subtyping) で説明している。

```python
from __future__ import annotations
from typing import Protocol, TypeVar, reveal_type

A = TypeVar("A", covariant=True)
B = TypeVar("B")

class Functor(Protocol[A]):
    def map(self, f: Callable[[A], B]) -> Functor[B]: ...

class ListF(Functor[A]):
    def __init__(self, values: list[A]) -> None:
        self.values = values

    def map(self, f: Callable[[A], B]) -> ListF[B]:
        return ListF[B]([f(x) for x in self.values])

    def list_only(self) -> list[A]:
        return self.values

def abstract_map(fa: Functor[A], f: Callable[[A], B]) -> Functor[B]:
    return fa.map(f)

mapped = ListF([1]).map(str)
reveal_type(mapped)  # ListF[str]
mapped.list_only()  # エラーにならない

abstracted = abstract_map(ListF([1]), str)
reveal_type(abstracted)  # Functor[str]
abstracted.list_only()
# mypy
# error: "Functor[str]" has no attribute "list_only"  [attr-defined]
# pyright
# error: Cannot access attribute "list_only" for class "Functor[str]"
```

`ListF`の`map`を直接呼び出す場合は、戻り値の型に`ListF[B]`を指定できるので、結果は`ListF[str]`になる。
`Functor`を引数とする`abstract_map`を経由すると、戻り値の型の指定は`Functor[B]`が限界で、結果は`Functor[str]`になる。
実行時の値は`ListF`だが、型チェッカーは`ListF`に固有のメソッドの呼び出しをエラーにする。
`abstract_map`の戻り値を引数と同じコンテナの型にするには`F[B]`の記述が必要で、これが高カインド型である。

`typing.Self`も代わりにならない。
`Self`は自身のクラスの型を意味するが、型引数を指定できない。

```python
from typing import Self

class Box[A]:
    def changing_map[B](self, f: Callable[[A], B]) -> Self[B]: ...
# mypy
# error: Self type cannot have type arguments  [misc]
# pyright
# error: Expected no type arguments for class "Self" (reportInvalidTypeArguments)
```

`Self`を戻り値にしたメソッドでは型引数を変更できず、上の`Box`の例では`Box[int]`の`map`の結果は常に`Box[int]`になる。

## 回避策

### 対応するコンテナを@overloadで列挙する

対応するコンテナが限られていれば、`@overload`でコンテナごとのシグネチャを列挙できる。

```python
from typing import overload

@overload
def fmap[A, B](f: Callable[[A], B], fa: list[A]) -> list[B]: ...
@overload
def fmap[A, B](f: Callable[[A], B], fa: Box[A]) -> Box[B]: ...
def fmap[A, B](f: Callable[[A], B], fa: list[A] | Box[A]) -> list[B] | Box[B]:
    if isinstance(fa, list):
        return [f(x) for x in fa]
    return Box(None if fa.value is None else f(fa.value))

reveal_type(fmap(str, [1]))   # list[str]
reveal_type(fmap(str, Box(1)))  # Box[str]
```

呼び出し側では戻り値の型が元のコンテナの型になる。
ただし列挙していないコンテナは引数にできず、コンテナを追加するたびに`fmap`の定義の変更が必要になる。

### 変換をコンテナのメソッドにする

コンテナ自身に`map`メソッドを定義すれば、戻り値の型に同一のクラスを指定できる。

```python
from __future__ import annotations

@dataclass
class Box[A]:
    value: A | None

    def map[B](self, f: Callable[[A], B]) -> Box[B]:
        return Box(None if self.value is None else f(self.value))

reveal_type(Box(1).map(str))  # Box[str]
```

`Box`のクラスの定義の中では、`Box`を型コンストラクタとして参照できるので、`Box[B]`を記述できる。
一方で、`map`を定義した複数の種類のコンテナを引数とし、戻り値が引数と同一の種類のコンテナになる関数は、この方法でも定義できない。
その関数の引数の型は前節のProtocolになり、戻り値の型も`Functor[B]`になるからである。

### returnsのKindで型コンストラクタを型引数にする

[returns](https://returns.readthedocs.io/en/latest/pages/hkt.html) ライブラリは、`F[A]`を`Kind1[F, A]`と表記するエンコーディングを提供する。
`F`自体を型引数の1つとして指定するので、型変数に型引数を指定する構文は不要である。
コンテナは`SupportsKind1`を継承し、関数は引数と戻り値を`Kind1`で宣言し、結果は`dekind`で元のコンテナの型に変換する。

```python
from __future__ import annotations
from typing import Any, Generic, TypeVar
from returns.interfaces.mappable import Mappable1
from returns.io import IO
from returns.primitives.hkt import Kind1, SupportsKind1, dekind

A = TypeVar("A")
B = TypeVar("B")

class Box(SupportsKind1["Box[Any]", A], Mappable1[A], Generic[A]):
    def __init__(self, value: A) -> None:
        self.value = value

    def map(self, function: Callable[[A], B]) -> Box[B]:
        return Box(function(self.value))

F = TypeVar("F", bound=Mappable1[Any])

def fmap(f: Callable[[A], B], fa: Kind1[F, A]) -> Kind1[F, B]:
    return fa.map(f)

reveal_type(dekind(fmap(str, Box(1))))  # mypy: Box[str]
reveal_type(dekind(fmap(str, IO(1))))   # mypy: IO[str]
```

`Kind1`の型引数の対応はreturnsの [mypyプラグイン](https://returns.readthedocs.io/en/latest/pages/contrib/mypy_plugins.html) が解決するので、mypyの設定でプラグインを有効にする。

```toml
# pyproject.toml
[tool.mypy]
plugins = ["returns.contrib.mypy.returns_plugin"]
```

型チェッカーごとの`dekind(fmap(str, Box(1)))`の型は次のとおりである。

| 型チェッカー | 推論結果 |
|---|---|
| mypy（returnsのプラグインあり） | `Box[str]` |
| mypy（プラグインなし） | `Box[Any]` |
| pyright | `Box[Any]` |

プラグインがない場合の要素の型は`str`ではなく`Any`になる。
pyrightでも結果は`Box[Any]`で、この方法では変換後の要素の型`str`を保持できない。
引数にできるのは`SupportsKind1`と`Mappable1`に対応したコンテナだけで、`list`はそのままでは引数にできない。

## 他の言語での高カインド型

| 言語 | 高カインド型の書き方 | 備考 |
|---|---|---|
| Haskell | `class Functor f where fmap :: (a -> b) -> f a -> f b` | 型変数のkindは推論で`* -> *`になる |
| Scala | `trait Functor[F[_]]` | `F[_]`で、型引数が1つの型コンストラクタを宣言する |
| TypeScript | 構文なし | fp-tsは型コンストラクタを文字列の識別子に対応させるエンコーディングを採用している |
| Python | 構文なし | returnsの`Kind`はfp-tsと同じ系統のエンコーディングで、mypyのプラグインが前提 |

## 回避策の使い分け

| 状況 | 選択する方法 | 理由 |
|---|---|---|
| 対応するコンテナが少数で固定 | `@overload` | 標準の型ヒントのみで、mypyとpyrightの両方で戻り値の型が元のコンテナになる |
| 変換を自作のコンテナにのみ提供する | コンテナのメソッド | 戻り値の型に同一のクラスを指定できる |
| returnsのインターフェースに対応させたコンテナを抽象化し、型チェッカーはmypyのみ | returnsの`Kind` | mypyのプラグインで戻り値の型が元のコンテナになる |
| `map`を実装したコンテナを抽象化し、戻り値のコンテナに固有の操作は不要 | Protocol | 戻り値の型はProtocolの型になるが、標準の型ヒントのみでmypyとpyrightの両方に対応する |
