こんなことがやりたかったんじゃないし, 誰もそんなこと望んじゃいない. でもやる.
動作確認している 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.
と怒られてしまいます. 仏の顔も三度まで, ってか...