遊びです. 真に受けないでください.
動作確認している TypeScript のバージョンは 3.8.3 です.
ゴール
タプル型 XS から, 要素の置換 (permutations) の union 型を作る Permutations<XS> を作ります.
type P = Permutations<["A", "B", "C"]>; // P = ["A", "B", "C"] | ["B", "C", "A"] | ["C", "A", "B"] // | ["B", "A", "C"] | ["C", "B", "A"] | ["A", "C", "B"]
準備 1. Head, Tail, Cons
まずはタプル型を操作するための基本的な道具を揃えていきます.
タプル型の先頭と, 先頭を除いた残りを返す Head<XS>, Tail<XS> については以前の記事でも紹介しました.
type Head<XS extends readonly unknown[]> = XS extends readonly [] ? never : XS[0]; type Tail<XS extends readonly unknown[]> = XS extends readonly [] ? never : TailSub<XS>; type TailSub<XS extends readonly unknown[]> = ((...xs: XS) => unknown) extends ((y: never, ...ys: infer YS) => unknown) ? YS : never;
タプル型の先頭に要素を付け加える Cons<X, XS> は以下のように定義できます. ちょうど TailSub<XS> の逆のような形ですね.
type Cons<X, XS extends readonly unknown[]> = ((x: X, ...xs: XS) => unknown) extends (...ys: infer YS) => unknown ? YS : never;
準備 2. 巡回
基本的な操作が用意できたところで, 続いてタプル型の要素を入れ替える操作を作っていきます.
まずタプル型の先頭の要素を末尾に付け替える操作 Rotate<XS> は以下のように書けます.
type Rotate<XS extends readonly unknown[]> = XS extends unknown ? { [I in keyof XS]: I extends keyof Tail<XS> ? Tail<XS>[I] : Head<XS> } : never;
タプル型に対して mapped type を作るとそのままタプル型になることを利用しつつ, インデックス I が最後の要素を指していなければ Tail<XS> の I 番目の要素を, 最後の要素を指していれば Head<XS> を, 新たなタプルの要素としています.
続いて巡回の union 型を返す Rotations<XS> を作ります. まずは思いつくまま, 要素の数だけ Rotate<XS> を作用させることを繰り返して, union 型としてまとめるようなものを書いてみます.
type Rotations<XS extends readonly unknown[]> = XS extends readonly [] ? XS : RotationsSub<XS, XS>; type RotationsSub<XS extends readonly unknown[], L extends readonly unknown[]> = L extends readonly [] ? never : XS | RotationsSub<Rotate<XS>, Tail<L>, H>;
TypeScript は型のレベルでは数に対する演算は (簡単には) 行えないので, 数の代わりにリスト L を用いて, リストが空になるまで繰り返すようにしています.
さてこれで完成と思いきや, 型を再帰的に定義しているために TypeScript から Type alias 'RotationsSub' circularly references itself. のように怒られてしまいます. 困りましたね. 困ったので殴って黙らせます.
type Rotations<XS extends readonly unknown[]> = XS extends readonly [] ? XS : RotationsSub<XS, XS, "__hack">; type RotationsSub<XS extends readonly unknown[], L extends readonly unknown[], H extends "__hack"> = L extends readonly [] ? never : XS | { [H0 in H]: RotationsSub<Rotate<XS>, Tail<L>, H> }[H];
こうすると不思議な力で TypeScript がエラーメッセージを吐かなくなります. 時に暴力はすべてを解決する.
動作確認してみるときちんと動いていることがわかります.
type R = Rotations<["A", "B", "C"]>; // R = ["A", "B", "C"] | ["B", "C", "A"] | ["C", "A", "B"]
余談: 無限再帰
ちなみに以下のような単純な無限再帰を書いてみると Inf = unknown となってきちんと止まってくれます.
type Inf = InfSub<"__hack">; type InfSub<H extends "__hack"> = { [H0 in H]: InfSub<H> }[H];
もうちょっと細工をして同じ型が現れないようにすると Type instantiation is excessively deep and possibly infinite. と怒られます.
export type Inf = InfSub<0, "__hack">; type InfSub<X, H extends "__hack"> = { [H0 in H]: InfSub<[X], H> }[H];
置換
さてここまでで準備は整ったので, 置換の union 型を返す Permutations<XS> を作っていきましょう.
まずは第一段階. Permutations<XS> は PermutationsSub<XS, H> に巡回の union 型を与えます.
type Permutations<XS extends readonly unknown[]> = XS extends readonly [] ? XS : PermutationsSub<Rotations<XS>, "__hack">;
既に "__hack" が登場していて胡散臭さがあります.
続いて第二段階. 与えられた巡回の union を最初の conditional で分解して, PermutationsSubSub<XS, YS> に, 分解されたひとつの巡回 (タプル) と, その先頭を除いた残りの置換の union を与えます.
type PermutationsSub<XS, H extends "__hack"> = XS extends readonly unknown[] ? PermutationsSubSub<XS, { [H0 in H]: Permutations<Tail<XS>> }[H]> : never;
XS に上限を書いていないのは意図的で, もし書いてしまうと Type instantiation is excessively deep and possibly infinite. と怒られます. 上限の検査のために型を実体化する必要があるのと関連している気はします.
そして最後. 与えられた置換の union を最初の conditional で分解して, それぞれを XS の先頭 Head<XS> と結合します.
type PermutationsSubSub<XS extends readonly unknown[], YS> = YS extends readonly unknown[] ? { [I in keyof XS]: I extends keyof Cons<Head<XS>, YS> ? Cons<Head<XS>, YS>[I] : never } : never;
ここで YS の上限を書いていないのも同じく意図的です. 結合する部分で単に Cons<Head<XS>, YS> ではなく XS に関する mapped type を使っているのは, XS に元々付いていた readonly 属性を保存する匠の粋な計らいです.
さてこれで欲しかったものが完成しました. 動作確認してみましょう.
type P = Permutations<["A", "B", "C"]>; // P = ["A", "B", "C"] | ["B", "C", "A"] | ["C", "A", "B"] // | ["B", "A", "C"] | ["C", "B", "A"] | ["A", "C", "B"]
よかったですね.
