Functional Programming with TypeScript's Type System

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.

Function Definition and Application

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.

Arithmetics

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>>>>

Higher-order functions

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>>>>>>

Factorial

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>>>>>>>>>>>>>>>>>>>>>>>>

Conclusion

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.