Складываем числа в системе типов Typescript

Недавно я участвовал в соревновании Yandex Cup, где одним из заданий в треке фронтенд-разработки было решить некую задачку полностью в рамках системы типов Typescript. Я очень люблю тайпскрипт в целом и его систему типов в частности, поэтому на это задание я потратил значительную часть всего времени. Что там было — совсем другая история, но именно тогда мне пришла идея написать свой сумматор на типах.

Вместо этого я решил взять за основу десятичную систему и алгоритм сложения столбиком. Что ж, начнём!

Нам нужно реализовать тип, который принимает на вход два числа, а на выход выдаёт ещё одно число — сумму.

Сначала нужно превратить числа в строки, а строки разбить на отдельные цифры. Это, пожалуй, единственный способ удобной работы с числами в TS, ведь никаких арифметических операций в системе типов нет.

type StringToChars<T extends string> = T extends `${infer C}${infer Rest}`
  ? [C, ...StringToChars<Rest>]
  : [];
type NumToChars<T extends number> = StringToChars<`${T}`>;

Для преобразования числа в строку мы используем подстановку в template literal. А вот для разбиения строки на символы пригодится рекурсия и немного infer-магии. Простыми словами можно описать так:

• на каждом шаге мы проверяем, представляет ли строка из себя нечто формата `${первый символ}${всё остальное}` (причём всё остальное может быть пустой строкой)
• если да, то возвращаем первый символ и результат разбиения оставшейся строки (которая возвращает второй символ и результат разбиения оставшейся строки и так далее)
• если нет, то возвращаем пустой массив (это нужно для завершения рекурсии, когда строка пустая)

Теперь из числа 12345 мы можем получить кортеж цифр ["1", "2", "3", "4", "5"]. Дальше вспоминаем алгоритм сложения столбиком: числа нужно записать так, чтобы одинаковые разряды оказались друг над другом. В нашем случае — чтобы одинаковые разряды была на одинаковых позициях в кортеже. Как бы сделать так, чтобы цифра 5 в числе 12345 была на том же месте, что и 8 в 678? Развернуть массив!

Для этого опять используем infer и рекурсию:

type Reverse<T extends any[]> = T extends [infer V, ...infer Rest]
  ? [...Reverse<Rest>, V]
  : [];

Reverse<NumToChars<12345>> даст нам ["5", "4", "3", "2", "1"], а Reverse<NumToChars<678>> — ["8", "7", "6"]. Как видите, разряды действительно совпадают.

Теперь нужно научиться складывать две цифры. Для этого я написал маленький скриптик, который генерирует look-up table:

for (let i = 0; i <= 9; ++i) {
  console.log(`A extends '${i}' ? (`)
  for (let j = 0; j <= 9; ++j) {
    console.log(`B extends '${j}' ? [${i + j >= 10 ? `'${(i+j) % 10}', true`: `'${i+j}', false`}] :`)
  }
  console.log('never) :')
}
console.log('never')

Результат выглядит примерно так:

type AddDigitsCore<A extends string, B extends string> = A extends "0" ? (
    B extends "0" ? ["0", false]
      : B extends "1" ? ["1", false]
      : B extends "2" ? ["2", false]
      // тут ещё 100 строчек…

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

Как добавлять единичку? Тут мне пришлось написать маленький костыль, потому что переделывать по-нормальному мне было лень.

type AddOne<T extends [string, boolean]> = [
  AddDigitsCore<T[0], "1">[0],
  AddDigitsCore<T[0], "1">[1] extends true ? true : T[1],
];

Тип принимает на вход кортеж из символа и индикатора переполнения и отдаёт такой же кортеж на выход. Символ — это результат прибавления единички к входному символу. А вот для индикатора переполнения написано условие. Если он равен true, то возвращаем true. Иначе возвращаем то, что было передано на вход. Выглядит не очень красиво, но работает, и вот почему:

1. Если на вход передаётся число с переполнением (например 12, то есть ["2", true]), то на выходе переполнение остаётся (получается 13, то есть ["3", true])
2. Переполнения переполнения случиться не может, потому что максимальное число на входе — это 9+9, то есть 18
3. Если на вход передаётся число от 0 до 8, то переполнения не появляется
4. Единственный случай, когда появляется переполнение — когда передаётся 9 (["9", false] => ["0", true])

Теперь напишем тип для сложения двух цифр, но с учётом возможной «единички»:

type AddDigits<
  A extends string,
  B extends string,
  Leftover extends boolean = false,
> = Leftover extends true ? AddOne<AddDigitsCore<A, B>> : AddDigitsCore<A, B>;

Тут всё просто: если Leftover = true, то складываем цифры и добавляем единичку; если нет, то просто складываем цифры.

Дальше напишем ещё несколько типов, которые пригодятся нам позже.
Первый — это тип Shift, который удаляет первый элемент из кортежа.

type Shift<T extends any[]> = ((...v: T) => void) extends
  ((v: any, ...rest: infer V) => void) ? V : [];

Я не очень понимаю, зачем тут используются сигнатуры функций, но без них что-то ломается. В общем, тип «проглатывает» первый элемент, а все остальные возвращает обратно. Если массив и так пустой, то просто возвращает пустой массив.

Второй — это тип FallbackToZero, тут всё очевидно.

type FallbackToZero<T extends string | undefined> = T extends undefined ? "0" : T;

Теперь подумаем о том, как бы нам реализовать алгоритм сложения. Шаги должны быть такие:

1. Сложить два числа в текущем разряде (не забыть про возможную «единичку» сверху)
2. Записать последнюю цифру результата в ответ
3. Запомнить «единичку» (если она есть) для следующего разряда
4. Перейти к следующему разряду

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

type AddCore<
  A extends string[],
  B extends string[],
  Leftover extends boolean = false,
> = true extends (
  & (A[0] extends undefined ? true : false)
  & (B[0] extends undefined ? true : false)
) ? Leftover extends true ? "1" : ""
  : `${AddCore<
    Shift<A>,
    Shift<B>,
    AddDigits<
      FallbackToZero<A[0]>,
      FallbackToZero<B[0]>,
      Leftover
    >[1]
  >}${AddDigits<
    FallbackToZero<A[0]>,
    FallbackToZero<B[0]>,
    Leftover
  >[0]}`;

Давайте разбираться, что тут происходит. На вход приходит два числа (в виде массива символов в обратном порядке) и индикатор «единички». Для первого разряда он всегда false, но для следующих итераций пригодится.

AddDigits<
  FallbackToZero<A[0]>,
  FallbackToZero<B[0]>,
  Leftover
>[0]

Тут мы получаем цифру, которая идёт в ответ.

AddCore<
  Shift<A>,
  Shift<B>,
  AddDigits<
    FallbackToZero<A[0]>,
    FallbackToZero<B[0]>,
    Leftover
  >[1]
>

Тут мы запускаем рекурсию для следующего разряда. В Leftover передаётся индикатор переполнения из результата сложения текущего разряда. Из чисел убирается по одной цифре с помощью метода Shift. С каждой итерацией остаётся всё меньше и меньше цифр. Если одно число короче другого, то в один момент у него закончатся цифры, и A[0] (или B[0]) вернёт undefined. Тут пригождается FallbackToZero, который заменяет undefined на "0".

true extends (
  & (A[0] extends undefined ? true : false)
  & (B[0] extends undefined ? true : false)
) ? Leftover extends true ? "1" : ""

Тут мы проверяем, не закончились ли у нас разряды у обоих чисел сразу. Если так, то мы завершаем рекурсию и возвращаем 1, если у нас осталась «единичка», либо пустую строку.

В результате у нас получается сумма чисел в виде строки. Никаких дополнительных манипуляций с ней производить не нужно, она уже записана в правильном порядке (старший разряд слева). Можно было попытаться возвращать результат в виде числа, но я не смог придумать оптимальный способ конвертации символов в число.

Ну и наконец делаем юзер-френдли тип, который принимает на вход два числа, конвертирует их в обратный массив символов и вызывает AddCore

type Add<A extends number, B extends number> = AddCore<
  Reverse<NumToChars<A>>,
  Reverse<NumToChars<B>>
>;

Готово! Потыкать можно в песочнице посмотреть код — на гитхабе.

Подписывайтесь на мой телеграм-канал, ставьте лайки, до связи!