It has been shown multiple times that TypeScript's Type System is Turing Complete. In this blog post, we will explore some basic concepts for writing general-purpose functional programs entirely at the type-level.

The most basic components of functional programming are functions and function application. We will define a type `F`

, which represents a function with an input argument `args`

and an output `out`

and define a type `apply`

which takes a function extending `F`

and a tuple of arguments `args`

and computes the output of the function.

interface F { args: unknown; out: unknown; } type apply<f extends F, args> = (f & { 'args': args })['out']

This very simple yet powerful trick allows to dinamically override the arguments of functions with new ones passed to apply and exploit type-inference to compute the output. To define a new function, we can simply extend the `F`

interface and override the output type by manipulating the `args`

through conditional type inference.

For instance, let's define the natural numbers through Peano's representation and implement some basic arithmetic operations.

A natural number can be defined as either zero or a successor of another natural number:

type Zero = { kind: "zero" } type Suc<n> = { kind: "suc", n: n }

For instance, we can define `1`

as `Suc<Zero>`

, `2`

as `Suc<Suc<Zero>>`

, and so on.

This definition is not fully correct, since the generic parameter `n`

is not constrained to be a natural number. We could fix this by using other TypeScript tricks, but let's keep things simple here.

Now we can define our first function, the addition:

interface add extends F { out: this['args'] extends [infer a, infer b] ? a extends Zero ? b : a extends Suc<infer n> ? Suc<apply<add, [n, b]>> : never : never }

The function is defined by extending the generic function interface `F`

and overriding the output type. In fact, `out`

is defined as a conditional type based on the `args`

tuple on which we can apply type inference to simulate pattern matching. In this case, we match on the parameter `a`

and check wheter it is zero or a successor of another natural number. In case of zero, we simply return `b`

, otherwise compute the result through recursive application.

Now we can use `apply`

to actually compute addition on different parameters:

type x0 = apply<add, [Zero, Zero]> // Zero type x1 = apply<add, [Suc<Zero>, Zero]> // Suc<Zero> type x2 = apply<add, [Suc<Zero>, Suc<Zero>]> // Suc<Suc<Zero>> type x3 = apply<add, [Suc<Suc<Zero>>, Suc<Zero>]> // Suc<Suc<Suc<Zero>>>

Similarly, we define multiplication:

interface mul extends F { out: this['args'] extends [infer a, infer b] ? a extends Zero ? Zero : a extends Suc<infer n> ? apply<add, [apply<mul, [n, b]>, b]> : never : never }

type y0 = apply<mul, [Zero, Zero]> // Zero type y1 = apply<mul, [Suc<Suc<Zero>>, Suc<Suc<Zero>>]> // Suc<Suc<Suc<Suc<Zero>>>>

We can also define higher-order functions in a very elegant way. For instance, let's define the `map`

function that applies a given function `f`

to each element of a list `args`

.

type map<f extends F, args extends unknown[]> = args extends [] ? args : args extends [infer x, ...infer xs] ? [apply<f, [x]>, ...map<f, xs>] : never;

For example, we can define a function that doubles a number and map a list of numbers to a list of the doubled numbers.

interface double extends F { out: this['args'] extends [infer a] ? apply<mul, [a, Suc<Suc<Zero>>]> : never } type xs = map<double, [Zero, Suc<Zero>, Suc<Suc<Zero>>]> // [Zero, Suc<Suc<Zero>>, Suc<Suc<Suc<Suc<Zero>>>>]

Similarly, we can define the `fold`

function as follows:

type fold<f extends F, b extends unknown, args extends unknown[]> = args extends [] ? b : args extends [infer x, ...infer xs] ? fold<f, apply<f, [b, x]>, xs> : never

For instance, we can use fold function to sum the elements of a list:

type r = fold<add, Zero, [Suc<Zero>, Suc<Suc<Zero>>, Suc<Suc<Suc<Zero>>>]> // Suc<Suc<Suc<Suc<Suc<Suc<Zero>>>>>>

As a more advanced example, let's implement the factorial function, which calculates the product of all positive integers up to a given number. We can define the function as follows:

interface fact extends F { out: this['args'] extends [infer a] ? a extends Zero ? Suc<Zero> : a extends Suc<infer n> ? apply<mul, [a, apply<fact, [n]>]> : never : never }

For instance, the factorial of `4`

is `24`

:

type fac = apply<fact, [Suc<Suc<Suc<Suc<Zero>>>>]> // Suc<Suc<Suc<Suc<Suc<Suc<Suc<Suc<Suc<Suc<Suc<Suc<Suc<Suc<Suc<Suc<Suc<Suc<Suc<Suc<Suc<Suc<Suc<Suc<Zero>>>>>>>>>>>>>>>>>>>>>>>>

We've explored the power of TypeScript's type system by writing general-purpose programs entirely at the type-level. This exploration showcases TypeScript as a powerful tool for not only providing static typing for JavaScript but also for constructing type-level programs that can help catch errors and ensure semantical correctness at compile-time.

You can try out the code in the TypeScript Playground.