Skip to content

Instantly share code, notes, and snippets.

@tjjfvi
Last active May 1, 2022 15:26
Show Gist options
  • Save tjjfvi/e1b4de4cb17978e234bb391726edaa59 to your computer and use it in GitHub Desktop.
Save tjjfvi/e1b4de4cb17978e234bb391726edaa59 to your computer and use it in GitHub Desktop.
A collection of utilities for programming in TypeScript's Type System

This is a collection of utilities for programming in TypeScript's Type System.

Each codeblock represents one utility type, but there are often multiple implementations. Each implementation has equivalent semantics, but differ in dependency count and length.

Most of the time, the implementation you pick should not really matter.

However, if you are code-golfing, alternate versions may be better or worse depending on what other utility types you need. Also, some implementations may benefit from inlining.

Natural Number Arithmetic

Convert a number to a Nat

Convert a number literal to a Nat

type NumToNat<T, N=[]> = T extends N["length"] ? N : NumToNat<T, [...N, 0]>

type NumToNat<T> = StrNumToNat<`${T}`>

type NumToNat<T> = NumOrStrNumToNat<T>

Convert a string literal representing a number to a Nat

type StrNumToNat<T, N=[]> = T extends `${N["length"]}` ? N : StrNumToNat<T, [...N, 0]>

type StrNumToNat<T> = NumOrStrNumToNat<T>

Convert a number literal or a string literal representing a number to a Nat

type NumOrStrNumToNat<T, N=[], U=`${T}`> = U extends `${N["length"]}` ? N : NumOrStrNumToNat<T, [...N, 0]>

Increment / Decrement Nat

type IncNat<A> = [...A, 0]

type IncNat<A> = IncInt<A>

Decrement a Nat, returning 0 in case of overflow

type DecNat<A> = A extends [0, ...infer B] ? B : []

type DecNat<A> = SubNat<A, [0]>

type DecNat<A> = DecInt<A>

Add / Subtract Nats

type AddNat<A, B> = [...A, ...B]

type AddNat<A, B> = AddInt<A, B>

Subtract two Nats, returning 0 in case of overflow

type SubNat<A, B> = A extends [...B, ...infer C] ? C : []

Multiply Nats

type MulNat<A, B, N = []> = A extends [0, ...infer A] ? MulNat<A, B, AddNat<A, B>> : N

type MulNat<A, B> = MulInt<A, B>

Divide / Modulo Nats

type DivNat<A, B, Q = []> = A extends [...B, ...infer X] ? DivNat<X, B, [...Q, 0]> : Q

type DivNat<A, B> = DivAndModNat<A, B>[0]
type ModNat<A, B> = A extends [...B, ...infer X] ? ModNat<X, B> : A

type ModNat<A, B> = DivAndModNat<A, B>[1]
type DivAndModNat<A, B, Q = []> = A extends [...B, ...infer X] ? DivAndModNat<X, B, [...Q, 0]> : [Q, A]

Misc

Calculate the GCD of two Nats using the Euclidean algorithm

type GcdNat<A, B> = [] extends A | B ? Exclude<A | B, []> : GcdNat<B, ModNat<A, B>>

Integer Arithmetic

Increment / Decrement an Int

type IncInt<T> = T extends [1, ...infer T] ? T : [...T, 0]

type IncInt<T> = IncOrDecInt<T>
type DecInt<T> = T extends [0, ...infer T] ? T : [...T, 1]

type DecInt<T> = IncOrDecInt<T, 1>

Increment if P is 0, decrement if P is 1

type IncOrDecInt<T, P=0, N=[1,0][P]> = T extends [N, ...infer T] ? T : [...T, P]

Add / Subtract Ints

type AddInt<A, B> = B extends [infer X, ...infer B] ? AddInt<IncOrDecInt<A, X>, B> : A

type AddInt<A, B> = AddOrSubInt<A, B>
type SubInt<A, B> = B extends [infer X, ...infer B] ? SubInt<IncOrDecInt<A, [1,0][X]>, B> : A

type SubInt<A, B> = AddOrSubInt<A, B, 1>

Add if X is 0, subtract if X is 1

type AddOrSubInt<A, B, X=0> = B extends [infer Y, ...infer B] ? AddOrSubInt<IncOrDecInt<A, [Y, [1, 0][Y]][X]>, B, X> : A
type NegInt<T> = { [K in keyof T]: [1,0][T[K]] }

type NegInt<T> = SubInt<[], T>

Multiply Ints

type MulInt<A, B, N = []> = A extends [infer X, ...infer A] ? MulInt<A, B, AddOrSubInt<A, B, X>> : N

Tuples

type Reverse<T, X = []> = T extends [...infer T, infer A] ? Reverse<T, [...X, A]> : X

Filter a union of tuples for those with the smallest length

type Shortest<T, K = keyof T> = T extends T ? keyof T extends K ? T : never : 0

Filter a union of tuples for those with the largest length

type Longest<T, K = T extends T ? keyof T : 0> = T extends T ? [K] extends [keyof T] ? T : never : 0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment