TS Type Challenges · Part 8 — Type-level Arithmetic

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

Cơ chế — nối = cộng

Nếu A là tuple độ dài A và B là tuple độ dài B, trải cả hai vào một mảng cho độ dài A + B. Từng dòng:

1. biến A thành tuple A ô.
2. tương tự cho B.
3. nối; spread tuple ở tầng type là nối mảng.
4. đọc độ dài gộp về lại thành type số.

Đánh giá cụ thể: Add<2, 3>

// step 1: BuildTuple<2>
//   [] → [unknown] → [unknown, unknown]
//   BuildTuple<2> = [unknown, unknown]

// step 2: BuildTuple<3>
//   [] → [unknown] → [unknown, unknown] → [unknown, unknown, unknown]
//   BuildTuple<3> = [unknown, unknown, unknown]

// step 3: concatenate
//   [...BuildTuple<2>, ...BuildTuple<3>]
//   = [...[unknown, unknown], ...[unknown, unknown, unknown]]
//   = [unknown, unknown, unknown, unknown, unknown]

// step 4: read length
//   [unknown, unknown, unknown, unknown, unknown]['length'] → 5

type Result = Add<2, 3>; // 5

Nối = cộng. Đây là ý tưởng quan trọng nhất trong toán tầng type.

Cạm bẫy

• Chi phí đơn nguyên: Add<900, 900> dựng tuple ~1800 phần tử và có thể vượt độ sâu đệ quy.
• Phụ thuộc BuildTuple: nếu toán hạng quá lớn không materialize được, Add lỗi trước khi nối.
• Chỉ số nguyên không âm: cả hai toán hạng là số tự nhiên qua độ dài tuple.

Tóm tắt: Add dựng hai tuple đếm rồi đo độ dài phần nối.

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

Cơ chế — khớp mẫu để tiêu thụ

Add trải để dựng, còn Subtract khớp mẫu để tiêu thụ. Từng dòng:

1. đống đủ A phần tử.
2. mẫu: “tuple này bắt đầu bằng thứ độ dài B, phần còn là Rest”.
3. nếu khớp, đáp án là bao nhiêu phần tử không bị lấy.
4. nếu B > A, không bóc được B phần tử từ tuple ngắn hơn; không có kết quả số tự nhiên.

Đánh giá cụ thể: Subtract<8, 3>

// step 1: BuildTuple<8> → 8 × unknown
// step 2: BuildTuple<3> → 3 × unknown

// step 3: pattern match
//   [u,u,u,u,u,u,u,u] extends [...[u,u,u], ...infer Rest] ?
//   Rest is inferred as [u,u,u,u,u]  (5 elements)

// step 4: Rest['length'] → 5

type Result = Subtract<8, 3>; // 5

Thất bại cụ thể: Subtract<3, 5>

// BuildTuple<3> = [u, u, u]   (3 elements)
// BuildTuple<5> = [u, u, u, u, u]   (5 elements)

// Can [u, u, u] match [...[u,u,u,u,u], ...infer Rest] ?
// No — you cannot prefix a 3-element tuple with 5 elements.
// Conditional fails → never

type Bad = Subtract<3, 5>; // never

Cạm bẫy

• never nghĩa là “không xác định trong ℕ”, không phải “âm năm” — độ dài tuple chỉ mô hình hoá 0, 1, 2, ….
• infer Rest phải là rest spread — mẫu [BuildTuple<B>, ...infer Rest] (không spread đầu B) sẽ không destructure đúng.
• Cả hai bên trả chi phí BuildTuple — trừ số lớn materialize hai tuple lớn.

Tóm tắt: trừ bằng cách khớp tuple A thành “tiền tố B + phần còn”, rồi đọc Rest['length'].

type GreaterThan<
  A extends number,
  B extends number,
  Count extends unknown[] = [],
> = A extends B
  ? false
  : Count['length'] extends A
    ? false
    : Count['length'] extends B
      ? true
      : GreaterThan<A, B, [...Count, unknown]>;

Cơ chế — đua hai đích

Từng dòng:

1. số bằng nhau không lớn hơn hẳn.
2. tuple đếm bắt đầu độ dài 0.
3. nếu chạm A trước B, A nhỏ hơn → A > B là false.
4. nếu chạm B trước, B nhỏ hơn → A > B là true.
5. chưa chạm đích nào; tăng Count rồi đệ quy.

Đánh giá cụ thể: GreaterThan<2, 1>

// step 0: Count = [], length 0
//   2 extends 1? no
//   0 extends 2? no
//   0 extends 1? no
//   → recurse with Count = [unknown]

// step 1: Count = [unknown], length 1
//   1 extends 2? no
//   Count['length'] extends A → 1 extends 2? no
//   Count['length'] extends B → 1 extends 1? yes → true

type Result = GreaterThan<2, 1>; // true — hit B (1) before A (2)

Đánh giá cụ thể: GreaterThan<1, 2>

// step 0: Count length 0 → no hits → Count = [unknown]
// step 1: Count length 1
//   1 extends 2? no
//   Count['length'] extends A → 1 extends 1 → true → false

type Result = GreaterThan<1, 2>; // false — hit A (1) before B (2)

Đánh giá cụ thể: GreaterThan<5, 5>

// step 0: A extends B → 5 extends 5 → true → false immediately

type Result = GreaterThan<5, 5>; // false

Số bạn chạm trước khi đếm từ 0 là số nhỏ hơn — đó là toàn bộ phép so sánh.

Cạm bẫy

• Trường hợp bằng xử lý trước — không có A extends B ? false, số bằng sẽ rơi vào cuộc đua đếm.
• Độ sâu là min(A, B) + 1 — so 500 với 499 đi ~499 bước.
• Chỉ bất đẳng thức nghiêm — hòa luôn trả false (đây là >, không phải >=).

Tóm tắt: đếm từ 0; toán hạng khớp trước là số nhỏ hơn.

type Fibonacci<
  N extends number,
  Cur extends unknown[] = [unknown],
  Prev extends unknown[] = [],
  Index extends unknown[] = [unknown],
> = Index['length'] extends N
  ? Cur['length']
  : Fibonacci<N, [...Cur, ...Prev], Cur, [...Index, unknown]>;

Cơ chế — ba accumulator

Ta mang ba tuple làm trạng thái:

Từng dòng:

1. dừng khi đã tiến tới vị trí N.
2. Fibonacci<N, [...Cur, ...Prev], Cur, [...Index, unknown]> — one loop iteration: Cur mới = nối Cur cũ + Prev → cộng qua spread. Prev mới = Cur cũ. Index mới = Index cũ thêm một phần tử.

Đánh giá cụ thể: Fibonacci<3>

// Initial: Cur=[u] (len 1), Prev=[] (len 0), Index=[u] (len 1)
// Target N = 3

// ── iteration 1 ──
// Index len 1 extends 3? no
// new Cur = [...[u], ...[]] = [u]           → len 1  (F₂)
// new Prev = [u]                            → len 1  (old Cur)
// new Index = [u,u]                         → len 2

// ── iteration 2 ──
// Index len 2 extends 3? no
// new Cur = [...[u], ...[u]] = [u,u]       → len 2
// new Prev = [u]                            → len 1
// new Index = [u,u,u]                       → len 3

// ── iteration 3 ──
// Index len 3 extends 3? yes → return Cur['length'] = 2

type Result = Fibonacci<3>; // 2

Lần tay trên giấy: F₁=1, F₂=1, F₃=2 — type trả 2.

Cạm bẫy

• Cur và Index khởi tạo [unknown] — indexing challenge coi Fibonacci<1> là 1; vòng lặp căn theo base case đó.
• Mỗi bước hai lần nối — Cur tăng nhanh; Fibonacci<30> đã nặng.
• Độ sâu ≈ N — một đệ quy mỗi nhịp Index; N lớn chạm giới hạn nhanh.

Tóm tắt: Fibonacci là vòng lặp đệ quy đuôi với tuple Cur, Prev, Index; mỗi bước cộng độ dài qua nối.

type MultiplyByTwo<N extends number> = Add<N, N>;

Nhân đôi là cộng với cùng toán hạng hai lần — tái dùng thứ đã dựng.

// step 1: BuildTuple<N> twice, concat, read length → 2 × N
type Double5 = MultiplyByTwo<5>; // 10

Độ dài tuple mô hình hoá số tự nhiên (0, 1, 2, …) — không có tuple độ dài âm. Mẫu [...BuildTuple<5>, ...infer Rest] không khớp tuple 3 phần tử (không bỏ 5 từ 3), nên conditional rơi xuống never, báo trung thực “không có kết quả tự nhiên”.

// BuildTuple<3> has 3 slots; prefix pattern needs 5 → match fails → never
type Bad = Subtract<3, 5>; // never