README.md

TypeScript において型レベルで自然数の計算を行うサンプルです。 実用的かどうかは分からないけど、型レベル再帰のテクニックとかは普通に使えそう (というか使った)。

以下を参考にしました。

• タプル型の操作
• 最低 N 個の要素をもつ配列型
• 型レベルプログラミングエラー抑制テクニック
• TypeScript の型システムはチューリング完全

type-arithmetic.ts

// T が S を継承していることを型推論器に伝えます。
// 型制約エラーを抑制するために利用できます。
type Cast<T, S> = T extends S ? T : S;

type Append<T, A extends Array<any>> = ((arg: T, ...rest: A) => void) extends ((...args: infer B) => void) ? B : never;
type Remove<A extends Array<any>> = A["length"] extends 0 ? [] : ((...args: A) => void) extends (arg: any, ...rest: infer B) => void ? B : [];

// 数値リテラル型を any から成るタプル型に変換します。
// 例えば、ToTuple<3> は [any, any, any] に評価されます。
type ToTuple<N extends number> = ToTupleRec<N, []>;
type ToTupleRec<N, A extends Array<any>> = {
  0: A,
  1: ToTupleRec<N, Append<any, A>>
}[A extends {length: N} ? 0 : 1];

// タプル型を数値リテラル型に変換します。
type FromTuple<A extends Array<any>> = A["length"];

// 型レベル自然数の後続数を計算します。
type Succ<N extends number> = FromTuple<Append<any, ToTuple<N> extends infer X ? Cast<X, Array<any>> : never>>;

// 2 つの型レベル自然数の和を計算します。
type Plus<M extends number, N extends number> = PlusRec<M, N, M, []>;
type PlusRec<M, N, R extends number, A extends Array<any>> = {
  0: R,
  1: PlusRec<M, N, Succ<R>, Append<any, A>>
}[A extends {length: N} ? 0 : 1];

type Seven = Plus<4, 3>;  // 7
type Twelve = Plus<3, 9>;  // 12

// 型レベル自然数の前者数を計算します。
type Prev<N extends number> = FromTuple<Remove<ToTuple<N> extends infer X ? Cast<X, Array<any>> : never>>;

// 2 つの型レベル自然数の差を計算します。
type Minus<M extends number, N extends number> = MinusRec<M, N, M, []>;
type MinusRec<M, N, R extends number, A extends Array<any>> = {
  0: R,
  1: MinusRec<M, N, Prev<R>, Append<any, A>>
}[A extends {length: N} ? 0 : 1];

type Six = Minus<9, 3>;  // 6

// 2 つの型レベル自然数の積を計算します。
type Times<M extends number, N extends number> = TimesRec<M, N, 0, []>;
type TimesRec<M extends number, N, R extends number, A extends Array<any>> = {
  0: R,
  1: TimesRec<M, N, Plus<R, M> extends infer X ? Cast<X, number> : never, Append<any, A>>
}[A extends {length: N} ? 0 : 1];

type Fifteen = Times<3, 5>;  // 15
type TwentyFour = Times<4, 6>;  // 24