Возможно вы слышали про Advent of Code — ежегодное соревнование по решению задач на рождественскую тему. Начиная с 1 декабря, вплоть до католического рождества, каждый день выкладывается новая задача. С каждым днем сложность задач возрастает.

В декабре 2023 года впервые проходил Advent of TypeScript — похожее соревнование, но более специфичное, в котором все задачи посвящены написанию типов, согласно условию. В результате решения каждой задачи должен быть написан тип, который что‑то принимает как дженерик параметр, как‑то преобразует этот параметр в другой тип, согласно описанию задания.

Мне было интересно попробовать свои силы в написании сложных типов, потому что на работе зачастую я пишу достаточно простые типы. Я даже не задумывался, что можно написать тип, который будет принимать судоку в формате многомерного массива, и возвращать true или false в зависимости от того, валиден он или нет????

Если хотите попробовать свои силы сами, то задачи все еще доступны. Если вы хотите посмотреть решения задач, то можно посмотреть подборку решений в телеграм канале UfoStation.

В ходе решения задач, я частично открыл / частично вспомнил паттерны и особенности написания типов, которыми хочу поделиться.

Для написания решения задач, нужно описать логику внутри типа. Для этого не помешали бы инструменты из мира рантайма: циклы, условия, функции. Те инструменты, которые мы используем, когда решаем задачи из LeetCode.

В ходе решения задач, я понял, что на самом деле итерироваться, создавать условия и использовать что‑то подобное функциям можно успешно и при решении задач на типы.

С функциями все просто — тип в typescript и является своего рода функцией. Типы умеют принимать параметры-дженерики, работать с ними и возвращать новое выражение в типах.

Условные типы

Теперь перейдем к условиям. В typescript есть специальная конструкция, с помощью которой трансформировать типы по условию — условные типы. Используя их, можно проверить является ли один тип подтипом другого. Тем самым можно создавать связь между инпутом типа и аутпутом типа.

type IsString<T> = T extends string ? "yes" : "no";
type Example1 = IsString<"str"> // "yes"
type Example2 = IsString<10> // "no"

Дистрибутивность условных типов

У условных типов есть особенность: если условие ставится для Union типа из дженерика выражения, то результатом будет юнион из применений выражения для каждого элемента из этого юниона. Таким образом в условных типах реализуется принцип дистрибутивности.

type IsString<T> = T extends string ? "yes" : "no";
type Example = IsString<"str" | 10> 
// то же, что и IsString<"str"> | IsString<10>, "yes" | "no"

Решим одну из задач контеста, использовав свойство дистрибутивности условных типов

Упрощенно условие выглядит следующим образом:

Реализуйте тип, который принимает параметр-объект, а возвращает тот же объект, но без ключей, начинающихся с "naughty_".

Сначала, я реализовал вспомогательный тип, который принимает параметр и если параметр — это строка, которая:

1. начинается с "nautghty_" — возвращает never

2. не начинается с "nautghty_" — возвращает исходный параметр

type FilterKeys<Key> = Key extends `naughty_${string}` ? never : Key;

Передав в этот тип Union из ключей объекта, я использую дистрибутивность и получаю следующую реализацию фильтрации

type FilterKeys<Key> = Key extends `naughty_${string}` ? never : Key;

type FilteredKeys = FilterKeys<keyof {
 naughty_bob: {},
 good_alice: {}
}>
/* то же, что и FilterKeys<"naughty_bob" | "good_alice">
   то же, что и FilterKeys<"naughty_bob"> | FilterKeys<"good_alice">
   то же, что и never | "good_alice"
   то же, что и "good_alice"
*/

Далее используем Mapped Types в комбинации с написанным ранее типом и получаем финальное решение:

type FilterKeys<Key> = Key extends `naughty_${string}` ? never : Key;

type RemoveNaughtyChildren<T extends Record<string, unknown>> = {
 [N in FilterKeys<keyof T>]: T[N]
};

Вывод типов из условных типов

Иногда мы хотим вывести из типа‑параметра какую‑то его составную часть, который мы передали через дженерик. Для этого через условное выражение описываем сам исходный параметр, а перед той частью типа, которую мы не знаем хотим вывести из параметра, ставим infer.

type RemoveHash<Str extends string> = Str extends `#${infer N}` ? N : never;
type Example = RemoveHash<"#123"> // "123"

Можно выводить типы и из других типов. Например, так выводится возвращаемое значение из типа функции

type ReturnType<T extends (...args: any) => any> = T extends 
  (...args: any) => infer R ? R : any;

Итерация элементов

Мы научились работать с условиями, теперь научимся итерироваться. Ведь иногда нам нужно описать логику не для одного элемента а для целого множества элементов, например для элементов массива.

Чтобы итерироваться по массиву, обрабатывать его, я часто использовал конструкцию, которая мне напоминает метод reduce массива, только рекурсивный. Я создавал рекурсивный тип, у которого есть дженерик параметр, в котором хранится аккумулированный тип всех предыдущих рекурсивных операций, а так же есть условие для выхода из рекурсии.

Рассмотрим на практике этот прием на примере реализации типа, с помощью которого можно получить сумму двух числовых типов. Например, у нас есть типы 2 и 3, а мы хотим получить средствами typescript тип суммы — 5. Такой тип который часто был мне необходим для решения задач контеста. Типы в typescript не предполагают операторов для математических операций, но желаемый результат можно получить, работая с массивами.

Первый шаг к сложению двух числовых типов — создание массивов с длинами, равными слагаемым. Рекурсивный тип который, который использует паттерн аккумауляции промежуточного значения следующим образом:

type ArrayByLength<N extends number, A extends any[] = []> = 
  A["length"] extends  N ? A : ArrayByLength<N, [...A, unknown]>;

Первым параметром передаем число, именно такой длины мы хотим получить массив на выходе, Второй параметр — массив‑аккумулятор, куда мы рекурсивно добавляем unknown до тех пор, пока массив не достигнет нужной длины. Когда длина массива‑аккумулятора станет равной параметру — это значит, что мы получили массив нужной длины, поэтому переходим в ту ветку условного типа, где происходит выход из рекурсии и возвращается финальное значение.

Использовав этот тип, можно реализовать легко реализовать сумму

type Sum<A extends number, B extends number> = [
 ...ArrayByLength<A, []>,
 ...ArrayByLength<B, []>,
]["length"];

type Example = Sum<2, 3>; // 5

Для того, чтобы реализовать вычитание сначала создадим вспомогательный тип, который вычитает 1 из числового типа, а потом уже с его помощью реализуем вычитание. Рекурсивно вычитаем из уменьшаемого и вычитаемого 1, до тех пор, как вычитаемое не станет равно 0, в этот момент уменьшаемое будет равно искомой разнице.

type SubtractOne<A extends number> = 
  ArrayByLength<A, []> extends [any, ...infer Other extends any[]] ?
    Other["length"] : A;


type Subtract<A extends number, B extends number> = B extends 0 ?
  A : Subtract<SubtractOne<A>, SubtractOne<B>>;

type Example = Subtract<5, 2>; // 3

Итоги

Подводя итоги, я получил удовольствие, решая Advent of TypeScript и рекомендую всем, кто хочет проверить свои силы. Правда, ближе к концу, задачи становятся, на мой взгляд, немного однотипными, и уж очень далекими от реальной разработки. Тем не менее, решение этих задач было приятным вызовом для меня, а сам формат стимулировал соревнования стимулировал пройти все до конца. Буду ждать новые задачи в конце 2024:)

Полезные ссылки

Advent of Code

Advent of TypeScript 

Итоги, варианты решений и объяснения конкретных задач

Про условные типы

Про дистрибутивность

Про Mapped Types