TypeScript: Type-based binary adder
Tags: typescript, webdev, funny
Published: 2021-03-13 09:58:57

_Everything described in the article is relevant for the 4.2.3 version of TypeScript._

Hi there!
The TypeScript now supports [Variadic Tuple Types](https://www.typescriptlang.org/docs/handbook/release-notes/typescript-4-0.html#variadic-tuple-types). It's mean that we can use spread operator and generic parameters to create types that contvert on array-like type to another. For example, let's create a type that appends an element to an array.
```typescript
type Append<T extends unknown[], R> = [R, ...T];

let a1: Append<[1, 2, 3], 0>;
//   ^ = let a1: [0, 1, 2, 3]
let a2: Append<[], "some">;
//   ^ = let a2: ["some"]
let a3: Append<[1, "q", false], {a: number}>;
//   ^ = let a3: [{a: number}, 1, "q", false]
```
[playground](https://www.typescriptlang.org/play?#code/C4TwDgpgBAgmkDsAmAeAKlCAPYFkGcoBXBAawQHsB3BAbQF0AaKAJQD4oBeKWl5gOkFp6AbgBQYgDYRgUAIYBGAFyx4eVLQXMATMwDMTKAAY24gPRmoVgHpco02YpW0jzLVF1QDUmfO0q4RA1DACJ8CgBbCBDTMQsrKFtuBz9nMMjo+h9HPQC1ZBRNZhCARxDmADM5SXwIQwBvORUEIgiAIwgAJwBfWPibOxS5XJ5G5taOnrdissrq2vogA)

OK, but what if we want to create a type that will remove the first element of the array. This type isn't that simple because an empty array `[]` extends `unknown[]` and we have to check that there are elements in the original array. We can do this using [conditional type](https://www.typescriptlang.org/docs/handbook/advanced-types.html#conditional-types) and [type inference](https://www.typescriptlang.org/docs/handbook/advanced-types.html#type-inference-in-conditional-types)
```typescript
type Slice<T extends unknown[]> = T extends [infer _, ...infer Tail] 
  ? Tail 
  : [];

let b1: Slice<[1, 2, 3]>;
//   ^ = let b1: [2, 3]

let b2: Slice<[1]>;
//   ^ = let b2: [];

let b3: Slice<[]>;
//   ^ = let b3: [];
```
[playground](https://www.typescriptlang.org/play?#code/C4TwDgpgBAygNgSwMYQDwBUoQB7AgOwBMBnKAV3wGt8B7Ad3wG0BdAPigF4pMc8jTGCfADMIAJygB9ADRQAdAqGiJ6AIYI4zKAH5u6uFABcUFgG4AUObgRgUAEYBGY-GRpGD2QCZZAZjYWAegCoEIA9TihrW0djRm8oP0so+09nRBRUd39zIJCocK5ku1STZgsrG3sfNNdM7NywiKLq0tMgA)

Let's complicate the task. How to create a type that will reverse an array? In typical situation we would use loops or recursion to iterate the array. In Typescript types we can use [recursive type alias](https://www.typescriptlang.org/docs/handbook/release-notes/typescript-3-7.html#more-recursive-type-aliases).
```typescript
type Reverse<T extends unknown[]> =
T extends [infer Item, ...infer Tail] 
  ? [...Reverse<Tail>, Item] 
  : [];

let c1: Reverse<[1, 2, 3]>;
//   ^ = let c1: [3, 2, 1]

let c2: Reverse<[1]>;
//   ^ = let c2: [1]

let c3: Reverse<[]>;
//   ^ = let c3: []
```
[playground](https://www.typescriptlang.org/play?#code/C4TwDgpgBAShBuEBOBnCAeAKlCAPYEAdgCYpQCuhA1oQPYDuhA2gLoB8UAvFNngSWSYBLQgDNkUAJIEAtgBooAOmUjxSHgEMhAGxZQAUFCgB+KE2WK4iVBkxbtbBdIgy9hqAC4zLANz792hDAUADGAIxeVsho6ExhCgBMCgDM7H4A9OlGUAB6XFCBweFeTMmJCmEs-oWhCZEI0RhxafqZ2XncNSF1ZpXVQaHJ9dYxrGwZWUYdBQMhQ95AA)

There is one unpleasant moment with this approach - typescript doesn't use generics' constraints to define the inference types. If we have `type Some<T extends number> = T` we can't use infer defined type as T parameter.
```typescript
type Some<A extends number> = A;

type Some2<A extends number[]> = A extends Array<infer B> 
  ? Some<B> 
//       ^ Error: Type 'B' does not satisfy the constraint 'number'
  : number;
```
But if we change `Some` type to `type Some<T> = T extends number ? T : number`, we can use infered type. These two vertion of `Some` type are not equal, but sometimes this approach can be used.

## Type-based binary adder

Ok, now we know everything to create a binary adder. If we don't know what a binary adder is, you can [learn it yourself](https://www.electronics-tutorials.ws/combination/comb_7.html). Firstly, we create several logical operations.
```typescript
type Xor<A, B> = A extends B ? 0 : 1;
/*
  A  B  Xor<A, B>
  0  0  0
  1  0  1
  0  1  1
  1  1  0
*/

type And<A, B> = A extends 1 ? B extends 1 ? 1 : 0 : 0;
/*
  A  B  And<A, B>
  0  0  0
  1  0  0
  0  1  0
  1  1  1
*/

type Or<A, B> = A extends 1 ? 1 : B extends 1 ? 1 : 0;
/*
  A  B  Or<A, B>
  0  0  0
  1  0  1
  0  1  0
  1  1  1
*/
```
Secondly, consider the adder circuit.
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bq4uhfn0epmkkblo7xx7.gif)
As you can see we have to use 2 bits of 2 numbers and _carry-in_ and return result bit and _carry-out_.
```typescript
type Sum<A, B, CIn> = Xor<Xor<A, B>, CIn>;
type COut<A, B, CIn> = Or<And<A, B>, And<Xor<A, B>, CIn>>;
```
Finally, we create the adder type.
```typescript
type Add<A, B, CIn = 0> = 
  A extends [...infer AN, infer AC] 
    ? B extends [...infer BN, infer BC]
      ? [...Add<AN, BN, COut<AC, BC, CIn>>, Sum<AC, BC, CIn>]
      : []
    : [];

let d1: Add<[0], [1]>
//   ^ = let d1: [1]

let d2: Add<[0, 1], [0, 1]>
//   ^ = let d2: [1, 0]

let d3: Add<[0, 1, 1, 1], [0, 0, 0, 1]>
//   ^ = let d3: [1, 0, 0, 0]

let d4: Add<[1, 1, 1, 1], [0, 0, 0, 1]>
//   ^ = let d4: [0, 0, 0, 0]
```
[playground](https://www.typescriptlang.org/play?ssl=48&ssc=30&pln=28&pc=1#code/C4TwDgpgBAGg9gJwDwEEA0UBCA+KBeKFKCAD2AgDsATAZyygH4oAGKALigEYBuAWACgA9ACoBUQuMzj4ydFmxiW41i0Wdl4zopXquazcoHDBAgaEiFqqDDnwTS5anXVMpDyrS6MvHVr75CovziRPSWVNby2hqqwV5KsTG6zPrxWvzGpvzm0ADysja4BETuTl5M6hxuZB7O3pUsASKKoVJQ+ZE40Qkpccma3cmpuumZ-Gbg0ADKAK4Atp0YAMIAkhRFsIhIMp3Yy2vYATlQS7kzwIsnB3YdKFZyOBh3ETsPe1frCuPZk4RUEQ99hQ7MwNi1iDUygBtAB0cIAlhQAGYQBCEAByGERKLRKCWAF0oIpxK4IY5PLCEcjUVhMVBsTTMATieJvJSYSh-qg6Zg6adzqgljYhR9sO9Zgs8cKgdh8SzxBwoXK4gqoEqAgIADYQYBQKicDiciJQ5j4jBQzj4r6CQSsgB6dm1uv1istWSdeoATIauSaMJbzcx-VaBDb7Y6dV7XRhTe7I1QAMw+41Brj+4OBmNZrghoS28QOggexPRljZ2PfYsAFmTSAt6bTOczZZblut+aghag1cVqb7MfxQA)

Other binary operations can be implemented using these principles. Will such types be needed in real projects? I don’t think so. But I think these principles will help you create really useful types. Subscribe to me and I will try to tell you more about interesting types of TypeScript.