TypeScript で型レベル階乗

こんなことがやりたかったんじゃないし, 誰もそんなこと望んじゃいない. でもやる.

動作確認している TypeScript のバージョンは 3.8.3 です.

ゴール

TypeScript で階乗を計算します. 型レベルで.

type F = Factorial<3>;
// F = 6

イデア

まずタプル型の length を参照すると, 長さが数値リテラル型で得られるという事実があります.

type S = ["foo", "bar", "baz"]["length"];
// S = 3

そして前回の記事でも使ったように, タプル型に対しては要素を追加する / 取り除くといった操作を定義できます. これは長さで言うと +1 / -1 ですね. さらにこれらを (再帰的型定義も使いつつ) 組み合わせることで, より複雑な操作も可能になります.

ということは, タプル型と数値リテラル型を相互変換できさえすれば, 数値リテラル型に対して様々な自然数の演算 (苦笑) を行うことが可能というわけですね.

準備1. タプル型と数値リテラル型の相互変換

まずは自然数を表現する型を決めておきます. Nat が数値リテラル型での表現, TNat がタプル型での表現です. タプル型の中身はなんでも良いので unknown としておきます.

type Nat = number;
type TNat = unknown[];

つづいて相互変換です.

type ToNat<XS> = XS extends TNat ? XS["length"] : never;
type ToTNat<N extends Nat> = ToTNatSub<[], N, "__hack">;
type ToTNatSub<XS extends TNat, N extends Nat, H extends "__hack"> =
  XS["length"] extends N
    ? XS
    : { [H0 in H]: ToTNatSub<TSucc<XS>, N, H> }[H];

タプル型から数値リテラル型への変換 ToNat<XS> は単に length を参照するだけです. その逆方向の変換 ToTNat<N> は, タプル型の長さが数値リテラル型と一致するまで TSucc<XS> (後述) を使って伸ばしていく, という乱暴なことをしています.

準備 2. Succ, Pred

+1 / -1 を行う操作です.

type TSucc<XS> =
  XS extends TNat
    ? ((x: unknown, ...xs: XS) => unknown) extends (...ys: infer YS) => unknown ? YS : never
    : never;
type Succ<N extends Nat> = ToNat<TSucc<ToTNat<N>>>;

type TPred<XS> =
  XS extends TNat
    ? (
      XS extends []
        ? []
        : ((...xs: XS) => unknown) extends (y: unknown, ...ys: infer YS) => unknown ? YS : never
    ) : never;
type Pred<N extends Nat> = ToNat<TPred<ToTNat<N>>>;

タプル型に対する演算は前回の記事で使った Cons<XS>Tail<XS> をちょっと改変しただけです. 数値リテラル型の演算は, タプル型へ変換してから演算を行って元に戻す, というように定義しておきます.

準備 3. 加算, 乗算

+1 / -1 ができれば, あとは再帰を使えば加算や乗算なども次々定義していけます. まずは加算は以下.

type TAdd<XS, YS> = TAddSub<XS, YS, "__hack">;
type TAddSub<XS, YS, H extends "__hack"> =
  XS extends []
    ? YS
    : { [H0 in H]: TAddSub<TPred<XS>, TSucc<YS>, H> }[H];
type Add<M extends Nat, N extends Nat> = ToNat<TAdd<ToTNat<M>, ToTNat<N>>>;

N に +1 を M 回行う, という素朴な定義です.

つづいて乗算.

type TMul<XS, YS> = TMulSub<XS, YS, [], "__hack">;
type TMulSub<XS, YS, ZS, H extends "__hack"> =
  XS extends []
    ? ZS
    : { [H0 in H]: TMulSub<TPred<XS>, YS, TAdd<ZS, YS>, H> }[H];
type Mul<M extends Nat, N extends Nat> = ToNat<TMul<ToTNat<M>, ToTNat<N>>>;

0 に +N を M 回行います. そうだね.

階乗

さて目的の階乗ですが, これも加算や乗算と同じノリで定義できます.

type TFactorial<XS> = TFactorialSub<XS, [unknown], "__hack">;
type TFactorialSub<XS, YS, H extends "__hack"> =
  XS extends []
    ? YS
    : { [H0 in H]: TFactorialSub<TPred<XS>, TMul<YS, XS>, H> }[H];
type Factorial<N extends Nat> = ToNat<TFactorial<ToTNat<N>>>;

ここまで一気に駆け抜けてきましたが, はじめて動作確認をしてみましょう.

type F = Factorial<3>;
// F = 6

無事 3 の階乗が計算できました. よかったですね.

と喜んだのも束の間, Factorial<4> を計算しようとすると Type instantiation is excessively deep and possibly infinite. と怒られてしまいます. 仏の顔も三度まで, ってか...

記事中のコード全体はこちら.