TypeScriptの型で素数を求めたい

初心者ながら急にTSの型で遊びたくなり，エラトステネスのふるいを使って素数を求めました．

リポジトリ：sititou70/ts-prime-number-type

TypeScriptとは

TypeScript，あるいはTSとはプログラミング言語の一種であり，JavaScriptと型システムの悪魔合体です．以下のコードを見てください．

const name: string = "sititou70";
          ^^^^^^^^

下線がついていない部分は通常のJavaScriptであり，下線の部分は 型 を表します．この例ではstring型のname変数に"sititou70"を代入しています．

そして今回の記事では， JavaScriptを一切書かず，型システム（下線の部分）だけでプログラミングしよう と思います． 「何言ってんだコイツ」 と感じたあなたは正常です．感じなかったあなたはTSの変態です．

TSの型はチューリング完全

もう数億回言われていることですが，TSの型システムはチューリング完全です．これは簡単に言い換えると，我々はTSの型だけで何でも作れるということです．つまり，型だけでミニ電卓も作れるし，JSONパーサーも作れるし，Brainfuckインタプリタも作れる．そして究極的には，TypeScriptもTSの型だけで作れるということになります（本末転倒）

私も何か作ってみたい，とはいえ型初心者なので手頃な課題は無いかと考えた結果，エラトステネスのふるいで素数を求めることにしました．

このような型パズル系の記事は既に2589番煎じだと思うので，本記事ではオリジナルな部分だけを詳しく書くように努めます．

Step 1：型のテスト環境を整える

私のような初心者にこそ，テストは重要だと思っています．TSの型をテストするには@kgtkrさんのアサーション型やSamVerschueren/tsdなどの方法がありますが，今回はdsherret/conditional-type-checksを使いました．好きなのを選べばいいと思います．

これにより，次のようにテストが書けます．

assert<IsExact<{ hoge: string }["hoge"], string>>(true);

→{ hoge: string }["hoge"]型はstring型に評価されるべき．

Step 2：自然数を作る

最終的には素数を求めたいのですが，型の世界には自然数すらありません．

「いやいや，1型とか2型とかあるじゃん」

と思われるかもしれませんが，それは単にリテラル型があるだけで，型同士の関係性が定義されていません．このままでは「1の次の数」すらわからないため，1 + 1すら計算できないのです．

では他の人はどうしているのかというと，こちらの記事ではペアノの公理を使っていました．なるほど，自然数といえばペアノさんですね．大学の講義でやったような，やってないような…

Wikipedia君に聞いてみました．ペアノの公理とは，簡単に言えば$(X, x, f)$によって自然数を定義するための条件です．ここで，$X$は数の集合，$x$はいかなる数の「後者」でもないもの（つまり一番はじめの数），そして$f: X \rightarrow X$はある数の「後者」を一意に決める関数（つまり$+1$の意味）です．公理の内容は割愛しますが，ともかく$(X, x, f)$をうまく定義することで以下のような自然数の構造が得られるといいます．

なるほどね．まぁ 論よりRUN ．難しい話は置いといて，とりあえず$(Natural, Zero, Succ)$を以下のように実装してみます．

export type Natural = 0[];
export type Zero = [];
export type Succ<N extends Natural> = [...N, 0];

はい！自然数できました！わーい！🎉

Naturalは自然数の集合で，お手製の自然数型です．自然数は0の配列型とし，その要素数によって数を表す ことにしました．[0]は1，[0, 0]は2，[]は0という具合です．

この手の型パズルにおける自然数の定義方法は様々あるのですが，今回は扱いやすさの関係で配列型を用いました．（例えば，Natural型からnumber型への変換が，['length']プロパティで簡単に実現できる…など．）また，配列の中身の型は特に0でなくても良かったのですが， 打ちやすい という理由から0を採用しました．ボタンを一個押すだけで打てますからね．テストコードでNatural型をたくさん書いたので，この点は結構重要でした．

Zeroはゼロです．ゼロを自然数に含めたほうが後々便利なのでゼロは自然数です．数学あるある．

Succ<N>（サック）はNの「後者（successor）」に評価される型です．特に難しくないのでサックリと実装できました（激ウマギャグ）

Step 3：自然数ユーティリティ

Natural，Zero，Succだけではあまりに不便なので，自然数に関するユーティリティを色々定義します．

type Add<N1 extends Natural, N2 extends Natural> = [...N1, ...N2];
type NaturalToNumber<N extends Natural> = N['length'];
type NumberToNatural<N extends number> = ...

Addは足し算を計算する型です．数学的な定義にしたがえばN1にSuccをN2回適用するのが王道です．しかしここはVariadic Tuple Typesでラクをしました．

NaturalToNumberは，Naturalをnumberに変換するユーティリティです．前述したとおり['length']でサックリと書けました．

そして問題のNumberToNatural<N extends number>についてです．これは，numberをNaturalに変換するユーティリティなのですが，ここでは，与えられたNと同じになるまでZeroにSuccを適用していくという愚直な方法しかとれません．つまり，$f( \cdots f(x) \cdots )$をNと等しくなるまで行うということで，型の再帰をたくさんする必要があります．しかしTSには TS2589 という再帰回数の制限があり，ナイーブな実装だとNumberToNatural<50>くらいでギブアップされます．TSくんさぁ…

型ハック1：再帰呼び出しによるTS2589の回避

この制限を回避するには，TSのコードを改変したり，再帰を再帰して再帰したり（？）といった方法があります．今回は一番シンプルな，オブジェクトのプロパティ内で再帰する方法をとりました．@susisuさんありがとうございます．

これはひとことで言えば，とっても 闇 ネストが深いオブジェクトに計算結果をくるんで後から取り出すという，一見して何の意味があるのかわからない操作でTS2589を回避するというものです．回避できる理由は割愛しますが，興味がある方は先程のリンク先を読んでください．

というわけでTS2589回避のためのユーティリティも作ります．

export type ResultContainer<T> = { _: T };
export type ExtractResult<CONTAINER> = ...

くるまれた計算結果をコンテナと呼ぶことにしました．コンテナを表すResultContainer型と，コンテナから計算結果を取り出すExtractResult<CONTAINER>型を実装しました．これで再帰し放題です！

Step 4：エラトステネスのふるいを実装する

この時点で我々ができる操作は，

• 数の等価 / 不等価比較（extendsで最初からできる）
• 自然数（Natural）の表現と足し算
• 配列への値の追加（Variadic Tuple Typesで最初からできる）
• Naturalとnumberの相互変換
• ループ（無制限の再帰呼び出し）

くらいなものです．減算，乗算，除算もできませんし，剰余も求められませんし，数の大小比較も行えません．定義していませんから．

「こんなんでエラトステネスのふるいが実装できるのか？」

と思われるかもしれませんが，結論から言うとできました．おおまかにだけ説明すると，肝となるのはStepFillという型です．

export type StepFill<
  ARRAY extends unknown[],
  START extends Natural,
  STEP extends Natural,
  VALUE extends unknown
> = ...

この型は，配列ARRAYにおいて，START番目の要素からSTEPごとにVALUEを代入するものです．これは，エラトステネスのふるいにおいて合成数をふるい落とす操作に相当し，アルゴリズム全体で最も難しい部分です．つまりこれが実装できればほとんど優勝なわけですが，配列を線形に走査しながら新しい配列へ適切な値を追加していくだけで実装できるので優勝しました 🏆

完成！PrimeNumbers型！

愚直にエラトステネスのふるいを実装した結果，PrimeNumbers<MAX extends number>ができました．これは，MAXまでの素数のリストに評価される型です．

const primes: PrimeNumbers<300> = "string";

としてtsc --noEmitすると…

src/index.ts:3:7 - error TS2322: Type 'string' is not assignable to type '[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293]'.

12 const primes: PrimeNumbers = 'string';
         ~~~~~~


Found 1 error.

やった！PrimeNumbers<300>が[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293]型に評価されています！

細かいこと

Error型

型を書いていると，エラーを投げたい場面があると思います．そのような場合にneverとしても良いのですが，次のようなError型を定義しました．

export type Error<REASON extends string> = { type: "error"; reason: REASON };

これにより，エラーの理由もわかるようになるので，デバッグが捗りました．

型ハック2：型のキャスト

あまり複雑な型を書くとTSの推論がうまく効かず，自分は正しいコードを書いているのに型エラーが発生してしまう場合があります．そんなときは@kgtkrさんのCast型が使えます．

type Cast<T, P> = T extends P ? T : P;

これにより，TSにT型をP型として推論させられます．T extends PすることでTSくんをわからせるという感じでしょうか．詳しくは元記事をどうぞ．

型ハック3：未解決な型によるTS2589の回避

複雑な型を組み合わせ，かつ未解決な型引数を扱っているとTS2589が発生することがあるようです．理由は謎です 😟

この解決にも先程の記事が役立ちました．@kgtkrさん，ありがとうございました．

まとめ

型パズル初心者が型だけで素数を求めてみました．いろいろハードロックな型を書いたせいで，TSの言語サーバーがメモリを食いつぶして爆発するというのも何度か見ました．

今回の開発を通して，TSの変なテクニックをいくつか習得し，型パズルの楽しさも分かってきました．また，型の素振りにもなりましたので，何かの業務に活かせると良いなと思います．