Завдання

Дано масив унікальних елементів, поверніть всі можливі підпослідовності.

Підпослідовність — це послідовність, яку можна вивести з масиву шляхом видалення деяких або жодних елементів без зміни порядку елементів, що залишилися. Наприклад:

type A = Subsequence<[1, 2]>; // [] | [1] | [2] | [1, 2]

Розв’язок

Це завдання було справді складним. Вирішуючи його, я згадав ще одне, досить схоже на це – Permutation. Там ми використовували рекурсію з варіативними типами, щоб створити фрагменти кортежу. Але давайте зосередимося на нашій проблемі та будемо вирішувати її крок за кроком.

Як завжди, я почну з порожнього типу, який нам потрібно реалізувати:

type Subsequence<T extends any[]> = any;

Завдання здається досить великим, тому я пропоную спочатку розділити його на менші завдання. Пішовши шляхом “розділяй і володарюй”, буде легше реалізувати тип.

Припустимо, у нас є кортеж з одним елементом всередині. Щоб отримати його значення, ми можемо використати умовний тип:

type Subsequence<T extends any[]> = T extends [infer I] ? never : never;

Якщо тип-параметр T матиме кортеж з одним елементом, його буде виведено в тип-параметр I. Таким чином ми отримуємо елемент із кортежу та можемо його повернути:

type Subsequence<T extends any[]> = T extends [infer I] ? I : never;

А якщо в кортежі елементів немає, ми можемо повернути порожній кортеж:

type Subsequence<T extends any[]> = T extends [infer I] ? I : [];

За допомогою цього типу ми можемо обробляти кортежі без елементів або з одним елементом. Однак, як тільки ми додаємо ще один елемент до вхідного кортежу, все стає складніше. Наш умовний тип не оброблятиме більше одного елемента, тому давайте виведемо решту кортежу в тип-параметр R:

type Subsequence<T extends any[]> = T extends [infer I, ...infer R] ? I : [];

На цьому етапі ми розбиваємо вхідний кортеж на перший елемент у тип-параметрі I, та решту — у тип-параметрі R.

Відповідно до специфікації завдання, нам потрібно повернути підпослідовності в кортежах. Тож, ми обертаємо I в кортеж:

type Subsequence<T extends any[]> = T extends [infer I, ...infer R] ? [I] : [];

Без рекурсії ми маємо одну підпослідовність, але нам також потрібно включити інші підпослідовності з решти кортежу. Для цього ми викликаємо той самий тип рекурсивно, для решти кортежу, без елемента в I:

type Subsequence<T extends any[]> = T extends [infer I, ...infer R]
  ? [I, ...Subsequence<R>]
  : [];

Залишилося додати інші послідовності як частину типу об’єднання, щоб ми отримали всі варіанти:

type Subsequence<T extends any[]> = T extends [infer I, ...infer R]
  ? [I, ...Subsequence<R>] | Subsequence<R>
  : [];

Давайте підсумуємо те, що ми тут маємо, по кожному випадку:

  • Коли T порожній, наш умовний тип поверне порожній кортеж.
  • Коли T матиме один елемент, то цей елемент буде виведено в тип-параметр I, тоді як R буде порожнім кортежем. Рекурсивний виклик типу з порожнім кортежем поверне порожній кортеж, як описано в попередньому пункті.
  • Коли T матиме більше одного елементу, він, по суті, розбиває кортеж на підкортежі та рекурсивно передає їх, доки не отримаємо один із двох основних випадків, наведених вище. Результат буде об’єднано разом у кінцевому типі.

Таким чином ми реалізували тип для отримання підпослідовностей кортежу.

Посилання