Усовершенствованный машинописный текст: конвертер уровня десятичного числа в двоичный

Как я реализовал конвертер с основанием 10 в основание 2, используя только типы!

Я всегда хочу улучшить свои навыки работы с Typescript, и лучший способ сделать это — бросить себе вызов, поэтому пару дней назад я подумал: могу ли я сделать конвертер десятичных чисел в двоичные на уровне типов в Typescript?

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

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

🎉 Результат

Если вас просто интересует решение, то вот оно:

type CastNumber<N extends unknown> = N extends number ? N : never;

type Length<A extends unknown[]> = CastNumber<A["length"]>;

type NumberToArray<
  N extends number,
  Acc extends unknown[] = []
> = N extends Length<Acc> ? Acc : NumberToArray<N, [...Acc, unknown]>;

type Increment<N extends number> = Length<[...NumberToArray<N>, unknown]>;

type Decrement<N extends number> = NumberToArray<N> extends [
  unknown,
  ...infer Rest
]
  ? Length<Rest>
  : 0;

type Sub<L extends number, R extends number> = R extends 0
  ? L
  : Sub<Decrement<L>, Decrement<R>>;

type DivBy2<
  Dividend extends number,
  Quotient extends number = 0
> = Dividend extends 0
  ? [0, Quotient]
  : Dividend extends 1
  ? [1, Quotient]
  : DivBy2<Sub<Dividend, 2>, Increment<Quotient>>;

type ToBinary<N extends number, Result extends string = ""> = N extends 0
  ? Result
  : N extends 1
  ? `1${Result}`
  : DivBy2<N> extends [
      infer Remainder extends 0 | 1,
      infer Quotient extends number
    ]
  ? ToBinary<Quotient, `${Remainder}${Result}`>
  : never;

type BinaryNumber = ToBinary<2>; // 10

Не стесняйтесь копировать и вставлять это решение и экспериментировать с ним.
Хотя, если вы не понимаете, что происходит, в оставшейся части статьи я объясню, как я пришел к этому решению.

🗒 Объяснение решения

Прежде чем перейти к объяснению, чтобы четко понять его, вам необходимо иметь базовые знания некоторых понятий, в частности:

Условные типы
Вывод
Кортежи
Немного математики

Если вы знакомы с этими понятиями, можете идти — в противном случае, я надеюсь, что примеры помогут вам понять, что происходит, но я настоятельно рекомендую перейти по ссылкам и прочитать документацию, это не ракетостроение 😉

Теория

Вы знаете, как преобразовать число из 10 в основание 2?

На самом деле это довольно просто, нам просто нужно разделить на 2 столько, сколько возможно, и сохранить остаток от всех этих делений.
Давайте сделаем пример и преобразуем число 10 из числа 10 в основание 2:

10 разделить на 2 равно 5 без остатка:

Сохраним остаток, это будет последняя цифра числа по основанию 2.
Теперь продолжим делить на 2 частное:

5 разделить на 2 равно 2 с напоминанием 1.
Как и раньше, мы сохраняем напоминание и помещаем его как предпоследнюю цифру числа в базе 2.
Теперь давайте двигаться к следующему шагу:

2 разделить на 2 равно 1 без остатка, снова сохраняем остаток и переходим к последнему шагу:

Наконец-то у нас есть наш номер! Частное последнего деления равно 0, что означает, что мы можем остановиться здесь.

Мы все еще не готовы кодировать! В программировании одна из самых важных вещей — разбивать большие задачи на маленькие, поэтому, прежде чем начать, мы должны понять, что делать:

Как и следовало ожидать, реальная проблема заключается в следующем: как выполнять математику только с типами Typescript?

Ответ не такой тривиальный, потому что есть много способов сделать это.
В этой статье я покажу вам один подход, основанный на массивах, который охватывает только естественные цифры — но вернемся к проблеме:

Нам нужен способ деления, но что такое деление? Мы можем видеть это как количество раз, которое нам нужно вычесть делитель из делимого, чтобы получить ноль (если они не делятся, это не совсем так, но да ладно... вы умеете делить 😀 сразу к делу!:

Чтобы делить, нам нужно знать, как делать две вещи: увеличивать (для подсчета количества вычитаний) и вычитать.
Но что такое вычитание, как не последовательность убывания?

Итак, чтобы выполнить деление, нам нужно знать только две основные операции: возрастание и убывание.

Теперь, когда мы знаем математику, стоящую за этим, мы можем начать программировать 🤓.

К сожалению, мы не можем выполнять математические операции с типами:

type Three = 3;
type Four = 4;
// Error: 'Four' only refers to a type, but is being used as a value here.
type Seven = Three + Four;

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

Все мое решение основано на массивах (в частности, на кортежах) и, в частности, на их свойстве length :

type MyArray = ['hello', 'world'];

type MyArrayLength = MyArray["length"]; // 2

length, также на уровне типа, указывает размер массива.

Еще одна важная вещь, которую нужно знать, это то, что мы можем (как бы) сравнивать числа на уровне типа, используя extends — мы не можем знать, больше ли одно, чем другое, но, по крайней мере, мы можем знать, равны ли они:

type AreNumbersEqual<
  L extends number,
  R extends number
> = L extends R ? true : false;

type Test_1 = AreNumbersEqual<2, 3>; // false
type Test_2 = AreNumbersEqual<3, 2>; // false
type Test_3 = AreNumbersEqual<3, 3>; // true

Последнее, что нужно знать перед началом, это то, что оператор распространения работает также на уровне типа!

type Array1 = ['Hello'];
type Array2 = ['World'];

type Result = [...Array1, ', ' , ...Array2]; // ['Hello', ',', 'World'];

Обратите внимание, что, поскольку мы можем объединять кортежи, мы можем выполнять некоторые математические операции:

type Array1 = ['Hello'];
type Array2 = ['My', 'Friend'];

type Length1 = Array1['length']; // 1
type Length2 = Array2['length']; // 2

type Merge = [Array1, ...Array2]; // ['Hello', 'My', 'Friend'];
type MergeLength = Merge['length']; // 3 = 1 + 2

Мы можем сделать все, используя только эти 3 концепции, хотите верьте, хотите нет!

Увеличение

Начнем с создания первой версии типа Increment, которая для заданного массива размером N будет определять тип, равный N+1:

type Increment<A extends unknown[]> = [...A, unknown]['length']; 

type Result = Increase<['Hello']>; // 2;

На самом деле это не то, чего мы хотим, но мы близки к этому... нам не хватает способа преобразоватьчисло в массив, который имеет тот же размер, что и значение числа, если мы можем это сделать. это, то определение типа Increment будет простым:

type Increment<N extends number> = [...NumberToArray<N>, unknown]['length'];

type Result = Increase<2>; // 3 --> [...[unknown, unknown], unknown]['length']

Итак… давайте построим этот новый тип!

type NumberToArray<
  N extends number,
  Acc extends unknown[] = []
> = N extends Acc['length']
    ? Acc
    : NumberToArray<N, [...Acc, unknown]>;

type Result = NumberToArray<4>; // [unknown, unknown, unknown, unknown]

Давайте визуализируем, как это работает, с небольшой анимацией:

По сути, мы добавляем «элемент» в массив Acc (накопитель) до тех пор, пока его длина не станет равной числу N.

Уменьшение

Мы будем строить typeDecrement с помощью вывода типов, идея следующая:

Учитывая непустой массив длины N, мы можем рассматривать его как объединение массива длины 1 и одного массива длины N-1,если только N = 1, в этом случае я не могу разбить массив на 2 непустых массива.

Давайте переведем эту идею на Typescript:

type Decrement<
  N extends number
> = NumberToArray<N> extends [unknown, ...infer Rest]
  ? Rest['length']
  : 0; // In case N is 1 the result is 0 (1 - 1)

Если что-то непонятно, надеюсь, небольшая анимация поможет вам понять, что происходит:

вычитание

Этот тип довольно прост, так как мы знаем, как уменьшать:

type Sub<
  L extends number,
  R extends number
> = R extends 0
  ? L
  : Sub<Decrement<L>, Decrement<R>>;

Это работает следующим образом:

Имея 2 числа LиR, если R равно 0, мы возвращаем L, если нет, то уменьшаем оба числа и рекурсивно вызываем тип.
Например. :

type Result = Sub<4, 1>;

Будет решаться так:

// 1st step
type Result = 1 extends 0 ? 4 : Sub<Decrement<4>, Decrement<1>>;
// 2nd step
type Result = 1 extends 0 ? 4 : Sub<3, 0>;
// 3rd step
type Result = 1 extends 0 
  ? 4 
  : 0 extends 0 // this is true
     ? 3  // <---
     : Sub<Decrement<3>, Decrement<0>>;
// 4th step
type Result = 1 extends 0 ? 4 : 3;
// 5th step
type Result = 3; // 4 - 1

Разделение на 2

Мы близки к окончательному решению, нам не хватает последней фундаментальной операции: деления, в частности, деления на 2.

Чтобы преобразовать число с основанием 10 в основание 2, нам нужен как остаток (который может быть только нулем или единицей), так и частное от деления.
Зная это, давайте создадим тип DivBy2 таким образом, чтобы обеспечить оба :

type DivBy2<
  Dividend extends number,
  Quotient extends number = 0
> = Dividend extends 0
  ? [0, Quotient]
  : Dividend extends 1
  ? [1, Quotient]
  : DivBy2<Sub<Dividend, 2>, Increment<Quotient>>;

Чтобы пояснить его реализацию, приведем пример:

type Result = DivBy2<5, 2>;
// 1st step
type Result = 5 extends 0
  ? [0, 0]
  : 5 extends 1
    ? [1, 0]
    : DivBy2<Sub<5, 2>, Increment<0>>;
// 2nd step
type Result = 5 extends 0
  ? [0, 0]
  : 5 extends 1
    ? [1, 0]
    : 3 extends 0
      ? [0, 1]
      : 3 extends 1
        ? [1, 1]
        : DivBy2<Sub<3, 2>, Increment<1>>;
// 3rd step
type Result = 5 extends 0
  ? [0, 0]
  : 5 extends 1
    ? [1, 0]
    : 3 extends 0
      ? [0, 1]
      : 3 extends 1
        ? [1, 1]
        : 1 extends 0
          ? [0, 2]
          : 1 extends 1 // This is true
            ? [1, 2] // Here we stop
// 4th step
type Result = [1, 2] // Where 1 is the remainder and 2 is the quotient.
// In fact 5 : 2 = 2 with a remainder of 1.

Конвертер

Наконец-то у нас есть все необходимые типы для создания нашего конвертера:

type ToBinary<
  N extends number,
  Result extends string = ""
> = N extends 0
  ? Result
  : N extends 1
  ? `1${Result}`
  : DivBy2<N> extends [
      infer Remainder extends 0 | 1,
      infer Quotient extends number
    ]
  ? ToBinary<Quotient, `${Remainder}${Result}`>
  : never;

Вот как работает этот тип:

Учитывая любое число N

В случае, если N равно нулю, возвращает значение аккумулятора
Если N равно 1, возвращается значение аккумулятора с префиксом 1.
В противном случае он вычисляет результат DivBy2 заданного числа и получает кортеж [Remainder, Quotient]
Тип вызывается рекурсивно на Quotient, а аккумулятор имеет префикс Remainder.

Приведем и такой пример:

type Result = ToBinary<3>;
// Step 1
type Result = 3 extends 0
  ? ''
  : 3 extends 1
    ? '1'
    : DivBy2<3> extends [1, 1]
      ? ToBinary<1, `${'1'}${''}`>
      : never;
// Step 2
type Result = 3 extends 0
  ? ''
  : 3 extends 1
    ? '1'
    : DivBy2<3> extends [infer Remainder, infer Quotient]
      ? 1 extends 0
         ? '1'
         : 1 extends 1 // This is true
           ? `1${'1'}` // Will stop here
           : DivBy2<1> extends [1, 0]
             ? ToBinary<0, `${'1'}${'1'}`>
             : never;
      : never;
// Step 3
type Result = '11'; // ToBinary<3>

Давайте соберем все вместе:

type CastNumber<N extends unknown> = N extends number ? N : never;

type Length<A extends unknown[]> = CastNumber<A["length"]>;

type NumberToArray<
  N extends number,
  Acc extends unknown[] = []
> = N extends Length<Acc> ? Acc : NumberToArray<N, [...Acc, unknown]>;

type Increment<N extends number> = Length<[...NumberToArray<N>, unknown]>;

type Decrement<N extends number> = NumberToArray<N> extends [
  unknown,
  ...infer Rest
]
  ? Length<Rest>
  : 0;

type Sub<L extends number, R extends number> = R extends 0
  ? L
  : Sub<Decrement<L>, Decrement<R>>;

type DivBy2<
  Dividend extends number,
  Quotient extends number = 0
> = Dividend extends 0
  ? [0, Quotient]
  : Dividend extends 1
  ? [1, Quotient]
  : DivBy2<Sub<Dividend, 2>, Increment<Quotient>>;

type ToBinary<N extends number, Result extends string = ""> = N extends 0
  ? Result
  : N extends 1
  ? `1${Result}`
  : DivBy2<N> extends [
      infer Remainder extends 0 | 1,
      infer Quotient extends number
    ]
  ? ToBinary<Quotient, `${Remainder}${Result}`>
  : never;

Вы можете видеть, что здесь у нас есть 2 дополнительных типа:

type CastNumber<N extends unknown> = N extends number ? N : never;

type Length<A extends unknown[]> = CastNumber<A["length"]>;

Length — это просто служебный тип, который я использую вместо того, чтобы писать Array["length"] каждый раз.
Вместо этого используется CastNumber, потому что по по какой-то причине компилятор жаловался, что Array[“length”] может быть не числом (не могу себе представить, когда тбх), поэтому, используя тип Length, я уверен, что всегда получаю число. Машинописный мат.

Еще кое-что.

Я хотел добавить к этой статье еще кое-что.
С созданными нами типами мы можем построить намного больше — позвольте мне привести несколько примеров:

Дополнение

type Add<L extends number, R extends number> = Length<
  [...NumberToArray<L>, ...NumberToArray<R>]
>;


type Result = Add<8, 2>; // 10

Умножение

type Mul<
  L extends number,
  R extends number,
  Result extends number = L
> = R extends 0
  ? 0
  : R extends 1
  ? Result
  : Mul<L, Decrement<R>, Add<Result, L>>;


type Result = Mul<10, 2>; // 20

Разделение

type GTE<L extends number, R extends number> = L extends R
  ? [true, 0]
  : R extends 0
  ? [true, Sub<L, R>]
  : L extends 0
  ? [false, Sub<R, L>]
  : GTE<Decrement<L>, Decrement<R>>;

type Div<
  L extends number,
  R extends number,
  Result extends number = 0
> = GTE<L, R> extends [infer IsGreater, infer Diff extends number]
  ? IsGreater extends true
    ? Diff extends 0
      ? [Increment<Result>, 0]
      : Div<Diff, R, Increment<Result>>
    : [Result, L]
  : never;

type GTEResult = GTE<3, 2>; // [true, 1] <-- [isGreter: true, Diff: 1]
type Result = Div<10, 3>; // [3, 1] <-- [Quotient: 3, Remainder: 1]

Мощность

type Pow<
  Base extends number,
  Exp extends number,
  Result extends number = Base
> = Exp extends 0
  ? 1
  : Exp extends 1
    ? Result
    : Pow<Base, Decrement<Exp>, Mul<Result, Base>>;

type Result = Pow<4, 2>; // 16

Проверить, является ли число четным

type IsEven<N extends number> = ToBinary<N> extends `${string}0`
  ? true
  : false;

type Result = IsEven<4>; // true

Предостережения

Как я сказал в начале статьи, есть и другие способы выполнения математики на уровне типов в Typescript, тот, который я выбрал для этой статьи, на мой взгляд, самый простой для чтения и понимания, но у него есть и некоторые недостатки:

Вы увидите, что некоторые из наших типов, даже если они правильные, отмечены следующей ошибкой: Type instantiation is excessively deep and possibly infinite. Чтобы улучшить эти типы, нам нужно написать их немного по-другому, но ради удобочитаемости я предпочел оставить их такими, какие они есть. во время прочтения статьи.
Вот несколько примеров того, как мы можем улучшить типы Increment и Add :

type Increment<N extends number> =
  NumberToArray<N> extends infer A extends unknown[]
    ? Length<[...A, unknown]>
    : never;

type Add<
  L extends number,
  R extends number
> = NumberToArray<L> extends infer LA extends unknown[]
  ? NumberToArray<R> extends infer RA extends unknown[]
    ? Length<[...LA, ...RA]>
    : never
  : never;

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

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

Кроме того, ничего из того, что мы сделали, не будет работать для ненатуральных чисел.

👋 Заключение

Я очень надеюсь, что вам понравилось читать эту статью, я хотел бы знать ваше мнение о ней, поэтому, пожалуйста, оставьте комментарий и дайте мне знать ❤️

Обычно я пытаюсь представить реальный сценарий, когда делаю такие продвинутые шрифты, но в этот раз, я думаю, их нет, и это было просто забавным испытанием для меня и, надеюсь, для вас.

Меня интересуют альтернативные решения и разные подходы, поэтому, если они у вас есть, напишите мне или напишите комментарий.

🙆🏻‍♂️ Об авторе

Я инженер-программист в VLK STUDIO и в настоящее время работаю над проектом с открытым исходным кодом под названием Morfeo.

Всякий раз, когда я могу, я делюсь тем, что знаю, здесь, на Medium.

Если вам нравится то, что я делаю, не стесняйтесь поддержать мою работу: https://medium.com/@mauro.erta/membership

Или подписывайтесь на меня в Твиттере.

Дополнительные материалы на PlainEnglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter, LinkedIn, YouTube и Discord . Заинтересованы в хакинге роста? Ознакомьтесь с разделом Схема.