TypeScript Type-Level Programming: Compute Fibonacci with Types

What We Want to Do

We aim to implement the Fibonacci sequence using TypeScript's type-level syntax, turning type declarations into a programmable computation.

Reference JavaScript Implementation

const fib = (n: number): number => n <= 1 ? n : fib(n - 1) + fib(n - 2);
for (let i = 0; i < 10; i++) {
  console.log(i, fib(i));
}

Running this prints the first ten Fibonacci numbers.

Type-Level Implementation

Using type definitions we can express the same computation.

import { Fib, Add } from './fib-type';

type one = Fib<1>;
type zero = Fib<0>;

type Two = Add<one, one>;
type Five = Add<Two, Add<Two, one>>;

type Fib5 = Fib<Five>;
type Fib9 = Fib<9>;

type r0 = Fib<Zero>; // 0
type r1 = Fib<One>; // 1
type r2 = Fib<Two>; // 1
type r3 = Fib<3>; // 2
type r4 = Fib<4>; // 3
type r5 = Fib<5>; // 5
type r6 = Fib<6>; // 8

Building Blocks

To perform arithmetic at the type level we define utility types such as Length, Shift, Append, IsEmpty, NotEmpty, And, Range, Concat, LessEq, SubList, Sub, and finally Fib.

type Length<T extends any[]> = T['length'];

type Shift<T extends any[]> = ((...t: T) => any) extends (_: any, ...Shift: infer P) => any ? P : [];

type Append<T extends any[], E = any> = [...T, E];

type IsEmpty<T extends any[]> = Length<T> extends 0 ? true : false;

type NotEmpty<T extends any[]> = IsEmpty<T> extends true ? false : true;

type And<T extends boolean, P extends boolean> = T extends false ? false : P extends false ? false : true;

type Range<T extends number, P extends any[] = []> = {0: Range<T, [any, ...P]>;1: P}[Length<P> extends T ? 0 : 1];

type Concat<T extends any[], P extends any[]> = [...T, ...P];

type LessEqList<T extends any[], P extends any[]> = {
  0: LessEqList<Shift<T>, Shift<P>>;
  1: true;
  2: false;
}[And<NotEmpty<T>, NotEmpty<P>> extends true ? 0 : IsEmpty<T> extends true ? 1 : 2];

type LessEq<T extends number, P extends number> = LessEqList<Range<T>, Range<P>>;

type Add<T extends number, P extends number> = Length<Concat<Range<T>, Range<P>>>;

type SubList<T extends any[], P extends any[], R extends any[] = []> = {
  0: Length<R>;
  1: SubList<Shift<T>, P, Append<R, any>>;
}[Length<T> extends Length<P> ? 0 : 1];

type Sub<T extends number, P extends number> = {
  0: Sub<P, T>;
  1: SubList<Range<T>, Range<P>>;
}[LessEq<T, P> extends true ? 0 : 1];

export type Fib<T extends number> = {
  0: T;
  1: Add<Fib<Sub<T, One>>, Fib<Sub<T, Two>>>;
}[LessEq<T, One> extends true ? 0 : 1];

Conclusion

The article demonstrates how TypeScript's type system can be used to perform compile‑time calculations such as the Fibonacci sequence, offering a playful exploration of type‑level programming.