TypeScriptの型で素因数分解する

こちらは LAPRAS Advent Calendar 2022の25日目の記事です。
https://qiita.com/advent-calendar/2022/lapras

概要

本記事では、与えられた自然数を素因数分解する型を作っていきます。
以下のPrimeFactorList型が完成イメージです。

const foo: PrimeFactorList<15> = [3, 5]
const bar: PrimeFactorList<16> = [2, 2, 2, 2]

バージョン情報

• TypeScript: v4.9.4

素因数分解のために必要なこと

最も素朴な「試し割り法」で行う場合、以下の 3 種類の計算が必要です。

• numberリテラル型Iが与えられたとき、その次の数I + 1の型を作れる（ループを回すため）
• 素因数分解したい数Nが、Iで割り切れるかどうかを判定できる
• 割り切れる場合にその商が計算できる

実際の「試し割り法」では、割る数を√N以下に限定するなどの工夫も行いますが、今回はとにかく素因数分解できる所までを目指すのでこの 3 つで十分となります。

型レベルで自然数を操作する

上記 3 種類の計算を型システム上で行うためには、まずはnumberリテラル型を計算可能な形に変換する必要があります。

今回は「タプルの長さを介して自然数の計算を行う方法(en)」を採用しました。

まずはその方法を、簡単な例をつかって解説します。

足し算を行う例

numberリテラル型1と2の足し算を行う場合は以下のようになります。

• 型1を長さ1のタプル型Tに変換する（方法は後述）
• 型2を長さ2のタプル型Uに変換する
• TとUを連結させ、長さ3のタプル型[...T, ...U]を得る
• そのタプルの長さ[...T, ...U]['length']を取ることで、型3を得る

つまり、

1. 自然数Nの型を、長さNのタプル型に変換
2. そのタプルを好きなように操作
3. 操作後のタプルのlengthを取得することで数値型に戻す

ということです。
このような方法をとるのは、numberリテラル型よりもタプル型の方が色々と操作がしやすいためです。

実装

「数Nを長さNのタプルに変換する型」は以下のように作れます。

与えられた自然数Nからその長さのタプルを作る型

type NumToTuple<
  N extends number,
  Result extends unknown[] = []
> = Result['length'] extends N
  ? Result 
  : NumToTuple<N, [...Result, unknown]>

使用例

let tuple: NumToTuple<3> // [unknown, unknown, unknown] 

一見ややこしく見えますが、やっていることは単純な再帰です。

• Resultタプルの長さがN未満なら、Resultに要素を一つ追加した上でNumToTupleを再度呼び出す
• Resultタプルの長さがNになったらResultを返す

Resultはデフォルトで[]型なので、N回ほど再帰すれば長さNのタプルが得られることになります。

「次の数」の型を作る

これで「数Iの次の数を返す型」が作れるようになりました。

次の数の型

type PlusOne<I extends number> = [...NumToTuple<I>, unknown]['length']

使用例

let four: PlusOne<3> // 4

数Iをタプルに変換し、要素を一つ追加してからそのlengthを取っているだけで簡単ですね。

引き算

次に「割り切れるかどうかを判定する型」を作っていきたいところですが、それは、

• 引き算の繰り返し
• 大小判定

から作れるので、まずは引き算を行う型から作成して行きます。

引き算の型

type Subtraction<
  N extends number,
  M extends number
> = NumToTuple<N> extends [
  ...NumToTuple<M>,
  ...infer U
]
  ? U['length']
  : never

使用例

let two: Subtraction<3, 1> // 2

解説

inferを用いて以下を行なっています。

• 長さMのタプルと、何らかのタプルUを繋げて長さNのタプルが作れそうなら、Uの長さを返す
• そのようなUが存在しなそうなら(Mの方がNより大きいということなので)neverを返す

例えばN = 3でM = 1の場合は、TS君が「Uとして長さ2のタプルを取ってくれば長さNのタプルが作れそうだな」と勝手に推論してくれます。賢いですね。

大小判定

次は大小判定です。これは引き算から簡単に作れます。

大小判定の型

type IsStrictlySmaller<
  N extends number,
  M extends number
> = Subtraction<N, M> extends never ? true : false

使用例

let is1SmallerThan2: IsStrictlySmaller<1, 2> // true

割り切れるかどうかの判定

これでようやく「割り切れるかどうかを判定する型」が作れるようになりました。

割り切れるかを判定する型

type IsDivisible<
  N extends number,
  M extends number
> = N extends 0
  ? true
  : isStrictlySmaller<N, M> extends true
  ? false
  : IsDivisible<Subtraction<N, M>, M>

使用例

let is8DivisibleBy2: <8, 2> // true

解説

• N < Mになるまで、NからMを引いていく
• 最終的にNが0になった場合、NはMの自然数倍ということなのでtrue
• 0より大きい数になった場合は、それが余りなのでfalse

今回は型が複雑になり過ぎないようゼロ除算や負数・浮動小数点値などは考慮していません

割り算

この節で下準備は最後です！
割り算もシンプルな引き算の再帰で作れます。

割り算の型

type Division<
  N extends number,
  M extends number,
  Q extends unknown[] = [] // 商
> = isStrictlySmaller<N, M> extends true 
  ? Q['length']
  : Division<Subtraction<N, M>, M, [unknown, ...Q]>

使用例

let eightDividedByTwo: <8, 2> // 4

解説

• N < Mになるまで「NからMを引いて商Qを1増やす」を繰り返す。
  （つまりQは「NをMで何回引けたか」を表す）
• N < MになったらQの長さを返す。

初めは「余り付き割り算」の型を作ったのですが、それだと「再帰が深すぎ」のエラーが出たため、結局割り算と余りの計算は別々に行うことにしました。

素因数分解

とうとう素因数分解までたどり着きました！
少し複雑ですが、基本的なテクニックはこれまでと同じです。

素因数分解をする型

type PrimeFactorList<
  N extends number, 
  I extends unknown[] = [unknown, unknown],
  Result extends number[] = []
> = N extends 1
  ? Result
  : I['length'] extends N
  ? [...Result, N]
  : IsDivisible<N, I['length']> extends true
  ? PrimeFactorList<Division<N, I['length']>, I, [...Result, I['length']]>
  : PrimeFactorList<N, [0, ...I], Result> // Iをインクリメントして再帰

解説

• N = 1なら、素因数がないので[]を返す
• N > 1なら、Iを長さ2から開始して、NがIの長さと等しくなるまで以下を繰り返す
  • NがIの長さで割り切れるなら、NをIの長さで割って、ResultにIを追加して再帰
  • NがIの長さで割り切れないなら、Iをインクリメントして再帰

Iをnumberではなくタプルで持っているのは、再帰の深さエラーにより型推論がうまくいかなかったためです

結果は以下のようになります。

let pf1: PrimeFactorList<1> // []
let pf2: PrimeFactorList<2> //[2]
let pf3: PrimeFactorList<3> // [3]
let pf4: PrimeFactorList<4> // [2, 2]
let pf5: PrimeFactorList<5> // [5]
let pf6: PrimeFactorList<6> // [2, 3]
let pf7: PrimeFactorList<7> // [7]
let pf8: PrimeFactorList<8> // [2, 2, 2]
let pf9: PrimeFactorList<9> // [3, 3]
let pf10: PrimeFactorList<10> // [2, 5]
let pf11: PrimeFactorList<11> // [11]
let pf12: PrimeFactorList<12> // [2, 2, 3]
let pf13: PrimeFactorList<13> // [13]
let pf14: PrimeFactorList<14> // [2, 7]
let pf15: PrimeFactorList<15> // [3, 5]
let pf16: PrimeFactorList<16> // [2, 2, 2, 2]
let pf17: PrimeFactorList<17> // [17]
let pf18: PrimeFactorList<18> // [2, 3, 3]
let pf19: PrimeFactorList<19> // [19]
let pf20: PrimeFactorList<20> // [2, 2, 5]
let pf21: PrimeFactorList<21> // [3, 7]
let pf22: PrimeFactorList<22> // [2, 11]
let pf23: PrimeFactorList<23> // [23]
let pf24: PrimeFactorList<24> // [2, 2, 2, 3]
let pf25: PrimeFactorList<25> // [5, 5]
let pf26: PrimeFactorList<26> // [2, 13]
let pf27: PrimeFactorList<27> // [3, 3, 3]
let pf28: PrimeFactorList<28> // [2, 2, 7]
let pf29: PrimeFactorList<29> // [29]
let pf30: PrimeFactorList<30> // [2, 3, 5]
.
.
.
let pf999: PrimeFactorList<999> // [3, 3, 3, 37]

型のみを使って正しく素因数分解することができています🎉

本来は再帰の上限により 49 までの数しか扱えないのですが、今回は末尾再帰(en)を用いたため 999 まで扱えています。

---

全体のコードはこちらにあります。

さらに工夫を加えれば、より大きな数の素因数分解もできるかと思います。
興味のある方は是非試してみてください！

🎅🎁🎄𝕄𝕖𝕣𝕣𝕪 𝕏𝕞𝕒𝕤...🎄🎁🎅