型は日頃の開発を強く支えてくれます。
解決しようとしている問題の制約を実現するような、
スマートな型定義ができたときは何事にも変え難い喜びですよね。

そんな TypeScript の型システムはチューリング完全であることを前々から聴いていました。
とはいえ、業務や趣味でプロダクトを作ろうとしても特別複雑な型に触れることはないため、Conditional Types を初めとした実装を繰り返すことはありませんでした。

今回は Advent Calendar という特別な機会もあり、普段関わることのない型レベルのプログラミングにチャレンジしてみます。もし間違っている説明や、より良い実装があればお手柔らかに御指南いただければ幸いです。

それではじめて参ります。

前提知識

今回の実装を理解するにあたっては、TypeScript の以下の機能に対する理解が必要です。

Conditional Types
Inferring
Tuples

作成した型の動作確認は、以下を用います。

type Assert<L, R extends L> = L extends R ? 'pass' : 'fail';

型制約エラーを抑制するための型を一部で使用します。(参考)

type Cast<Value, Type> = Value extends Type ? Value : never;

四則演算の実装

TypeScript の型レベルでは、数値の演算は定義されていません。
そのため、Tuple から取得した length を元に数値を扱います。

type NumberToTuple<
  Value extends number,
  Acc extends unknown[] = [],
> = Acc['length'] extends Value ? Acc : NumberToTuple<Value, [...Acc, unknown]>;

type NumberToTupleTest = Assert<
  NumberToTuple<4>,
  [unknown, unknown, unknown, unknown]
>; // -> "pass"

インクリメント, デクリメント, 再帰を組み合わせれば簡単に加算と減算が実装できそうです。

type Increment<Value extends number> = Cast<
  [...NumberToTuple<Value>, unknown]['length'],
  number
>;

type IncrementTest = Assert<Increment<1>, 2>; // -> "pass"

type Decrement<Value extends number> = NumberToTuple<Value> extends [
  unknown,
  ...infer Rest,
]
  ? Rest['length']
  : never;

type DecrementTest = Assert<Decrement<1>, 0>; // -> "pass"

type Add<L extends number, R extends number> = R extends 0
  ? L
  : Add<Increment<L>, Decrement<R>>;

type AddTest = Assert<Add<1, 1>, 2>; // -> "pass"

type Sub<L extends number, R extends number> = R extends 0
  ? L
  : Sub<Decrement<L>, Decrement<R>>;

type SubTest = Assert<Sub<1, 1>, 0>; // -> "pass"

乗算・除算・剰余も同様の方針で実装

type Mul<
  L extends number,
  R extends number,
  Acc extends number = 0,
> = L extends 0 ? Acc : R extends 0 ? Acc : Mul<L, Decrement<R>, Add<Acc, L>>;

type MulTest = Assert<Mul<2, 2>, 4>; // -> "pass"

type Div<
  L extends number,
  R extends number,
  Acc extends number = 0,
> = L extends R ? Increment<Acc> : Div<Sub<L, R>, R, Increment<Acc>>;

type DivTest = Assert<Div<4, 2>, 2>; // -> "pass"

type Mod<L extends number, R extends number> = Sub<L, R> extends never
  ? L
  : Mod<Sub<L, R>, R>;

// Type instantiation is excessively deep and possibly infinite.ts(2589)
type ModTest = Assert<Mod<4, 2>, 0>; // -> "fail"

ここでいろんな数を試しているうちに、再帰呼び出しの制約に引っ掛かってしまいました。
再帰上限がある、というのは前情報から心得ていたことなのですが、結構早い段階で引っ掛かってしまうみたいですね。

再帰上限突破方法もあるようですが、今回は TypeScript 本体の変更をせず、できるところまでやってみましょう。
Tuple を直接扱うことで再帰を行わずに加算が実装できそうです。

type Add<L extends number, R extends number> = Cast<
  [...NumberToTuple<L>, ...NumberToTuple<R>]['length'],
  number
>;

type AddTest = Assert<Add<1, 1>, 2>; // -> "pass"

減算は結局思い付かずで、参考にさせていただきました。型レベルのプログラミングは難しいですね。
Conditional Types で制約を作り、Inferring で結果を推論させる方法でいけるみたいです。
（結果が負の数になるものは演算できませんが）
思い付かなかったのはちょっと悔しいですが、解らなかったものが解るものになった時はやっぱり嬉しい。
素敵な経験をありがとうございます。

type Sub<L extends number, R extends number> = NumberToTuple<L> extends [
  ...NumberToTuple<R>,
  ...infer ResultTuple,
]
  ? ResultTuple['length']
  : never;

type SubTest = Assert<Sub<1, 1>, 0>; // -> "pass"

FizzBuzz

剰余が問題なく求められれば、型レベル FizzBuzz が実装できますね。

type FizzBuzz<Value extends number> = Mod<Value, 15> extends 0
  ? 'FizzBuzz'
  : Mod<Value, 5> extends 0
  ? 'Buzz'
  : Mod<Value, 3> extends 0
  ? 'Fizz'
  : Value;

type FizzBuzzTest1 = Assert<FizzBuzz<1>, 1>; // -> "pass"
type FizzBuzzTest3 = Assert<FizzBuzz<3>, 'Fizz'>; // -> "pass"
type FizzBuzzTest5 = Assert<FizzBuzz<5>, 'Buzz'>; // -> "pass"
type FizzBuzzTest15 = Assert<FizzBuzz<15>, 'FizzBuzz'>; // -> "pass"

階乗計算

階乗計算は 6 が限界みたい。

type Factorial<Value extends number> = Value extends 0
  ? 1
  : Mul<Value, Factorial<Sub<Value, 1>>>;

type FactorialTest1 = Assert<Factorial<1>, 1>; // -> "pass"
type FactorialTest2 = Assert<Factorial<2>, 2>; // -> "pass"
type FactorialTest3 = Assert<Factorial<3>, 6>; // -> "pass"
type FactorialTest4 = Assert<Factorial<4>, 24>; // -> "pass"
type FactorialTest5 = Assert<Factorial<5>, 120>; // -> "pass"
type FactorialTest6 = Assert<Factorial<6>, 720>; // -> "pass"

// Type instantiation is excessively deep and possibly infinite.ts(2589)
type FactorialTest7 = Assert<Factorial<7>, 5040>; // -> "fail"

閏年の判定

僕にとっての思い出のアルゴリズムです。
高校時代の課題でいくつかパターンを出して提出したのですが、そのことをとても褒めてくれた先生がいました。プログラムに自信を持ったり、今でもプログラミングを愛することができるきっかけになった、大切な思い出です。
自分も誰かのそんな存在になりたいなぁ、と常々思います。

type IsLeap<Value extends number> = Mod<Value, 4> extends 0
  ? Mod<Value, 100> extends 0
    ? Mod<Value, 400> extends 0
      ? true
      : false
    : true
  : false;

type IsLeapTest4 = Assert<IsLeap<4>, true>; // -> "pass"
type IsLeapTest100 = Assert<IsLeap<100>, false>; // -> "pass"
type IsLeapTest400 = Assert<IsLeap<400>, true>; // -> "pass"

終わりに

いやぁ、楽しい。もう夢中になってパズルを解いていました。
来年はもっと楽しく TypeScript を書いていけそうです。

全ての TypeScript プログラマへ愛を込めて。
よき型ライフを。　