➖

パターンマッチをつかいこなして効率的に型レベル減算しよう！！

2025/06/14に公開

TypeScript

記事投稿コンテスト「TypeScriptでやってみた挑戦・学び・工夫」

tech

はじめに

皆さんこんにちは。
最近はもっぱら型を捏ねてばかりで実益のあるコードをかけておらずまずいなぁと思っています。
27 卒学生エンジニアの yossuli と申します。

以前参加した LT にて型レベル四則演算を行うというものがありました。
今回はその中で登場した減算について、「型黒魔術完全に理解した」になる過程でより簡潔に書けるのではないかと思い、その周辺の技術について記事にしました。

本題

型を捏ねていると以下のようなコードを書く場面がよくあるかなと思います

type Hoge<T> = T extends [any, ...infer U] ?　...

先頭の 2 要素を除きたい場合だったら以下のようになります

type Hoge<T> = T extends [any, any, ...infer U] ? ...

先頭の n 要素を除きたい場合だったら以下のようになります。

type Hoge<T, U extends any[] = []> = T extends [...U, ...infer V]
  ? ...

このように U に除外したいだけの長さの配列を指定した場合、...U で展開されて

Hoge<[0, 1, 2, 3, 4], [any, any, any]>;
// [0, 1, 2, 3, 4] extends [any, any, any, ...infer U]
//                          ^0   ^1   ^2            ^[3, 4]

のようにパターンマッチされます。
今回は長さ 3 の配列を指定したので先頭の 3 要素が取り除かれます。
[any, any, any] の部分が any[] に抽象化されずにタプルとして処理されるのが素晴らしいですね！

型レベル演算において、タプルが抽象化されずに展開され、さらにパターンマッチの際に各要素にきちんとマッチすることは非常に便利です。
というのも、型を捏ねている際に数値計算を行う場合、型レベルで数値を直接計算することができません。
そのため基本的に数値を扱う時には number 型ではなく配列を使いまわし、数値が必要な時になって "length"の長さを利用して計算を行うためです。

【参考】型レベル四則演算

以下より引用

// 二項演算
type NatAdd<A extends N[], B extends N[]> = [...A, ...B];
type NatSub<A extends N[], B extends N[]> = [A, B] extends [
  [N, ...infer RestA extends N[]],
  [N, ...infer RestB extends N[]]
]
  ? NatSub<RestA, RestB>
  : B extends []
  ? A
  : A extends []
  ? [] // 負数になる場合は0を返す
  : never;
type NatMul<A extends N[], B extends N[]> = B extends [
  any,
  ...infer Rest extends N[]
]
  ? [...A, ...NatMul<A, Rest>]
  : [];
type NatFact<A extends N[], B extends N[]> = NatFactRect<[N], A, B>;
type NatFactRect<Result extends N[], A extends N[], B extends N[]> = B extends [
  any,
  ...infer Rest extends N[]
]
  ? NatFactRect<NatMul<Result, A>, A, Rest>
  : Result;

そのため、このように数値を配列として受け取るようなジェネリクス型は使い勝手が良いです。

事例

以下に、タプルの展開とパターンマッチを利用するメリットが感じられた事例をいくつか紹介します。

スライス

type Slice<
  T extends any[],
  Start extends any[],
  End extends any[],
  _T = T
> = _T extends [...End, ...infer _U]
  ? T extends [...infer U, ..._U]
    ? U extends [...Start, ...infer V]
      ? V
      : []
    : T
  : never;

3 回パターンマッチを行うことで効率的にスライスを実現しています。
まずは T のコピーに対して End を展開してパターンマッチを行い、その部分を捨てて余剰部分にマッチする配列を取り出します。
次に剰余部分にマッチさせて End の長さだけの配列を取り出します。（この操作を行わず直接 infer U extends End とすると U の型が [any, ...] になってしまいます）
最後に Start を展開してパターンマッチを行い、その長さを捨てることでスライスを完了します。

配列の配列から最も長い配列の長さを取得

type MaxArrayLength<T extends any[][], Result extends any[] = []> = T extends [
  infer F,
  ...infer Rest extends any[][]
]
  ? F extends [...Result, ...infer V]
    ? MaxArrayLength<Rest, [...Result, ...{ [K in keyof V]: any }]>
    : MaxArrayLength<Rest, Result>
  : Result["length"];

パターンマッチを効果的に利用することで(たぶん)二次元配列において最適である O(n^2) の計算量で最も長い配列の長さを取得することができます。
...{ [K in keyof V]: any で受け取った配列を any 型の配列に変換することで F extends [...Result, ] の部分でいずれの型の要素に対してもマッチさせることができます。
マッチに成功しなかった場合、比較対象の配列が Result よりも長くないことが確定するため、Result をそのまま返します。
マッチに成功した場合、余剰部分を Result に追加します。

効率的に型レベル減算

タプルを展開してパターンマッチを行うようなジェネリクス型を捏ねているうちに、型レベルでの減算を効率的に行う方法が見えてきました。

type Subtract<
  A extends any[],
  B extends any[],
  Result extends any[] = []
> = A extends [...B, ...infer Result] ? Result : [];

このように、A の先頭の B の長さ分を除外することで、型レベルでの減算を実現することができます。

除算も同様に行うことができます。

type Fact<
  A extends any[],
  B extends any[] = [],
  Result extends any[] = []
> = A extends [...B, ...infer Rest extends any[]]
  ? Fact<Rest, B, [...Result, ...any]>
  : Result;

終わりに

いかがでしたでしょうか。
型レベルでの減算を行う際に、タプルの展開をパターンマッチで利用することで、より簡潔で効率的なコードを書くことができるようになりました。
型レベルの演算は非常に奥が深いですね。
今後も型パズルを楽しみながら、より良いコードを書いていきたいと思います。

型レベルマインスイーパーも飽きてほっぽり出してしまっているので、そろそろそろ再開したい所存...

~~課題に追われる日々が憎い...~~

もし、この記事を読んで「こんなこともできるよ！」というアイデアや実装があれば、ぜひコメントで教えていただけると嬉しいです。
また、型パズルを学ぶ際のおすすめな教材やリソースがあれば、ぜひ教えていただけると幸いです。

mosya<TC>の上級はすべて解きました