TS Type Challenges · Part 5 — Recursion over Tuples

type Push<T extends any[], V> = [...T, V];
type Unshift<T extends any[], V> = [V, ...T];

Từng dòng

Push

type Push<T extends any[], V> = [...T, V];
//     ^^^^^^^^^^^^^^^^^^^^^^    ^^^^  ^
//     T must be tuple-shaped    spread  append V at the end

• T là kiểu tuple (hoặc mảng).
• spread mọi phần tử của T, rồi thêm V làm phần tử cuối.

Unshift

type Unshift<T extends any[], V> = [V, ...T];
//                                  ^   ^^^^
//                                  V first, then all of T

• V đứng đầu; phần còn lại của T theo sau.

Đánh giá cụ thể

// Push<[1, 2], 3>
// step 0: T = [1, 2], V = 3
// step 1: spread T → 1, 2
// step 2: append V → [1, 2, 3]

// Unshift<[1, 2], 0>
// step 0: T = [1, 2], V = 0
// step 1: place V first → 0
// step 2: spread T after → [0, 1, 2]

Cạm bẫy

• Bất biến — khác push runtime, đây trả về kiểu tuple mới; không có gì bị mutate.
• Dùng trong đệ quy — ReverseAcc<R, [H, ...Acc]> mỗi bước Unshift H vào accumulator.

Tóm tắt: Push = [...T, V], Unshift = [V, ...T] — khối dựng cho mọi mẫu accumulator.

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

Từng dòng

type Reverse<T extends any[]> = T extends [infer Head, ...infer Tail]
//     ^^^^^^^^^^^^^^^^^^^^^^      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//     input tuple                 peel first element + rest

  ? [...Reverse<Tail>, Head]
//  ^^^^^^^^^^^^^^^^^^^^^^^^
//  recurse on Tail FIRST, spread that result, then append Head at the end

  : [];
//  ^^
//  base case: empty tuple → empty tuple

1. Khớp pattern — T không rỗng thành Head (đầu) + Tail (phần còn lại).
2. Nhánh đệ quy — Reverse<Tail> chạy trước khi đặt Head; spread [...] nối đuôi đã đảo hoàn toàn với Head ở cuối.
3. Base case — [] không khớp [Head, ...Tail], trả [].

Đánh giá cụ thể

// step 0: Reverse<[1, 2, 3]>
//   Head = 1, Tail = [2, 3]
//   need [...Reverse<[2, 3]>, 1]  — must finish Reverse<[2, 3]> first

// step 1: Reverse<[2, 3]>
//   Head = 2, Tail = [3]
//   need [...Reverse<[3]>, 2]

// step 2: Reverse<[3]>
//   Head = 3, Tail = []
//   need [...Reverse<[]>, 3]

// step 3: Reverse<[]>
//   [] does not match [Head, ...Tail]  →  base case  →  []

// step 2 (unwind): [...[], 3]           = [3]
// step 1 (unwind): [...[3], 2]          = [3, 2]
// step 0 (unwind): [...[3, 2], 1]       = [3, 2, 1]

Đặt Head sau kết quả đệ quy chính là thứ lật thứ tự — mỗi head chờ ở cuối trong khi các lời gọi trong giải quyết.

Cạm bẫy

• Không đệ quy đuôi — [...Reverse<Tail>, Head] bọc lời gọi đệ quy trong spread, nên TypeScript không tối ưu đệ quy đuôi; tuple dài có thể chạm giới hạn ~50.
• Sửa bằng accumulator — ReverseAcc<T, Acc> prepend mỗi Head vào Acc khi đi xuống, biến lời gọi thành đệ quy đuôi (xem mục giới hạn độ sâu bên dưới).

Tóm tắt: đảo đuôi trước, đẩy head sau — [...Reverse<Tail>, Head].

type Equal<X, Y> =
  (<T>() => T extends X ? 1 : 2) extends (<T>() => T extends Y ? 1 : 2)
    ? true
    : false;

type Includes<T extends readonly any[], U> = T extends [infer Head, ...infer Tail]
  ? Equal<Head, U> extends true
    ? true
    : Includes<Tail, U>
  : false;

Từng dòng

Equal<X, Y> — kiểm tra assignability hai chiều qua tham số hàm contravariant; trả true chỉ khi X và Y cùng type, không chỉ assignable.

Includes

type Includes<T extends readonly any[], U> = T extends [infer Head, ...infer Tail]
//                                          peel one element

  ? Equal<Head, U> extends true
//  ^^^^^^^^^^^^^^^^^^^^^^^^^^^
//  strict equality check — not Head extends U

    ? true
//    ^^^^
//    found it — short-circuit, stop searching

    : Includes<Tail, U>
//    ^^^^^^^^^^^^^^^^^
//    not equal — keep searching in the rest

  : false;
//  ^^^^^
//  empty tuple — never found U

1. Bóc Head ở đầu.
2. nếu bằng chặt, trả true ngay (không cần xét đuôi).
3. ngược lại đệ quy Tail.
4. Tuple rỗng → false.

Đánh giá cụ thể

// step 0: Includes<[1, 2, 3], 2>
//   Head = 1, Tail = [2, 3]
//   Equal<1, 2> → false  →  recurse Includes<[2, 3], 2>

// step 1: Includes<[2, 3], 2>
//   Head = 2, Tail = [3]
//   Equal<2, 2> → true  →  short-circuit: true

// result: true

Đánh giá cụ thể

// step 0: Includes<[boolean], false>
//   Head = boolean, Tail = []
//   Equal<boolean, false> → false  (not equal — false is narrower)
//   recurse Includes<[], false>

// step 1: Includes<[], false>
//   [] → base case → false

// result: false  ✅ correct (naive Head extends U would have returned true)

Cạm bẫy

• extends vs Equal — dùng extends khi ý là “assignable tới”; dùng Equal khi test đòi đúng identity type.
• Thoát sớm — trả true khi khớp nghĩa là không quét phần còn lại; false chỉ khi hết cả tuple.
• readonly — ràng buộc readonly any[] nhận cả input tuple mutable lẫn readonly.

Tóm tắt: bóc, Equal<Head, U>, short-circuit khi true, không thì đệ quy — không dùng extends thường cho thành viên chính xác.

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

Từng dòng

type Flatten<T extends any[]> = T extends [infer Head, ...infer Tail]
//                                peel Head + Tail

  ? Head extends any[]
//  ^^^^^^^^^^^^^^^^^^
//  branch: is Head nested?

    ? [...Flatten<Head>, ...Flatten<Tail>]
//    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//    Head is array → flatten BOTH Head and Tail, concat

    : [Head, ...Flatten<Tail>]
//    ^^^^^^^^^^^^^^^^^^^^^^^^
//    Head is leaf → keep Head, flatten only Tail

  : [];
//  base case: empty → []

1. Đệ quy ngoài — T extends [infer Head, ...infer Tail] duyệt danh sách tầng trên.
2. Đệ quy trong — Head extends any[] quyết định khoan vào Head hay coi là lá.
3. Nối — spread (...) lắp lại các mảnh đã phẳng theo thứ tự.
4. Base case — [] → [].

Đánh giá cụ thể

// step 0: Flatten<[1, [2, 3]]>
//   Head = 1, Tail = [[2, 3]]
//   1 is NOT an array  →  [1, ...Flatten<[[2, 3]]>]

// step 1: Flatten<[[2, 3]]>
//   Head = [2, 3], Tail = []
//   [2, 3] IS an array  →  [...Flatten<[2, 3]>, ...Flatten<[]>]

// step 2: Flatten<[2, 3]>
//   Head = 2, Tail = [3]
//   2 is NOT an array  →  [2, ...Flatten<[3]>]

// step 3: Flatten<[3]>
//   Head = 3, Tail = []
//   3 is NOT an array  →  [3, ...Flatten<[]>]

// step 4: Flatten<[]>
//   base case  →  []

// unwind step 3: [3, ...[]]           = [3]
// unwind step 2: [2, ...[3]]          = [2, 3]
// unwind step 1: [...[2, 3], ...[]]   = [2, 3]
// unwind step 0: [1, ...[2, 3]]       = [1, 2, 3]

Cạm bẫy

• Đệ quy hai chiều — giới hạn độ sâu áp cho cả độ dài danh sách lẫn độ sâu lồng; lồng rất sâu có thể lỗi dù tuple ngắn.
• any[] vs tuple — Head extends any[] khớp cả [2, 3] lẫn Array<number>; bài coi mọi kiểu mảng là có thể lồng.
• Viết lại đệ quy đuôi — bài nâng cao cuối dùng accumulator để chịu lồng sâu hơn.

Tóm tắt: mỗi head, rẽ nhánh “có phải mảng?” — làm phẳng vào trong hoặc giữ làm lá, luôn đệ quy đuôi.

type Join<
  T extends (string | number)[],
  U extends string | number,
> = T extends [
  infer Head extends string | number,
  ...infer Tail extends (string | number)[],
]
  ? Tail['length'] extends 0
    ? `${Head}`
    : `${Head}${U}${Join<Tail, U>}`
  : '';

Từng dòng

type Join<T extends (string | number)[], U extends string | number> =
//     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^    ^^^^^^^^^^^^^^^^^^^^^^^^
//     elements must be string | number      separator too

  T extends [
    infer Head extends string | number,
//  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//  constrained infer — Head is usable in `${Head}`

    ...infer Tail extends (string | number)[],
//  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//  rest of tuple, also constrained
  ]

  ? Tail['length'] extends 0
//  ^^^^^^^^^^^^^^^^^^^^^^^^
//  is Tail empty? → Head is the LAST element

    ? `${Head}`
//    ^^^^^^^^^
//    last element: no separator after

    : `${Head}${U}${Join<Tail, U>}`
//    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//    not last: emit Head + separator + recurse

  : '';
//  ^^
//  empty tuple → empty string

1. infer có ràng buộc — không có extends string | number, Head có thể infer quá rộng cho template literal.
2. Tail['length'] extends 0 — độ dài tuple là literal type số; [] có length 0.
3. Nhánh phần tử cuối — chỉ `${Head}`, tránh U thừa cuối.
4. Nhánh đệ quy — dán Head, dấu ngăn U, và phần còn lại.
5. Base case — tuple rỗng → ''.

Đánh giá cụ thể

// step 0: Join<['a', 'b', 'c'], '-'>
//   Head = 'a', Tail = ['b', 'c']
//   Tail['length'] = 2, not 0  →  `a-${Join<['b', 'c'], '-'>}`

// step 1: Join<['b', 'c'], '-'>
//   Head = 'b', Tail = ['c']
//   Tail['length'] = 1, not 0  →  `b-${Join<['c'], '-'>}`

// step 2: Join<['c'], '-'>
//   Head = 'c', Tail = []
//   Tail['length'] = 0  →  last element  →  `c`

// unwind step 1: `b-c`
// unwind step 0: `a-b-c`

Đánh giá cụ thể

// step 0: Join<['你', '好'], 1>
//   Head = '你', Tail = ['好']
//   Tail['length'] = 1, not 0  →  `你1${Join<['好'], 1>}`

// step 1: Join<['好'], 1>
//   Head = '好', Tail = []
//   Tail['length'] = 0  →  `好`

// unwind: `你1好`

Cạm bẫy

• Tail['length'] extends 0 vs Tail extends [] — cả hai phát hiện đuôi rỗng; length là style type-challenges quen thuộc.
• Kiểu dấu ngăn — U extends string | number cho phép dấu ngăn số như 1 trong ví dụ apple.
• Tuple một phần tử — Join<['x'], '-']> vào nhánh cuối ngay → 'x', không phải 'x-'.

Tóm tắt: bóc Head, kiểm Tail['length'] extends 0 cho phần tử cuối, không thì `${Head}${U}${Join<Tail, U>}`.

type ToUnion<U> = U extends any[] ? U[number] : U;

type Without<T extends any[], U> = T extends [infer H, ...infer R]
  ? H extends ToUnion<U>
    ? Without<R, U>
    : [H, ...Without<R, U>]
  : [];

Cơ chế: chuẩn hoá U thành union qua ToUnion, rồi với mỗi Head hoặc bỏ (khi H extends ToUnion<U>) hoặc giữ và đệ quy.

// Without<[1, 2, 3, 4], [2, 4]>
// step 0: H=1, 1 extends 2|4? no  →  [1, ...Without<[2,3,4], [2,4]>]
// step 1: H=2, 2 extends 2|4? yes →  skip  →  Without<[3,4], [2,4]>
// step 2: H=3, 3 extends 2|4? no  →  [3, ...Without<[4], [2,4]>]
// step 3: H=4, 4 extends 2|4? yes →  skip  →  Without<[], [2,4]> → []
// unwind: [1, 3]

Test của Without dùng literal khác biệt nên extends và Equal cho cùng kết quả — xoá “mọi thứ assignable tới 2 | 4” là ngữ nghĩa đúng. Includes có ca ([boolean] vs false) mà assignable ≠ equal: false extends boolean là true, nhưng Equal<boolean, false> là false. Luôn đọc test để biết bài cần thành viên (chính xác) hay lọc (assignable).