TypeScript: Type-based binary adder

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

Hi there!
The TypeScript now supports 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.

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

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 and type inference

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

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.

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

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.

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. Firstly, we create several logical operations.

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.

As you can see we have to use 2 bits of 2 numbers and carry-in and return result bit and carry-out.

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.

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

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.