type-challengesの醍醐味「算術演算系問題」の紹介
はじめに
この記事は、TSKaigi Advent Calendar 2024の24日目の記事です。
フロントエンドエンジニアのhigh-gです。
TSKaigi Kansai 2024に引き続き、TSKaigi 2025も運営メンバーとして参加しています。
最近は、業務開始前にTypeScriptの型パズル問題集として知られるtype-challengesに取り組むことを日課としています。
type-challengesの問題の中でも、個人的に最も面白いと感じているのが算術演算系問題です。
本記事では、中級の難問として知られるMinusOneをテーマとして扱います。
普段何気なく行っている算術演算を型レベルで実現する中で、型パズルの奥深い面白さを体感していただけると幸いです。
※本記事を読む前に、TypeScriptのジェネリクス、Conditional Types、inferを理解しておくことをおすすめします。
MinusOneとは？
以下が問題のリンクです。
型引数として与えられた数値リテラル型をデクリメントし、その結果として得られる数値リテラル型を返す型定義を実装するという問題になります。
例えば、55が型引数として与えられた場合、54が返されれば正解となります。
type FiftyFour = MinusOne<55> // 54が返されれば正解
この問題の難しい点は、TypeScriptの型システムにデフォルトでデクリメントする仕組みが存在しないところです。
言い換えれば、以下のような単純な算術演算が、型レベルでは実行できないということになります。
// このような直接的な減算はTypeScriptの型システムでは不可能です
type MinusOne<Num> = Num - 1
では、どのようにアプローチすればよいでしょうか？
MinusOneをいきなり取り組むには難易度が高いため、準備運動として型引数の数値リテラル型をインクリメントして返す問題、PlusOneからはじめてみましょう。
※なお、PlusOneという問題はtype-challengesには存在しません。
PlusOneをやってみる
結論として、以下のような型定義になります。
type PlusOne<T extends number, Count extends unknown[] = []> =
Count['length'] extends T
? [...Count, 1]['length']
: PlusOne<T, [...Count, 1]>
type Res = PlusOne<2> // 3
※注意点として、この型定義は型引数の値が大きい場合、ネストの深さによってType instantiation is excessively deep and possibly infinite.(2589)のエラーが発生するため、比較的小さい数値リテラル型のみの対応となっています。
この型定義には、TypeScriptの型システムで数値演算を行う上で重要な要素が含まれているため、詳細を分解して確認していきましょう。
ジェネリクスの構造解説
type PlusOne<T extends number, Count extends unknown[] = []>
この型定義には2つの型引数があります
- 第1引数：外部から受け取る数値リテラル型
- 第2引数：カウントアップを担う配列型（デフォルト値は空配列）
Conditional Typesの動作
Count['length'] extends T
? [...Count, 1]['length']
: PlusOne<T, [...Count, 1]>
以下のロジックでインクリメントを実現しています。
- Count['length']で配列型の長さを数値リテラル型として取得
- 配列の長さと入力された数値リテラル型を比較
- 一致した場合：カウントアップした配列型の長さを返却
- 一致しない場合：カウントアップしながら再帰的に処理を繰り返し
この一連の型操作により、型引数の値をインクリメントした数値リテラル型を得ることができます。
TypeScriptの型システムで算術演算の基本的アプローチ
ここまでの説明から分かるように、型レベルでの算術演算は、以下の流れで行われるのが基本です。
- 任意の配列型を準備する
- 配列型に任意の型を代入する
- 代入処理を再帰的に実行する
- 最終的に、準備した配列型の長さ（length）を確認する
MinusOneを改めてやってみる
改めて問題の内容を確認します。以下の条件を満たすMinusOneを実装することが目標です。
type FiftyFour = MinusOne<55> // 54が返されれば正解
MinusOneのシンプルなアプローチ
まず、PlusOneと同様の流れで実装を始めます。最初に、2つの型引数を持つジェネリクスを定義します。
type MinusOne<T extends number, Count extends unknown[] = []> = any
次に、PlusOneと同様にConditional Typesと再帰を使用して型を構築します。
type MinusOne<T extends number, Count extends unknown[] = []> =
Count['length'] extends T
? [...Count, 1]['length']
: MinusOne<T, [...Count, 1]>
この時点では、型引数をインクリメントした数値リテラル型が返されるため、型引数をデクリメントように修正する必要があります。
シンプルな解決策として、以下の解答例があります。
リンク先を参考にしながら、本記事用に少しだけ手を加えると以下のようになります。
type Pop<T extends unknown[]> = T extends [...infer head, unknown] ? head : never;
type MinusOne<T extends number, Count extends unknown[] = []> = Count['length'] extends T
? Pop<Count>['length']
: MinusOne<T, [...Count, 1]>
変更点は、以下です。
- 自作ユーティリティ型Popを新たに実装
- Conditional Typesの条件に一致した場合の記述を
Pop<Count>['length']に変更
Popの型定義をピックアップしてみます。
type Pop<T extends unknown[]> = T extends [...infer head, unknown] ? head : never;
この自作ユーティリティ型Popは、配列型から末尾要素を簡潔に除外する型変換を実現しています。
型引数Tが[...infer head, unknown]のパターンにマッチする場合、元の配列型から最後の要素を削除した新しい配列型（head）を返します。
そのため、Pop<Count>で、Countから要素を一つ削除した配列型を生成でき、Pop<Count>['length']で、型引数の値から1を引いた数値リテラル型を返却できています。
この実装で一件落着としたいところですが、残念ながら重大な制約があります。
PlusOneと同様に、型引数の値が大きくなると、ネスト構造が深くなり、Type instantiation is excessively deep and possibly infinite.(2589)のエラーが発生する問題があるため、比較的小さい数値リテラル型のみ対応という点は変わりません。
シンプルで美しい実装であるものの、実用面では大きな制限があります。
この問題を見事にクリアしている解答例を確認してみましょう。
Type instantiation is excessively deep and possibly infinite.をクリアしている解について
type ParseInt<T extends string> = T extends `${infer Digit extends number}` ? Digit : never
type RemoveLeadingZeros<S extends string> = S extends '0' ? S : S extends `${'0'}${infer R}` ? RemoveLeadingZeros<R> : S
type InternalMinusOne<
S extends string
> = S extends `${infer Digit extends number}${infer Rest}` ?
Digit extends 0 ?
`9${InternalMinusOne<Rest>}` :
`${[9, 0, 1, 2, 3, 4, 5, 6, 7, 8][Digit]}${Rest}`:
never
type ReverseString<S extends string> = S extends `${infer First}${infer Rest}` ? `${ReverseString<Rest>}${First}` : ''
type MinusOne<T extends number> = ParseInt<RemoveLeadingZeros<ReverseString<InternalMinusOne<ReverseString<`${T}`>>>>>
少し記述量が多めですが、MinusOneの型定義から順番にみていきましょう。
type MinusOne<T extends number> = ParseInt<RemoveLeadingZeros<ReverseString<InternalMinusOne<ReverseString<`${T}`>>>>>
自作ユーティリティ型がいくつも入れ子になっているため、一つずつ分解していきましょう。
まずは、ジェネリクスの最も内側にある記述に着目します。
ReverseString<`${T}`>
自作ユーティリティ型ReverseStringの型引数に、型Tを文字列リテラル型にキャストした型を渡しています。
ReverseStringの型定義は以下です。
type ReverseString<S extends string> = S extends `${infer First}${infer Rest}` ? `${ReverseString<Rest>}${First}` : ''
この型は、inferを使用することで、文字列型の型Sを先頭文字（First）とそれ以外の文字列（Rest）に分解し、${ReverseString<Rest>}${First}によって再帰的に処理しながら、型引数として与えられた文字列型の並び順を逆転していきます。
次に確認する型は、InternalMinusOneです。
InternalMinusOne<並び順が逆転した文字列リテラル型>
InternalMinusOneの型定義は以下です。
type InternalMinusOne<
S extends string
> = S extends `${infer Digit extends number}${infer Rest}` ?
Digit extends 0 ?
`9${InternalMinusOne<Rest>}` :
`${[9, 0, 1, 2, 3, 4, 5, 6, 7, 8][Digit]}${Rest}`:
never
本実装のキモとなる部分です。inferを利用し、文字列型の型Sを先頭の数字（Digit）と残りの文字列（Rest）に分解します。
その後、Conditional Typesで先頭が0か、0以外かで分岐します。
先頭が0の場合、9${InternalMinusOne<Rest>}とし、0を9に変換後残りの文字列型をInternalMinusOneの型引数とすることで再帰処理を行っています。
少し混乱するので、具体的な数値リテラル型で考えてみると、以下のような順で処理されます。
- 元の数値リテラル型10の場合、Sには並び順が逆転した文字列リテラル型が代入されるため、01となる
- 01が
${infer Digit extends number}${infer Rest}の部分で分解され、Digitには0が入る - Digitが0の場合、
Digit extends 0のConditional Typesの条件と一致するので、9${InternalMinusOne<Rest>}が適用され、この部分だけ見ると91となり、再帰処理で再度1の部分がInternalMinusOneの型引数として渡される
先頭が0以外の場合は、[9, 0, 1, 2, 3, 4, 5, 6, 7, 8][Digit]を使用し、Digitに応じて-1された数値リテラルを取得します。
例えば、Digitが5の場合、[9, 0, 1, 2, 3, 4, 5, 6, 7, 8][5]により4が得られます。
この実装により、型レベルのデクリメントが可能になります。
次にもう一度、ReverseStringを利用しています。このおかげで、文字列の並び順がもとに戻ります。
ReverseString<並び順が逆転し、-1された文字列リテラル型>
次は、RemoveLeadingZeros型が適用されています。
RemoveLeadingZeros<-1された文字列リテラル型（ただし先頭に0が残るパターンが存在）>>
RemoveLeadingZerosの型定義は以下です。
type RemoveLeadingZeros<S extends string> = S extends '0' ? S : S extends `${'0'}${infer R}` ? RemoveLeadingZeros<R> : S
これは型Sの先頭文字が0だった場合、その0を取り除くための型定義です。
MinusOneに与えられた型引数が、例えば、100だった場合、RemoveLeadingZerosが実行されるまでの時点では099という文字列リテラル型になっています。
RemoveLeadingZerosは、099を再帰的に精査しながら先頭の0を取り除き、最終的に99という文字列リテラル型に変換します。
そして、最後にParseInt型に、ここまでの処理で生み出された-1された文字列リテラル型を渡しています。
ParseInt<-1された文字列リテラル型>
ParseIntの型定義は以下です。
type ParseInt<T extends string> = T extends `${infer Digit extends number}` ? Digit : never
inferとextendsを組み合わせ、数値型が内包された文字列リテラル型Tから数値型Digitを取得する実装となっています。
ここまでの工程を経て、ようやく型引数の値から1を引いた数値リテラルが得られました。
ちなみに以下のような桁数が非常に大きいテストケースでもエラーなくデクリメントが出来ています。
Expect<Equal<MinusOne<9_007_199_254_740_992>, 9_007_199_254_740_991>>
まとめ
いかがでしたでしょうか？
ただデクリメントする処理でも型システムの制約により難易度が格段に上がります。
複雑な型変換を行うため、TypeScriptの型システムを深く理解していないと問題解決が困難になります。
このような型レベルの複雑なプログラミングは、一般的な業務では滅多に遭遇しないため、直接的な実用性は低いかもしれません。
しかし、inferを活用した文字列型の分解や再帰的な型定義などの技術を磨くことで、より高度で複雑な型定義を実装するスキルが身につきます。
また、外部ライブラリの型定義を読解する際の理解力も向上するでしょう。
この記事を読んで型パズルに興味を持った方は、ぜひtype-challengesに挑戦してみてください！
イベント告知
TSKaigi 2025が、2025年5月23日(金)・24日(土)の2日間で開催されます！
TSKaigiは、日本最大級のTypeScriptカンファレンスです。
前回のTSKaigi 2024は2,000人以上が参加し、同年11月に京都で開催したTSKaigi Kansai 2024もチケット完売で大盛況でした！
TypeScriptに興味のある方は、ぜひ会場に足を運び、最新の技術トレンドやTSコミュニティの熱量に触れてみてください！！
Discussion