Variadic Tuple Types を使った型レベル自然数演算

プログラミング TypeScript 小ネタ

つい先日 TypeScript 4.0 RC がリリースされました. めでたいですね.

さて TS 4.0 の目玉機能といえばなんといっても variadic tuple types ですが, これが型レベルで自然数の計算をしたいナウなヤングにバカウケということで, 界隈では一時期のタピオカミルクティーを彷彿とさせる流行を見せているとのことです. このビッグウェーブに乗り遅れるわけにはいかない, というわけでやっていきましょう.

TS 4.0 以前の型レベル自然数

まずは TS 4.0 以前の型レベル自然数を振り返ってみましょう.

型レベルで自然数を表す方法は様々ありますが, ここでは自然数 N を長さ N のタプルで表現する方法を紹介します.

type Natural = unknown[];

type Zero = [];
type One = [unknown];
type Two = [unknown, unknown];

このように表した自然数に対して, 後者関数 Succ<N> および前者関数 Pred<N> は以下のように定義できます. ちょっと複雑ですが, まあ読めなくはないくらいですね.

type Succ<N extends Natural> =
  ((x: unknown, ...xs: N) => unknown) extends (...ys: infer M) => unknown ? M : never;
type Pred<N extends Natural> =
  ((...xs: N) => unknown) extends (y: unknown, ...ys: infer M) => unknown ? M : Zero;

さらに足し算 Add<N> と引き算 Sub<N> も定義してみましょう.

// ???
type Add<N1 extends Natural, N2 extends Natural> =
  ((...xs: N1, ...ys: N2) => unknown) extends (...zs: infer N3) => unknown ? N3 : never;
type Sub<N1 extends Natural, N2 extends Natural> =
  ((...xs: N1) => unknown) extends (...ys: N2, ...zs: infer N3) => unknown ? N3 : Zero;

ところが rest parameter は関数のパラメータのうち最後にしか使用できないため, このような定義はできません. そこで我々は再帰的型定義の沼に足を踏み入れるのでした.

// TypeScript は一般の再帰的型定義を許さないので, ちょっと細工をして無理やり定義する
type Recurse<T, H extends "__hack" = "__hack"> =
  T extends { __rec: unknown }
    ? { [H0 in H]: Recurse<_Recurse<T>> }[H]
    : T;
type _Recurse<T> =
    T extends { __rec: { __rec: infer U } } ? { __rec: _Recurse<U> }
  : T extends { __rec: infer U } ? U
  : T;

type Add<N1 extends Natural, N2 extends Natural> = Recurse<_Add<N1, N2>>;
type _Add<N extends Natural, M extends Natural> =
  N extends Zero
    ? M
    : { __rec: _Add<Pred<N>, Succ<M>> };

type Sub<N1 extends Natural, N2 extends Natural> = Recurse<_Sub<N2, N1>>;
type _Sub<N extends Natural, M extends Natural> =
  N extends Zero
    ? M
    : { __rec: _Sub<Pred<N>, Pred<M>> };

type Four = Add<Two, Two>;
type Three = Sub<Four, One>;

ちょっとつらいですよね. ちなみにこういったやんちゃをしているとよく tsserver がスッと落ちます.

TS 4.0 以降の型レベル自然数

さて TS 4.0 の variadic tuple types でこれらの演算がどのように変わるかを見ていきましょう.

自然数の表現は TS 4.0 以前のものと同じです.

type Natural = unknown[];

type Zero = [];
type One = [unknown];
type Two = [unknown, unknown];

後者関数 Succ<N> および前者関数 Pred<N> は, 以下のように variadic tuple types を使うことで以前よりもシンプルに定義することができます.

type Succ<N extends Natural> = [unknown, ...N];
type Pred<N extends Natural> = N extends [unknown, ...infer M] ? M : Zero;

足し算 Add<N> と引き算 Sub<N> を定義するのにも, もはや再帰的型定義は必要ありません.

type Add<N1 extends Natural, N2 extends Natural> = [...N1, ...N2];
type Sub<N1 extends Natural, N2 extends Natural> = [...N1] extends [...N2, ...infer N3] ? N3 : Zero;

type Four = Add<Two, Two>;
type Three = Sub<Four, One>;

簡単ですね.

次回予告

型レベルで数の加減算が容易に実現できるようになったということで, さらに発展させて次元をもった量の計算などはどうでしょう?