🧩

React で配列のソートや絞り込みをしたいあなたへ〜型パズルを添えて〜

2022/05/05に公開

1件

🪝 What's this?

一言で書くなら、「React で複雑なソートや絞り込みを簡単に記述できるカスタムフック」 です。

少し詳しく書くと、以下のような機能があります。

任意の絞り込み条件を容易に AND, OR で繋ぐことができる
絞り込み・ソート条件を複数重ねることができる
これらを型安全に行う

以下のようなユースケースを想定しています。

フロント側でインタラクティブに配列の絞り込みやソートを行いたい
条件 A と B については　AND 条件で絞り込みたいが、条件 C と D については　OR 条件で絞り込みたい

特に二つ目のような複雑な絞り込み処理を簡単に実装することができるライブラリになっています。

とはいえ、配列操作自体に技術的に特に難しい話はないので、以降ではこのライブラリの開発時に解いた型パズルについて書きたいと思います。（結局この型パズルが使われることはなかったので供養も兼ねて）

🧩 型パズル

問題

String リテラルの Union Type を受け取り、その任意の要素を 'or' で繋いだ型を作ってください

type OR<T extends string> = ...
type Key = 'A' | 'B' | 'C'
type OrKey = OR<Key> // 'A' | 'B' | 'C' | 'AorB' | 'AorC' | 'BorA' | 'BorC' | 'CorA' | 'CorB' | 'AorBorC' | 'AorCorB' | 'BorAorC' | 'BorCorA' | 'CorAorB' | 'CorBorA'

解法を2つ用意しています✌️
それぞれの解法において小問を設置しているので、少しずつこの大問を攻略していきましょう👍

（追記）加えて、コメントにて最もエレガントな解法をいただきましたので解法1の最後に掲載しています

解法1

小問1: Union 要素の全ての順列を配列化する

type Permutation<T> = ...
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 extends string, U extends string = T> = [T] extends [never]
  ? []
  : T extends T
  ? [T, ...Permutation<Exclude<U, T>>]
  : never;

最初にして最大の鬼門ですね（笑）
実は Type-Challenge に全く同じ問題があります。

ここではざっくりと解説をします（より詳細については英語で書かれているこちらをお読みください）

流れとしては、 T が Union であることを踏まえ、条件節(foo extends bar部分)でそれを分配して1つの要素だけを配列の最初に固定し、配列の残りは再帰的に処理する、というものです。

まず最初の [T] extends [never] では、 T が　never かどうかのチェックを行っています。わざわざ [] で囲っているのは条件節に never が来ると問答無用で結果が never になってしまうためです。条件節における Union の分配についてよく知らない方はこちらの記事がわかりやすいです。

次の T extends T では、引数の Union をあえて分配しています。（'A'|'B'|'C' がここに来ると、この文以降の T は 'A' や　'B' などの分配された要素になります）。そして、 Permutation の型引数の第二引数に U = T を追加しているのは、 T が分配されてしまった後でも、分配前の Union を使いたいためです。この不思議な記法の詳細については手前味噌ですがこちらの記事で詳しく解説しています。

小問2: Union 要素の任意の要素の順列を配列化する

type ArbitraryPermutation<T> = ...
ArbitraryPermutation<"A"|"B"|"C"> // ["A"] | ["B"] | ["C"] | ["A", "B"] | ["A", "C"], ... , ["A", "B", "C"] | ["A", "C", "B"], ...

解説

type ArbitraryPermutation<T extends string, U extends string = T> = [T] extends [never]
  ? never
  : Permutation<T> | (T extends T ? ArbitraryPermutation<Exclude<U, T>> : never);

Union を条件節で分配しながら、任意の Union に対して再帰的に　Permutation を呼びましょう。
小問1 で使ったテクニック（ never 判定, Union の分配）を分かっていれば理解できるはずです！

小問3: 配列内の要素を 'or' で結合する

type JoinWith<T, U> = ...
JoinWith<["A", "B", "C"], "or"> // "AorBorC"

解説

type JoinWith<T extends string[], U extends string> = T extends [infer Head, ...infer Rest]
  ? Rest['length'] extends 0
    ? Head
    : Head extends string
    ? Rest extends string[]
      ? `${Head}${U}${JoinWith<Rest, U>}`
      : ''
    : never
  : never;

流れとしては、 infer を使って配列を分解し、初めの要素と残りを 'or' でつなげ、その残りの要素については再帰的に処理を行なっておく、というものです。

infer は条件節においてのみ使えるキーワードで、 ... と併用することで配列型や文字列リテラルを型の世界で分解して命名し、それ以降の型処理で使うことができます。

Rest['length'] extends 0 ? Head の部分がこの型関数の基底部にあたります。
Rest が空配列になる時、つまり、 T が長さ1の配列で Head に要素が割り当てられ、 Rest は空配列の型になる時、にその中身を返しています。

小問4: 1~3 を組み合わせて Union の任意の要素を or で結合する

type OR<T> = ...
OR<"A"|"B"|"C"> // "A" | "B" | "C" | "BorC" | "CorB" | "AorBorC" | "AorCorB" | "AorC" | "CorA" | "BorAorC" | "BorCorA" | "AorB" | "BorA" | "CorAorB" | "CorBorA"

解答例

type OR<T extends string, P = ArbitraryPermutation<T>> = [T] extends [never]
  ? never
  : P extends P
  ? P extends string[]
    ? JoinWith<P, 'or'>
    : never
  : never;

いよいよ完成です🎉
Union の任意の要素を含む配列を作成し、それぞれに対して小問3で作成した型を作用させましょう！

最終版はこちら

別解

コメントにて最もエレガントな解法を教えていただきました🙏
ここまで解説を読んでくださった方は理解できるはずです！

答え

type OR<T extends string, U extends string = T> = T extends T
  ? T | `${T}or${OR<Exclude<U, T>>}`
  : never;

解法2

小問1: Union の要素全てを or で繋いだ型を作る

type JoinedWithOR<T> = ...
JoinedWithOR<"A"|"B"|"C"> // "AorBorC" | "AorCorB" | "BorAorC" | "BorCorA" | "CorAorB" | "CorBorA"

解説

type JoinedWithOR<T extends string, U extends string = T> = [T] extends [never]
  ? never
  : T extends T
  ? [Exclude<U, T>] extends [never]
    ? T
    : `${T}or${JoinedWithOR<Exclude<U, T>>}`
  : never;

解法1で培った知識があれば容易に理解できると思います！
ちなみに [Exclude<U, T>] extends [never] が真の時に T を返しているのは、これがないと AorBorCor　のように最後にも or がついてしまうためです。

小問2: Union の要素を指定した個数だけ繋いだ型を作る

type OrKeyOfLength<T, U> = ...
OrKeyOfLength<"A"|"B"|"C", 2> // "AorB" | "AorC" | "BorA" | "BorC" | "CorA" | "CorB"

解説

type ArrayOfLength<N extends number, C extends any[] = []> = C['length'] extends N
  ? C
  : ArrayOfLength<N, [...C, any]>;

type Minus<N extends number> = ArrayOfLength<N> extends [any, ...infer Rest]
  ? Rest['length']
  : never;
 
type OrKeyOfLength<T extends string, Length extends number, U extends string = T> = [T] extends [
  never,
]
  ? never
  : Length extends 1
  ? T
  : T extends T
  ? [Exclude<U, T>] extends [never]
    ? `${T}`
    : `${T}or${OrKeyOfLength<Exclude<U, T>, Minus<Length>>}`
  : never;

少し複雑になってきましたね。やっていること自体はシンプルで、先ほど作った "or" でつなぐ再帰的な型を改良し、再帰を行う回数を制限するだけです。

ただ、 TypeScript の型の世界で直接数字を減らしたり増やしたりすることはできません。 型の世界においては number リテラルの 1 という型と 2 という型に大小関係は存在しないからです。

そこで、型の世界における数字のインクリメントやデクリメントなどは、配列の長さを使って行うことが多いです。数字の 1 を長さ　1　の配列として扱い、その配列の要素数を増減させて数字のインクリメント、デクリメントを扱います。

上記のコードでは次のように処理を行なっています。

ArrayOfLength : 受け取った数字と同じ長さの配列を作成する
Minus : 受け取った配列の長さを 1 減らす

小問3: Union の要素数以下の非負整数の Union を返す型を作る

type LTEUnionLength<T> = ... // LTE : Less Than or Equal to
LTEUnionLength<"A"|"B"|"C"> // 0 | 1 | 2 | 3

解説

type UnionLength<T, Length extends any[] = [], U = T> = [T] extends [never]
  ? Length['length'] // ここで配列の長さを返す
  : T extends T
  ? UnionLength<Exclude<U, T>, [...Length, any]>
  : never;

type LTEUnionLength<T, U = T> = [T] extends [never]
  ? 0
  : T extends T
  ? UnionLength<U> | LTEUnionLength<Exclude<U, T>>
  : never;

流れとしては Union の要素数を求める型　UnionLength を作り、それを再帰的に使っていくというものです。
ここでも先ほどの小問2で出てきた数字を配列の長さとして扱うテクニックが出てきます。

小問4: 1~3 をもとに、 Union の任意の要素を or で結合する

type OR<T> = ...
OR<"A"|"B"|"C"> // Key | "AorB" | "AorC" | "BorA" | "BorC" | "CorA" | "CorB" | "AorBorC" | "AorCorB" | "BorAorC" | "BorCorA" | "CorAorB" | "CorBorA"

解説

type OR<T extends string> = OrKeyOfLength<T, LTEUnionLength<T>>;

今までのものを組み合わせるだけです！

最終版はこちら

パズルを終えて

詳しく説明しきれていない部分があったかと思いますが、型パズルを解く上での流れをふんわり掴んでいただけたら嬉しいです。
他にもこんな解法あるよ、という方いらっしゃいましたらコメント欄にてご教授くださいませ🙏

終わりに

いかがでしたでしょうか？
本編が型パズルになってしまいましたが、ライブラリの方も気が向いたら触っていただけると嬉しいです。

Discussion

malt03

misogohan さんの解法が最高にエレガントなので蛇足になってしまいますが、UnionをTupleに変換することで OR<"A"|"B"> = "A" | "B" | "AorB" を実現してみました！
TuplifyUnion はStackoverflowをコピペしてきていますが、コピペ元にも書いてあるとおりUnionを非対称に扱うのは未定義動作であり非推奨ですが、パズルということで…。
プロダクションコードであれば OR<["A", "B", "C"]> のように使える型を定義することになりそうです。

type UnionToIntersection<U> = (U extends any ? (k: U) => void : never) extends ((k: infer I) => void) ? I : never;
type LastOf<T> = UnionToIntersection<T extends any ? () => T : never> extends () => (infer R) ? R : never;
type Push<T extends any[], V> = [...T, V];
type TuplifyUnion<T, L = LastOf<T>, N = [T] extends [never] ? true : false> = true extends N ? [] : Push<TuplifyUnion<Exclude<T, L>>, L>;

type Combinations<T extends any[], U extends any[] = []> = T extends [infer R, ...infer S] ? [...Combinations<S, U>, ...Combinations<S, [...U, R]>] : [U];
type Join<T extends string[]> = T extends [string] ? T[0] : T extends [string, ...infer R] ? R extends string[] ? `${T[0]}or${Join<R>}` : never : never;
type JoinAll<T extends string[][]> = { [K in keyof T]: T[K] extends string[] ? Join<T[K]> : never };
type JoinAllCombinations<T> = T extends string[] ? JoinAll<Exclude<Combinations<T>, []>> : never;
type OR<T extends string> = JoinAllCombinations<TuplifyUnion<T>>[number];

type Answer = OR<"A" | "B" | "C">; // "A" | "B" | "C" | "BorC" | "AorC" | "AorB" | "AorBorC"