TypeScriptで型のループを計算する

## 注意

　この記事では相当ルーズに等号などの記号を使っています。きっちり頑張るのはつらいので、ぜひ良い感じに読んでください。また、TypeScriptのバージョンは3.9を想定しています。

## TL; DR

[コードサンプル](https://www.typescriptlang.org/play?#code/C4TwDgpgBAKhDOwoF4oCUIDcICd4QB4BtARgBooAmCgZgF0A+AbgCgXRJ0td8CYoIAD2AQAdgBN4UAK6iA1qID2Ad1FFGKKAH0M2PIRgV1RuhRhEARABsxAc2AALC41btw0Hd30EWUKADEcRQBbAWExSRl5JVVjX1hFMJEJKVkFFTVTeIBJCSEkiNTojLi-ABkAS2CKpCFkyNFpYIAjXBYGTQBveIAGAC4E1j8SAc89Xni-QJCySagAQTBICQJp4KJc8SFLG1F7JzpTBIZZvz9F5fECNJjRCk2hE7nK6uB45hYAXw28wQKUqCdKC7fYDF41KCfKAAfigPSgAxIdFcHGgFwifAoAFV-pEbiUNKgABREwQDQxQAB01JAAyxAEoUB1MIoKuJGXVClAifFqZSyVAKqIAGa4KAANRYjOQzNZ4nisMlfgGoi8rCAA)

## １．やりたいこと

　長さ$n$のタプル型
$$
A = [ A[0], A[1], \dots, A[n - 1]]
$$
に対して、この並び順を逆転させた型
$$
\mathrm{Reverse} \langle A \rangle = [A[n - 1], A[n - 2], \dots, A[0]]
$$
を計算するようなジェネリクス`Reverse`を定義したいとします。この記事では`Reverse`の実装を通して、タプル型の要素１つ１つを列挙・加工し、新たな型を定義する方法を説明します。

## ２．準備

　`Reverse`を定義する前に、必要となる型をあらかじめ定義しておきます。
$$
\mathrm{Append} \langle \mathrm{unknown}, A \rangle = [\mathrm{unknown}, A[0], A[1], \dots, A[n - 1]]
$$
であるようなジェネリクス`Append`を次のように定義します。

```typescript
type Append<T, U extends unknown[]> = ((x: T, ...y: U) => void) extends (
  ...x: infer V
) => void
  ? V
  : never;
```

## ３．添え字の計算

　まず型のforループにあたるものを実装します。つまり、タプル`["a", "b", "c"]`があるとして、このタプルの各要素`"a","b","c"`に順番にアクセスする方法を考えていきます。

　通常、配列の全列挙を行いたいときは添え字を１づつ増やしますが、TypeScriptにおいて型`1`と型`1`を足して型`2`を得ることは（簡単には）できません。

　そこで次のような方法を採ります。`unknown`が$n$個だけ並んだタプル`X<n>`を添え字$n$と対応させ、以下のよう書くことにします。ただし$[] \leftrightarrow 0$です。

$$
n  \leftrightarrow X \langle n \rangle =\left[ \underbrace{\mathrm{unknown}, \dots, \mathrm{unknown}}_n \right]
$$

　このとき

$$
n + 1 \leftrightarrow X \langle n + 1 \rangle = \mathrm{Append} \langle \mathrm{unknown}, X \langle n \rangle \rangle
$$

なので、for文における`i++`にあたるものを計算できます。

　また、$n$は`X<n>`の長さなので`X<n>["length"]`で取り出せます。そのため、型`X<i> extends { length: n } ? 1 : 0`は$i = n$のとき$1$、$i \neq n$のとき$0$なので、添え字がタプルの長さに達したときにループを止める操作も実装できそうに思えます。

　試しに、再帰を使って次のような実装を書いてみます。

```typescript
type Reverse<T extends unknown[]> = _Reverse<T, [], [], T["length"]>;

type _Reverse<
  From extends unknown[],
  To extends unknown[],
  Index extends unknown[],
  Limit extends number
> = Index extends { length: Limit }
  ? To
  : _Reverse<
      From,
      Append<From[Index["length"]], To>,
      Append<unknown, Index>,
      Limit
    >;
```

　これは一見うまくいきそうですが、まだ少し足りません。TypeScriptは型の再帰を直接書くことができないため、この型定義はエラーを起こします[^1][^4]。

## ４．再帰的な型定義

　先ほど「TypeScriptは型の再帰を直接書くことができない」と言いました。この項ではこれについて、もう少し詳しく説明します。

　例えば、TypeScriptにおいて次のような型定義はできません。

```typescript
type T = T;
```

　これがなぜできないかというと、この定義を許した場合

- 右辺の`T`は型エイリアスなので、`T`の定義の右辺`T`に置き換える必要がある。
- その`T`も型エイリアスなので、`T`の定義の右辺`T`に置き換える必要がある。
- その`T`も……

といった具合で、置き換えがいつまでたっても終了しないためです[^4]。

　一方で、次の型定義は可能です[^*1]。

```typescript
type T = Array<T>;
// const t: T = [[], [[]]];
```

　２つの違いは「`T`を定義するために、右辺の型エイリアスを調べつくす必要があるかどうか」にあります。２つ目の例では、`T`を定義するには`T`が`Array<any>`の部分型であることさえ知っていれば十分です。`T`の要素にアクセスされるときまで、右辺の型エイリアス`T`を調べる必要はありません。なので、TypeScriptのコンパイラをこのような型定義を許すように実装できます。

　以上の理屈だと、次の型定義はできないことになります（実際できません）。

```typescript
type T = Array<T>[0];
```

なのですが、次の型定義は可能です。

```typescript
type T<U extends 0 | 1> = {
  0: U,
  1: T<U>
}[U];
```

　この型定義はプログラムのどこかに`T<1>`と書いたとたんにエラーを起こしますが、`T<1>`がプログラム中に表れない限りはエラーを起こしません。`T`を定義するときに`T<1>`を計算する必要はない（し、コンパイラも計算しない）からです。

　上の例は少し非現実的ですが、例えば長さ１で深くネストされたタプル```[[[1]]]```から`1`を取り出すジェネリクス`Flatten`は以下のように定義できます。

```typescript
type Flatten<T> = {
  0: T,
  1: T extends [infer U] ? Flatten<U> : never,
}[T extends [unknown] ? 1 : 0];
```

## ５．Reverseの実装

　以上を踏まえて`Reverse`を定義します。第３節の型定義を少し変形して、第４節のしかけを導入します。

```typescript
type Reverse<T extends unknown[]> = _Reverse<T, [], [], T["length"]>;

type _Reverse<
  From extends unknown[],
  To extends unknown[],
  Index extends unknown[],
  Limit extends number
> = {
  0: To;
  1: _Reverse<
    From,
    Append<From[Index["length"]], To>,
    Append<unknown, Index>,
    Limit
  >;
}[Index extends { length: Limit } ? 0 : 1];
```

　この型定義は確かにうまくいきます（[コードサンプル](https://www.typescriptlang.org/play?#code/C4TwDgpgBAKhDOwoF4oCUIDcICd4QB4BtARgBooAmCgZgF0A+AbgCgXRJ0td8CYoIAD2AQAdgBN4UAK6iA1qID2Ad1FFGKKAH0M2PIRgV1RuhRhEARABsxAc2AALC41btw0Hd30EWUKADEcRQBbAWExSRl5JVVjX1hFMJEJKVkFFTVTeIBJCSEkiNTojLi-ABkAS2CKpCFkyNFpYIAjXBYGTQBveIAGAC4E1j8SAc89Xni-QJCySagAQTBICQJp4KJc8SFLG1F7JzpTBIZZvz9F5fECNJjRCk2hE7nK6uB45hYAXw28wQKUqCdKC7fYDF41KCfKAAfigPSgAxIdFcHGgFwifAoAFV-pEbiUNKgABREwQDQxQAB01JAAyxAEoUB1MIoKuJGXVClAifFqZSyVAKqIAGa4KAANRYjOQzNZ4nisMlfgGoi8rCAA)で確認できます）。

## さいごに

　この記事は[@uhyoさんの記事](https://qiita.com/uhyo/items/80ce7c00f413c1d1be56)と[再帰的な型定義の公式解説](https://www.typescriptlang.org/docs/handbook/release-notes/typescript-3-7.html#more-recursive-type-aliases)を特に参考にしています。なんならこの２つを見たほうが早いかもしれません。

## 参考文献

+ [TypeScriptで最低n個の要素を持った配列の型を宣言する方法](https://qiita.com/uhyo/items/80ce7c00f413c1d1be56)
+ [TypeScriptの型入門](https://qiita.com/uhyo/items/e2fdef2d3236b9bfe74a)
+ [TypeScriptの型初級](https://qiita.com/uhyo/items/da21e2b3c10c8a03952f)
+ [TypeScript: Handbook - TypeScript 3.7](https://www.typescriptlang.org/docs/handbook/release-notes/typescript-3-7.html#more-recursive-type-aliases)

[^1]: [TypeScriptで最低n個の要素を持った配列の型を宣言する方法](https://qiita.com/uhyo/items/80ce7c00f413c1d1be56)
[^2]: [TypeScriptの型入門](https://qiita.com/uhyo/items/e2fdef2d3236b9bfe74a)
[^3]: [TypeScriptの型初級](https://qiita.com/uhyo/items/da21e2b3c10c8a03952f)

[^4]: [TypeScript: Handbook - TypeScript 3.7](https://www.typescriptlang.org/docs/handbook/release-notes/typescript-3-7.html#more-recursive-type-aliases)
[^*1]: 正確にはTypeScript 3.7で可能になりました[^4]。