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

注意

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

TL; DR

１．やりたいこと

　長さ$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を次のように定義します。

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$なので、添え字がタプルの長さに達したときにループを止める操作も実装できそうに思えます。

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

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は型の再帰を直接書くことができないため、この型定義はエラーを起こします¹²。

４．再帰的な型定義

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

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

type T = T;

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

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

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

　一方で、次の型定義は可能です³。

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

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

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

type T = Array<T>[0];

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

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

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

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

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

５．Reverseの実装

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

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];

　この型定義は確かにうまくいきます（コードサンプルで確認できます）。

さいごに

　この記事は@uhyoさんの記事と再帰的な型定義の公式解説を特に参考にしています。なんならこの２つを見たほうが早いかもしれません。

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

注意