The Functional Language Hiding Inside TypeScript's Types

TypeScript’s type system is a programming language hiding inside another programming language. It has all the tools, functional programming languages give us to write programs: Functions, pattern matching and even recursion.

Once you’ve seen it that way you can’t unsee it, and you start wondering what you could get away with. Compile-time crimes is me pushing it to the limit. This post is the toolkit that series is going to be built upon.

I’m assuming you already know your way around basic TypeScript. If you don’t, the TypeScript handbook is a better place to start.

Type functions (AKA Generic Types)

But first I’d like you to think of this as a type function. It takes a type and returns a type.

type Maybe<A> = A | undefined

Maybe is a type function that given a type A returns a type A | undefined.
(ie. Maybe<3> == (3 | undefined))

Pattern Matching

To learn about pattern matching in typescript’s types we’re going to write a Result type.

type Result<T, E> = { tag: 'Ok', value: T } | { tag: 'Err', error: E }

That’s a good first draft. Now how would we write a function that tells us whether a Result is Ok?

type IsOk<T extends Result<any, any>> = T extends { tag: 'Ok' } ? true : false

type A = IsOk<{ tag: 'Ok', value: 1}> 
//   ^? true
type B = IsOk<{ tag: 'Err', error: 'asdf'}> 
//   ^? false

Our function takes a T that must be a Result and pattern matches it against { tag: 'Ok' }.

What about a function to get the value if it’s okay and undefined otherwise?

type GetValue<T extends Result<any, any>> =
  T extends { tag: 'Ok', value: infer V }
  ? V
  : undefined

type A = GetValue<{ tag: 'Ok', value: 42 }>
//   ^? 42

type B = GetValue<{ tag: 'Err', error: 'oops' }>
//   ^? undefined

And there’s infer: it captures a piece of the pattern so we can use it on the other side of the ?.

Making helper patterns

We can now define helper patterns to clean up our code

type Ok<T> = { tag: 'Ok', value: T }
type Err<E> = { tag: 'Err', error: E }

// Now we can use `Ok<infer V>` instead of `{ tag: 'Ok', value: infer V }`
type GetValue<T extends Result<any, any>> = T extends Ok<infer V> ? V : undefined

Why does T extends Ok<infer V> work?

Well let’s simplify it: Ok<infer V> = { tag: 'Ok', value: infer V }

This is the same we used in the previous version of the function

That T extends Result<any, any> is still bothering me though, is there anything we can do about it?

Default Types

Yes! We can use default type arguments. Let’s rewrite our Result type

type Ok<T = any> = { tag: 'Ok', value: T }
type Err<E = any> = { tag: 'Err', error: E }

// let's take the chance to reuse our new Ok and Err types
type Result<T = any, E = any> = Ok<T> | Err<E>

This allows us to use Result on its own, and T and E will be assigned the default values
(Result == Result<any, any>). Let’s rewrite the functions.

type IsOk<T extends Result> = T extends Ok ? true : false
type GetValue<T extends Result> = T extends Ok<infer V> ? V : undefined

Much cleaner.

Do we still need that T extends Result? Not really, but it’s a safety feature.

// WITH `extends Result`
type IsOk<T extends Result> = T extends Ok ? true : false
type A = IsOk<3>
//   ^? Type 'number' does not satisfy the constraint 'Result<any, any>'. [2344]

// WITHOUT `extends Result`
type IsOk<T> = T extends Ok ? true : false
type A = IsOk<3>
//   ^? false

A note on union distribution

One catch: unions spread out

When the thing on the left of extends is a union, TypeScript doesn’t match it as a whole. It splits the union apart, runs the conditional on each member separately, and unions the results back together. Our Result is a union, so:

// previously defined:
// type Result<T = any, E = any> = Ok<T> | Err<E>
// type IsOk<T> = T extends Ok ? true : false

type A = IsOk<Result>
//   ^? boolean

Result is a union of Ok<T> | Err<E> so IsOk expands to (Ok<T> | Err <E>) extends Ok ? true : false.

Since the left-hand side is a union, TS distributes it and the whole expression becomes: (OK<T> extends Ok ? true : false) | (Err<E> extends Ok ? true : false) which becomed true | false and finally boolean.

Most of the time this is a gift, since it means every function you write is automatically a map over unions for free. But when you want to ask something about the union itself, wrap both sides in a tuple to switch it off:

type IsOkStrict<T extends Result> = [T] extends [Ok] ? true : false

type A = IsOkStrict<Result>
//   ^? false
type B = IsOkStrict<Ok<1>>
//   ^? true

[T] isn’t a union, so there’s nothing to distribute over and the whole type gets matched at once.

Going recursive

Now suppose our chain of computations left us with nested results

type SomeComputation = Ok<Ok<Ok<3>>>

and we want a function that gets us the value. For that we’ll need to recursively dig into the Ok.

type GetValueDeep<T extends Result> =
  T extends Ok<infer S extends Result> // is T an Ok with a Result inside?
    ? GetValueDeep<S>     // continue recursion but with S
  : T extends Ok<infer S> // is T an Ok with something that's not a Result inside?
    ? S         // return that thing
    : undefined // return undefined

type A = GetValueDeep<Ok<Ok<Ok<3>>>>
//   ^? 3
type B = GetValueDeep<Err<1>>
//   ^? undefined
type C = GetValueDeep<"John">
//   ^? Type 'string' does not satisfy the constraint 'Result<any, any>'. [2344]

Lists are tuples

Tuples pattern match exactly like objects do — the only new thing is the shape of the pattern. [infer Head, ...infer Tail] splits a tuple into its first element and everything after it. That’s head and tail, which is all you need to write a fold.

Here’s map:

type GetValues<T extends Result[]> =
  T extends [infer Head extends Result, ...infer Tail extends Result[]]
    ? [GetValue<Head>, ...GetValues<Tail>] // apply, then recurse on the rest
    : []                                   // ran out of elements, stop

type A = GetValues<[Ok<1>, Ok<'two'>, Err<'nope'>]>
//   ^? [1, 'two', undefined]

Note the spread works in both directions: we take the tuple apart with ...infer Tail and put it back together with ...GetValues<Tail>.

The other trick worth knowing is counting. There are no numbers to increment up here, so instead we carry a second parameter — a tuple we push onto — and read its ['length'] at the end:

type CountOks<T extends Result[], C extends unknown[] = []> =
  T extends [infer Head extends Result, ...infer Tail extends Result[]]
    ? IsOk<Head> extends true
      ? CountOks<Tail, [unknown, ...C]> // an Ok: push a placeholder onto C
      : CountOks<Tail, C>               // an Err: leave C alone
    : C['length']                       // done, so how big did C get?

type A = CountOks<[Ok<1>, Err<'nope'>, Ok<3>]>
//   ^? 2

C is an accumulator and this is plain tail recursion with a default argument for the base case, the same shape you’d write in any functional language. unknown is just filler, nothing ever reads those elements, they exist to be counted.

Conclusion

That’s the whole toolkit: type functions, pattern matching with conditional types, infer, default arguments, constraints, recursion, and tuples for lists and counting.

It doesn’t look like much. But it’s enough, however, to make TypeScript’s type system Turing complete. Later in the series we will build a working Brainfuck interpreter out of these exact primitives.

But first, part 1, where we teach the type system to do arithmetic and then patch the compiler when it refuses.