Chapter 26

Type-Level Algorithms: Filter, Zip, BinaryAdd — The Turing-Complete Edge

TypeScript's Type System Is Turing-Complete

Not an exaggeration. Recursive conditional types mean you can implement any computable function at the type level—at the cost of compile time and a recursion depth limit of approximately 1000. Understanding these implementations decodes the computation model underlying TypeScript's type inference, and it gives you the tools to read complex recursive types when you encounter them in library definitions.

1. Filter: Keeping Tuple Elements That Match a Predicate

type Filter<T extends any[], Pred> =
  T extends [infer Head, ...infer Tail]
    ? Head extends Pred
      ? [Head, ...Filter<Tail, Pred>]
      : Filter<Tail, Pred>
    : [];

// Tests
type Mixed = [string, number, string, boolean, string, null];

type Strings = Filter<Mixed, string>;
// [string, string, string]  ✓

type Numbers = Filter<Mixed, number | boolean>;
// [number, boolean]  ✓

type NonNullable2<T extends any[]> = Filter<T, {}>;
type CleanMixed = NonNullable2<[string, null, number, undefined, boolean]>;
// [string, number, boolean]  ✓

Breakdown:

T extends [infer Head, ...infer Tail]: destructure the tuple into first element and rest
Head extends Pred: test whether the head satisfies the predicate
Recurse on Tail, splice results with spread

2. ZipWith: Pairing Two Tuples Element-by-Element

type ZipWith<A extends any[], B extends any[]> =
  A extends [infer AHead, ...infer ATail]
    ? B extends [infer BHead, ...infer BTail]
      ? [[AHead, BHead], ...ZipWith<ATail, BTail>]
      : []
    : [];

type Keys = ["id", "name", "email"];
type Values = [number, string, string];

type Pairs = ZipWith<Keys, Values>;
// [["id", number], ["name", string], ["email", string]]  ✓

// Reconstruct an object type from pairs
type PairsToObject<T extends [PropertyKey, any][]> = {
  [K in T[number] as K[0]]: K[1]
};

type Reconstructed = PairsToObject<Pairs>;
// { id: number; name: string; email: string }  ✓

Zip to Union of Pairs

type Zip<K extends PropertyKey[], V extends any[]> =
  { [I in keyof K]: I extends keyof V ? { key: K[I]; value: V[I] } : never }[number];

type Zipped = Zip<["a", "b", "c"], [1, 2, 3]>;
// { key: "a"; value: 1 } | { key: "b"; value: 2 } | { key: "c"; value: 3 }

3. Reverse: Flipping a Tuple

type Reverse<T extends any[], Acc extends any[] = []> =
  T extends [infer Head, ...infer Tail]
    ? Reverse<Tail, [Head, ...Acc]>
    : Acc;

type Rev = Reverse<[1, 2, 3, 4, 5]>;
// [5, 4, 3, 2, 1]  ✓

The Acc accumulator is the key to tail-recursive form. Without it, results are assembled during stack unwinding (non-tail-recursive), hitting depth limits sooner. With Acc, the result accumulates in a parameter and TypeScript's compiler can apply tail-call optimization.

4. Flatten: Deep Flatten of Nested Tuples

type Flatten<T extends any[]> =
  T extends [infer Head, ...infer Tail]
    ? Head extends any[]
      ? [...Flatten<Head>, ...Flatten<Tail>]
      : [Head, ...Flatten<Tail>]
    : [];

type Nested = [1, [2, [3, [4]]], 5];
type Flat = Flatten<Nested>;
// [1, 2, 3, 4, 5]  ✓

5. Numeric Arithmetic via Tuple Length

This is the most surprising part: TypeScript has no numeric operators, but tuple length provides the primitive for all arithmetic.

BuildTuple: The Core Primitive

type BuildTuple<N extends number, T extends unknown[] = []> =
  T["length"] extends N
    ? T
    : BuildTuple<N, [...T, unknown]>;

type T3 = BuildTuple<3>;  // [unknown, unknown, unknown]

T["length"] returns the tuple's length as a literal number type. Every numeric operation builds on this.

Add

type Add<A extends number, B extends number> =
  [...BuildTuple<A>, ...BuildTuple<B>]["length"];

type Sum = Add<3, 4>;   // 7  ✓
type Sum2 = Add<10, 5>; // 15 ✓

Concatenate two tuples, read their combined length.

Subtract

// A - B, requires A >= B
type Subtract<A extends number, B extends number> =
  BuildTuple<A> extends [...BuildTuple<B>, ...infer Rest]
    ? Rest["length"]
    : never;

type Diff1 = Subtract<10, 3>;  // 7  ✓
type Diff2 = Subtract<5, 5>;   // 0  ✓
// Subtract<3, 5> = never — negative numbers unsupported

BuildTuple<A> extends [...BuildTuple<B>, ...infer Rest]: check if the A-length tuple can be decomposed into a B-length prefix plus remainder. The remainder's length is A - B.

Multiply

type Multiply<
  A extends number,
  B extends number,
  Acc extends unknown[] = []
> =
  B extends 0
    ? Acc["length"]
    : Multiply<A, Subtract<B, 1>, [...Acc, ...BuildTuple<A>]>;

type Prod = Multiply<3, 4>;  // 12 ✓

IsGreaterThan

type IsGreaterThan<A extends number, B extends number> =
  A extends B
    ? false
    : BuildTuple<A> extends [...BuildTuple<B>, ...infer _Rest]
      ? true
      : false;

type GT1 = IsGreaterThan<5, 3>;  // true  ✓
type GT2 = IsGreaterThan<3, 5>;  // false ✓
type GT3 = IsGreaterThan<3, 3>;  // false ✓

The Recursion Ceiling

// This causes "Type instantiation is excessively deep and possibly infinite"
type Overflow = BuildTuple<1001>;

// Practical limits:
// < 50: fast
// < 500: usable
// > 999: compile error

6. String Parsing at the Type Level

Split

type Split<S extends string, Sep extends string> =
  S extends `${infer Head}${Sep}${infer Tail}`
    ? [Head, ...Split<Tail, Sep>]
    : [S];

type Parts = Split<"a,b,c,d", ",">;
// ["a", "b", "c", "d"]  ✓

type PathParts = Split<"foo/bar/baz", "/">;
// ["foo", "bar", "baz"]  ✓

// Split into individual characters
type Chars = Split<"hello", "">;
// ["h", "e", "l", "l", "o"]  ✓

Join

type Join<T extends string[], Sep extends string> =
  T extends []
    ? ""
    : T extends [infer Only extends string]
      ? Only
      : T extends [infer Head extends string, ...infer Tail extends string[]]
        ? `${Head}${Sep}${Join<Tail, Sep>}`
        : never;

type Joined = Join<["a", "b", "c"], "-">;
// "a-b-c"  ✓

Practical: Type-Safe Route Parameter Extraction

type ExtractRouteParams<Route extends string> =
  Route extends `${string}:${infer Param}/${infer Rest}`
    ? Param | ExtractRouteParams<`/${Rest}`>
    : Route extends `${string}:${infer Param}`
      ? Param
      : never;

type Params1 = ExtractRouteParams<"/user/:id/posts/:postId">;
// "id" | "postId"  ✓

type RouteParamObject<Route extends string> = {
  [K in ExtractRouteParams<Route>]: string;
};

type UserParams = RouteParamObject<"/user/:id/posts/:postId">;
// { id: string; postId: string }  ✓

// Type-safe route builder
function buildRoute<Route extends string>(
  route: Route,
  params: RouteParamObject<Route>
): string {
  return Object.entries(params).reduce(
    (r, [key, value]) => r.replace(`:${key}`, value as string),
    route as string
  );
}

const url = buildRoute("/user/:id/posts/:postId", { id: "42", postId: "7" });
// "/user/42/posts/7"  ✓

// buildRoute("/user/:id", { id: "1", extra: "x" });
// Compile error: Object literal may only specify known properties  ✓

7. Tail-Call Optimization: Extending the Depth Limit

TypeScript 4.5 introduced special handling for tail-recursive conditional types:

// Non-tail-recursive: operations happen on the return value — cannot be optimized
type ReverseNonTail<T extends any[]> =
  T extends [infer H, ...infer R]
    ? [...ReverseNonTail<R>, H]  // spread happens after recursive call returns
    : [];

// Tail-recursive: recursive call IS the return value — compiler can optimize
type ReverseTail<T extends any[], Acc extends any[] = []> =
  T extends [infer H, ...infer R]
    ? ReverseTail<R, [H, ...Acc]>  // last operation is the recursive call itself
    : Acc;

For tail-recursive form to be recognized:

The true branch of the conditional must be a direct recursive call with no additional wrapping
Results accumulate in an Acc-style parameter, not on the return value

In practice, tail-recursive type operations can handle tuples roughly 20× longer than non-tail-recursive equivalents before hitting depth errors.

Recursion Depth Reference

Operation	Practical Limit	What Happens When Exceeded
Non-tail-recursive tuple recursion	~45 elements	"excessively deep" error
Tail-recursive tuple recursion	~1000 elements	Same error, higher threshold
Template literal string recursion	~100 characters	Same
Numeric arithmetic (BuildTuple)	0–999	Compile error above 999
Nested conditional types	~1000 levels	Compiler hangs or errors

Anti-Patterns

Anti-Pattern	Problem	Fix
Type-level arithmetic on large numbers in production code	Exceeds depth limit, extremely slow compile	Limit to ≤ 100, or use runtime
Non-tail-recursive deep tuple operations	Hits depth ceiling fast	Rewrite with `Acc` parameter
Unbounded string template parsing	Long strings exceed depth	Add length constraints or parse at runtime
Over-relying on type-level algorithms	Compile times explode, error messages become unreadable	Use generic constraints for compile-time, runtime for heavy computation

Summary

Algorithm	Core Technique	Depth Constraint
`Filter<T, Pred>`	Head/Tail destructuring + conditional splice	Tuple length
`ZipWith<A, B>`	Dual simultaneous destructuring	Shorter tuple length
`Reverse<T>`	Tail-recursive with Acc	~1000 with optimization
`Flatten<T>`	Nested destructuring + double recursion	Total element count
`Add/Subtract<A, B>`	BuildTuple length	Operands < 1000
`Split<S, Sep>`	Template literal infer	String length < ~100
`Join<T, Sep>`	Template literal splice recursion	Same

Rate this chapter

4.6 / 5 (4 ratings)