TypeScriptの型レベルプログラミングで足し算・引き算・掛け算を実装する

2021-05-01

TOC

  1. なぜタプル型なのか
    1. 比較：再帰的な定義
  2. 実装していく
    1. リテラル型→タプルへの変換
    2. タプル→リテラル型の変換
    3. 足し算の実装
    4. 引き算の実装
    5. 掛け算の実装
  3. おまけ：Multipleを用いて、より大きい数を作る
  4. まとめ

こんにちは。shundroidです。
最近型レベルプログラミングに興味があります。
TypeScriptの型機能、気づかぬうちにめちゃくちゃ強くなっていてすごいですね。最大限活用したいですが、実用上は使う機会あるのでしょうか。

変な型を作るのは楽しいですよね。
というわけで、今回は次のような型(Add<T, U> 型、 Minus<T, U> 型、 Multiple<T, U> 型)を実装しようと思います。

1
2
3
type AddTest = Add<3, 5>; // 8
type MinusTest = Minus<8, 4>; // 4
type MultipleTest = Multiple<6, 2>; // 12

さらに、より大きな数にも対応できるために工夫をします。
（大きな数には再帰制限が働きやすいので、工夫が必要なのです。後述します）

最終的には、次くらいの大きさの演算でも行けるようにします。

1
type MultipleTest2 = Multiple<20, 100>; // 2000

実装にはタプル型を用います。

なぜタプル型なのか

まず、型レベルプログラミングでよく扱われるタプル型について少し書きます。
型レベルプログラミングでは、 0 や 1 、 2 などのリテラル型を、 [] や [any] 、 [any, any] のように、その長さを持ったタプル型に変換して処理することが多いです。

これはなぜかというと、タプルにおいて、演算をしていくうえで不可欠な操作が可能だからです。
この「不可欠な操作」は大きく次の３つになると思います。

1
2
3
4
5
6
7
8
9
// 操作1
type tupleA = [0, 1];
type tupleB = [...tupleA, 2]; // [0, 1, 2]

// 操作2
type tupleC = [tupleB] extends [infer I, ...any[]] ? [I] : never; // [0]

// 操作3
type len = tupleB["length"] // 3 (literal type)

すなわち、型プログラミングにおいて、要素の追加(操作1)と、一部取り出し(操作2)があり、
そして実用的な表現に戻す手法として、タプル長をリテラル型として取得する(操作3)が存在するのです。

比較：再帰的な定義

Haskell などでの関数型プログラミングでは、ペアノの公理的に自然数を次のように定義し、演算を作っていくのが自然でしょう。

1
Zero, Next<Zero>, Next<Next<Zero>>, ...

ですが、TypeScriptでは 再帰回数の制限が厳しく 、あまり値の定義に再帰を使いたくないのです。

また、既に演算が一部定義されていて、さらに操作3により実用的な表現に落とし込めるタプル型を上回るメリットが、このような再帰的な自然数定義にはありません。

何だかんだタプル型が強いので、これを使っていきます。

実装していく

リテラル型→タプルへの変換

このサイトを参考に、 Repeat 型を用います。

（ここに書かれているbrainf*ckインタプリタもなかなか気になっちゃいますね）

このサイトはマジで凄くて、型プログラミングをするうえで大事なヒントが沢山載っています。
眺めているだけでも楽しい。このブログもこういう風にしていきたいですね。

というわけで、上のサイトを参考に Repeat 型を実装します。
ここはそのままです。

1
2
3
type Repeat<T, N extends number, R extends any[] = []> = R["length"] extends N
  ? R
  : Repeat<T, N, [T, ...R]>;

型プログラミングはかなり可読性が低いですが、このくらいなら分かりやすいですね。
再帰を利用して、所定の長さになるまでタプル型を伸ばしています。

これを用いて数値を表したいので、分かりやすくするため、エイリアスを用意しましょう。

1
type ToTupleNum<T extends number> = Repeat<any, T>;

こうすると、 toTupleNum<4> は [any, any, any, any] 型になります。

タプル→リテラル型の変換

ここは簡単です。というかタプル型がやはり強すぎる。

1
2
type TupleNum = any[];
type ToNumber<T extends TupleNum> = T["length"];

こうすると、 ToNumber<TupleNum<4>> は 4 (リテラル型)になります。
ToNumber は関数のように機能する型です。対して TupleNum<T> は変数のように機能しますね。意味論的には、TypeScript の型には色んな種類があるようです。

足し算の実装

もう簡単ですね。

1
2
type _Add<T extends TupleNum, U extends TupleNum> = [...T, ...U];
type Add<T extends number, U extends number> = ToNumber<_Add<ToTupleNum<T>, ToTupleNum<U>>>;

単純にextractしてあげればよいです。

これで足し算が実装できます。

1
type testAdd = Add<5, 8>; // 13

引き算の実装

引き算は色々実装方法があると思います。ここでは最も楽そうな方法を書きます。

1
2
type _Minus<T extends TupleNum, U extends TupleNum> = T extends [...U, ...infer X] ? X : never;
type Minus<T extends number, U extends number> = ToNumber<_Minus<ToTupleNum<T>, ToTupleNum<U>>>;

これで引き算が実装できます。

1
type testMinus = Minus<10, 8>; // 2

ちなみに、負の数は定義していないので、 Minus<1, 2> のようにすると死にます。

掛け算の実装

足し算と引き算は出オチでしたね。...T と infer を用いて、簡単に足し算と引き算を定義することができました。

問題は掛け算です。
最も計算理論的に思いつきやすいのは、やはり再帰による定義でしょう。

$$
Multiple(a, b)=
\begin{cases}
Multiple(a, b-1)+b & (b>1) \\
a & (b=1)
\end{cases}
$$

ただし、$a\neq 0,b\neq 0$としています。（実際の実装では0の時を考慮しています）

1
2
3
4
5
6
type _Multiple<T extends TupleNum, U extends TupleNum> = {
    "ifZero": [],
    "ifUIsOne": T,
    "else": _Add<_Multiple<T, _Minus<U, [any]>>, T>
}[T extends [] ? "ifZero" : U extends [] ? "ifZero" : U extends [any] ? "ifUIsOne" : "else"];
type Multiple<T extends number, U extends number> = ToNumber<_Multiple<ToTupleNum<T>, ToTupleNum<U>>>;

確かにこれでも行けます。ですが、先ほども書きましたが、TypeScriptは再帰回数に厳しい。
この計算では、僕の環境では高々×23くらいまでしか出来ませんでした。

そこで応急的な改善。こうしたら確かに×40くらいまではいけました。
$$
Multiple(a, b)=
\begin{cases}
Multiple(a, b-2)+2\times b & (b>1) \\
a & (b=1) \\
0 & (b=0)
\end{cases}
$$

ただし、$a\neq 0$としています。（実際の実装では0の時を考慮しています）

$2\times b$ の $\times$ は$Multiple(a,b)$ とは区別しています。これは実装が異なるからです。
$2\times b$ は、TypeScriptでは [...T, ...T] で実装しています。

1
2
3
4
5
6
type _Multiple<T extends TupleNum, U extends TupleNum> = {
  "ifZero": [],
  "ifUIsOne": T,
  "else": _Add<[...T, ...T], _Multiple<T, _Minus<U, [any, any]>>>
}[T extends [] ? "ifZero" : U extends [] ? "ifZero" : U extends [any] ? "ifUIsOne" : "else"]
type Multiple<T extends number, U extends number> = ToNumber<_Multiple<ToTupleNum<T>, ToTupleNum<U>>>;

確かに、これはやればやるほど確かに計算限界は上がります。
今はステップ数を2にしていますが、これを3,4,5,…という風にしていけば、線形に再帰数は減少するでしょう。

ですが、根本的解決にはなりませんよね。そこで、次のような方式を取りました。
まずはコードを見てください。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
type DigitsStr = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";
type OtherThanLast<T extends string> = T extends `${infer X}${DigitsStr}` ? X : never;
type Last<T extends string> = T extends `${OtherThanLast<T>}${infer X}` ? X : never;
type Times<T extends TupleNum> = {
  "0": [],
  "1": [...T],
  "2": [...T, ...T],
  "3": [...T, ...T, ...T],
  "4": [...T, ...T, ...T, ...T],
  "5": [...T, ...T, ...T, ...T, ...T],
  "6": [...T, ...T, ...T, ...T, ...T, ...T],
  "7": [...T, ...T, ...T, ...T, ...T, ...T, ...T],
  "8": [...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T],
  "9": [...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T],
};
type TenTimes<T extends TupleNum> = [...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T, ...T];

type _Multiple<T extends TupleNum, U extends string> = {
  "ifZero": [],
  "ifOneLen": U extends keyof Times<any> ? Times<T>[U] : never,
  "else": Last<U> extends keyof Times<any> ?
    _Add<Times<T>[Last<U>], TenTimes<_Multiple<T, OtherThanLast<U>>>> : never
}[T extends [] ? "ifZero" : U extends [] ? "ifZero" : U extends `${DigitsStr}` ? "ifOneLen" : "else"];
type Multiple<T extends number, U extends number> = ToNumber<_Multiple<ToTupleNum<T>, `${U}`>>;

最近追加された Template Literal Types を用いています。
こちらの記事をやや参考にしました。

やっていることは、筆算です。

$$
12\times 345=12\times 5+(12\times 34)\times 10 \\
=12\times 5+(12\times 4 + (12\times 3)\times 10)\times 10
$$

一般化すると、次のようになります。

$$
Multiple(a, b)=
\begin{cases}
a\times last(b)+Multiple(a, otherthanlast(b))\times 10 & (b\geq 10) \\
a\times b & (otherwise)
\end{cases}
$$

ただし、$a\neq 0$としています。（実際の実装では0の時を考慮しています）
$last(a)$は文字としてのaの最後の文字を取得し、それを数値にしています。
TypeScriptでも Last 型として定義しています。

1
type testLast = Last<"12345"> // "5"

$otherthanlast(a)$は文字としてのaの最後の文字以外を取得し、それを数値にしています。
TypeScriptでも OtherThanLast 型として定義しています。

1
type testOtherThanLast = OtherThanLast<"12345"> // "1234"

$a\times b$は$Multiple(a, b)$とは分けています。$\times$のほうは[...T, ...T] のように、TypeScriptの機能を利用しています。

これで、掛ける数がとても大きくても掛け算ができるようになりました。めでたし。

1
type testMultipleBig = Multiple<2, 4999>; // 9998

どうやら、今度はタプルの長さの最大に引っかかるようで、10000以上の長さにタプルを作れず、
結果が10000を超えてしまう場合は計算できなくなってしまいます。
一難去ってまた一難。これはまた、データ形式を工夫するなどして、今度対処しましょう。

おまけ：Multipleを用いて、より大きい数を作る

先ほど、ToTupleNum ではRepeatを用いていたので、再帰制限のためせいぜい45くらいまでの数しかTupleにできませんでしたが、
このMultipleを用いれば、実はもっと大きな数が作れるようになります。

1
type SuperToTupleNum<T extends number> = Multiple<1, T>;

まとめ

TypeScriptの型システムは、本当に奥が深いです。
こういう変なことをするのが大好きなので、もう少し調べてみたいと思います。

今回のコードは、こちらで試すことができます。
型に計算結果が入っているので、カーソルをその型に合わせると、中身が分かると思います。

© 2021 asterisks - Powered by Hexo - Theme Chan