การกำหนดชนิดข้อมูลแบบเรียกซ้ำ

ชนิดแบบเรียกตัวเองคืออะไร

type LinkedList<T> = {
  value: T;
  next: LinkedList<T> | null;
};
// next is the same type again, ending at null.

ชนิดลิงก์ลิสต์

type LinkedList<T> = { value: T; next: LinkedList<T> | null };
const list: LinkedList<number> = {
  value: 1,
  next: { value: 2, next: null }
};
console.log(list.value, list.next?.value);

กรณีฐานมีความสำคัญ

type LinkedList<T> = { value: T; next: LinkedList<T> | null };
const single: LinkedList<string> = { value: "only", next: null };
console.log(single.next);

สร้างสายโซ่ให้ยาวขึ้น

type LinkedList<T> = { value: T; next: LinkedList<T> | null };
const chain: LinkedList<number> = {
  value: 10,
  next: { value: 20, next: { value: 30, next: null } }
};
console.log(chain.next?.next?.value);

เดินผ่านลิงก์ลิสต์

type LinkedList<T> = { value: T; next: LinkedList<T> | null };
function toArray<T>(list: LinkedList<T> | null): T[] {
  const out: T[] = [];
  let cur = list;
  while (cur) { out.push(cur.value); cur = cur.next; }
  return out;
}
const l: LinkedList<number> = { value: 1, next: { value: 2, next: null } };
console.log(toArray(l));

ฟังก์ชันแบบเรียกตัวเองกับชนิดแบบเรียกตัวเอง

type LinkedList<T> = { value: T; next: LinkedList<T> | null };
function length<T>(list: LinkedList<T> | null): number {
  return list === null ? 0 : 1 + length(list.next);
}
const l: LinkedList<string> = { value: "a", next: { value: "b", next: null } };
console.log(length(l));

เพิ่มสมาชิกไว้หน้าลิสต์

type LinkedList<T> = { value: T; next: LinkedList<T> | null };
function prepend<T>(value: T, list: LinkedList<T> | null): LinkedList<T> {
  return { value, next: list };
}
const l = prepend(1, prepend(2, null));
console.log(l.value, l.next?.value);

ตัวสิ้นสุดแบบเลือกมีค่ากับแบบอนุญาตให้เป็น null

type ListA<T> = { value: T; next: ListA<T> | null };
type ListB<T> = { value: T; next?: ListB<T> };
const a: ListA<number> = { value: 1, next: null };
const b: ListB<number> = { value: 1 };
console.log(a.value, b.value);

ชนิดแบบเรียกตัวเองจะขยายอย่างชะลอ

type LinkedList<T> = { value: T; next: LinkedList<T> | null };
// Using two levels only expands two levels.
const l: LinkedList<number> = { value: 1, next: { value: 2, next: null } };
console.log(l.next?.value);

แปลงค่าทั่วทั้งลิสต์

type LinkedList<T> = { value: T; next: LinkedList<T> | null };
function mapList<T, U>(list: LinkedList<T> | null, fn: (v: T) => U): LinkedList<U> | null {
  if (list === null) return null;
  return { value: fn(list.value), next: mapList(list.next, fn) };
}
const l: LinkedList<number> = { value: 1, next: { value: 2, next: null } };
console.log(mapList(l, x => x * 10)?.value);

เหตุใดชนิดแบบเรียกตัวเองจึงทรงพลัง

type LinkedList<T> = { value: T; next: LinkedList<T> | null };
const l: LinkedList<boolean> = { value: true, next: { value: false, next: null } };
console.log(l.value, l.next?.value);

ตรวจสอบความเข้าใจอย่างรวดเร็ว: ชนิดแบบเรียกตัวเอง

ทบทวน: นิยามชนิดแบบเรียกตัวเอง

type LinkedList<T> = { value: T; next: LinkedList<T> | null };
const l: LinkedList<number> = { value: 1, next: null };
console.log(l.value);