mosya<TC> - Union 型からその組み合わせの配列を生成する型を実装するの解説

この記事はmosya<TC>の問題の一つであるPermutation型の解説になります。

問題

Union 型を Union 型の値の順列を含む配列に変換する順列型を実装します。

type perm = Permutation<
  "A" | "B" | "C"
>; // ['A', 'B', 'C'] | ['A', 'C', 'B'] | ['B', 'A', 'C'] | ['B', 'C', 'A'] | ['C', 'A', 'B'] | ['C', 'B', 'A']

解答例

type Permutation<T, K = T> = [
  T
] extends [never]
  ? []
  : K extends K
  ? [K, ...Permutation<Exclude<T, K>>]
  : never;

Permutationで二つの型パラメータを定義する

まず、Permutation<T, K = T> の部分ですが、これは型パラメータ K にデフォルト値として T を指定しています。これにより、K は T と同じ型を持つことになります。
ここで、Kを定義する理由は、後ほど、K extends Kでユニオンの各要素を条件式で順番に取り出すために使います。

再帰処理の終了条件を定義する

次に [T] extends [never] ? [] : ...の部分ですが、これは再帰処理の終了条件を定義しています。ここでは、Tがnever型の場合は空の配列を返し、それ以外の場合は...の部分の処理を行います。
never extends neverは評価ができないので配列を利用してTがnever型かどうかを判定しています。

順列を生成する

次に K extends K ? [K, ...Permutation<Exclude<T, K>>] : never の部分で、次に処理する要素 K を配列の先頭に置き、その後ろに T から K を除いた残りの要素の順列を配置します。ここで Exclude<T, K> は T から K を取り除いた型を作ります。
extendsを使った条件式ではユニオンのメンバーは個別に評価されるのでこの特性を利用して、ユニオンの各要素を順番に取り出すことができます。

この過程を繰り返していくことで、全ての順列が生成されます。

わかりやすくするために、要素が A, B, C の3つだけの場合を考えてみましょう。まず、A を先頭に置き、残りの要素 B, C の順列を作ります。次に、B を先頭に置き、残りの要素 A, C の順列を作ります。最後に、C を先頭に置き、残りの要素 A, B の順列を作ります。この各ステップで、残りの要素から順列を作るために同じ処理を再帰的に行います。最終的に、全ての順列が生成されます。