再帰的型定義ではオブジェクト型のプロパティの遅延評価に注意

この記事の内容は typescript@4.5.4 で動作確認しています.

TL; DR

  • TypeScript において, オブジェクト型のプロパティは必要になるまで評価が遅延される
  • 遅延されていたプロパティの評価が行われるときには, TypeScript 4.5 の末尾再帰の最適化が効かない

例題: FizzBuzz

型レベルで FizzBuzz やります.

type A4 = FizzBuzz<4>;   // = 4
type A6 = FizzBuzz<6>;   // = "Fizz"
type A10 = FizzBuzz<10>; // = "Buzz"
type A15 = FizzBuzz<15>; // = "FizzBuzz"

まずは以下のような型 NumMod を使って自然数とその剰余を表現することにします.

type NumMod = {
  // 長さ N のタプルで自然数 N を表現
  num: unknown[];
  // 合わせて N mod 3, N mod 5 を追跡する
  mod3: 0 | 1 | 2;
  mod5: 0 | 1 | 2 | 3 | 4;
};

この NumMod にしたがって 0 を表現すると以下のようになります.

type Zero = {
  num: [];
  mod3: 0;
  mod5: 0;
};

また NumMod に 1 を足す操作は以下のように定義できます.

type Increment<V extends NumMod> = {
  // タプルに要素を 1 つ追加する
  num: [...V["num"], unknown];
  // 剰余はそれぞれ 1 ずつ進める
  mod3: { 0: 1; 1: 2; 2: 0 }[V["mod3"]];
  mod5: { 0: 1; 1: 2; 2: 3; 3: 4; 4: 0 }[V["mod5"]];
};

NumMod は既に FizzBuzz に必要な剰余が計算されている形になっているため, 出力は単に条件分岐を行うだけ良いです.

type Print<V extends NumMod> =
  V["mod3"] extends 0
    ? V["mod5"] extends 0 ? "FizzBuzz" : "Fizz"
    // タプルは T["length"] で number に変換できる
    : V["mod5"] extends 0 ? "Buzz" : V["num"]["length"];

最後に FizzBuzz<N> は, 与えられた数 N になるまで 0 から順番に 1 を足していき, N まで到達したら出力を行うだけで完成です.

type FizzBuzz<N extends number> = Loop<Zero, N>;
type Loop<V extends NumMod, N extends number> =
  V["num"]["length"] extends N
    ? Print<V>
    : Loop<Increment<V>, N>;

簡単ですね.

type A4 = FizzBuzz<4>;   // = 4
type A6 = FizzBuzz<6>;   // = "Fizz"
type A10 = FizzBuzz<10>; // = "Buzz"
type A15 = FizzBuzz<15>; // = "FizzBuzz"

ここまでのコードはこちら.

末尾再帰の最適化

上で定義した Loop<V, N> は末尾再帰の形になっているため, TypeScript 4.5 であれば末尾再帰の最適化が行われ, 最大で 1000 回まで繰り返しを行うことが可能なはずです.

ということでまずは試しに 100 を入力してみましょう. うまくいけば "Buzz" が出力されるはずです.

type A100 = FizzBuzz<100>;
//          ~~~~~~~~~~~~~
// error TS2589: Type instantiation is excessively deep and possibly infinite.

残念ながら親の顔より見た TS2589 エラー (型のインスタンス化の上限の超過) が出て失敗してしまいました. なぜでしょうか?

オブジェクト型のプロパティの遅延評価

試しに Loop<V, N> を以下のように Print<V> をしないように変更して, 最終的な V の様子を見てみることにします.

type Loop<V extends NumMod, N extends number> =
  V["num"]["length"] extends N
    ? V // ? Print<V>
    : Loop<Increment<V>, N>;

このように変更すると FizzBuzz<100> を計算するだけでは TS2589 エラーは発生しなくなります. 一方で A100 にカーソルをホバーさせるなどして型の内容を見てみると, num はうまく計算されているようですが, mod3mod5any となってしまっています.

type A100 = FizzBuzz<100>;
// type A100 = {
//   num: [unknown, (中略), unknown];
//   mod3: any;
//   mod5: any;
// };

さらにこの mod3mod5 を参照しようとすると, そこで TS2589 エラーが発生します.

type X = A100["mod3"];
//       ~~~~~~~~~~~~
// error TS2589: Type instantiation is excessively deep and possibly infinite.

ここで思い当たるのがオブジェクト型のプロパティの遅延評価です.

Increment<V> の定義を見てみると, 各プロパティの新たな値をプロパティの定義の中で計算しています. この場合, 新たな値は即座に評価されず, プロパティが参照されるなどして必要になった時に初めて評価されます.

type Increment<V extends NumMod> = {
  num: [...V["num"], unknown];
  mod3: { 0: 1; 1: 2; 2: 0 }[V["mod3"]];
  mod5: { 0: 1; 1: 2; 2: 3; 3: 4; 4: 0 }[V["mod5"]];
};

このため, 元々の Loop<V, N> の計算は,

  • V["num"]["length"]N になるまで Increment<V> を繰り返す
  • N に到達したら Print<V> を行うが, このときに初めて遅延されていた V のプロパティの評価を行う

という順番で行われることになります. そして前者では末尾再帰の最適化が行われますが, 後者では最適化が行われないために, 上限を突破してエラーとなってしまうようです.

この遅延評価の機構は再帰的なオブジェクト型を定義する際には有効に働きますが, 今回のケースでは正格に評価してしまうのが適切そうです.

FizzBuzz 修正版

ということで Increment<V> がプロパティを正格に評価するようにします. 方法はいくつかありますが, ここではオブジェクト型をリテラルで書くのではなく, 型エイリアスを経由して作成するようにしてみましょう.

type MakeNumMod<Num, Mod3, Mod5> = {
  num: Num;
  mod3: Mod3;
  mod5: Mod5;
};

type Increment<V extends NumMod> = 
  MakeNumMod<
    [...V["num"], unknown],
    { 0: 1; 1: 2; 2: 0 }[V["mod3"]],
    { 0: 1; 1: 2; 2: 3; 3: 4; 4: 0 }[V["mod5"]]
  >;

このように変更するだけで無事末尾再帰の最適化の恩恵を受けられるようになり, FizzBuzz<100> でも FizzBuzz<666> でも計算できるようになります. よかったですね.

type A100 = FizzBuzz<100>; // = "Buzz"
type A666 = FizzBuzz<666>; // = "Fizz"

完成形のコードはこちら.

読者への宿題

以下を TS2589 エラーを回避しつつ計算できるような FizzBuzz<V> を定義しましょう.

type A2021 = FizzBuzz<2021>; // = 2021
type A2022 = FizzBuzz<2022>; // = "Fizz"

愚直な方法でも, 工夫して計算する方法でも, ハックめいた方法でも実現可能です.