Persistent Immutable List

A persistent (immutable) list is one where every update returns a new version of the list and the old version keeps working, unchanged, forever. The trick that makes this affordable is structural sharing: the new version reuses the nodes that did not change instead of deep-copying the whole list. This is the idea behind Immutable.js, Clojure's collections, and the way Redux and React state produce a new object on each update while keeping the old one intact. You will build one backed by a singly-linked chain of immutable { value, next } cells — a cons list — where items[0] is the front. See persistent data structure for background.

Signature

function persistentImmutableList(...items: unknown[]): ImmutableList;

interface ImmutableList {
  prepend(value: unknown): ImmutableList;         // NEW list with value at the front (O(1))
  first(): unknown | undefined;                   // front value, or undefined if empty
  rest(): ImmutableList;                          // the shared tail, or the empty list
  get(i: number): unknown | undefined;            // value at index i, or undefined if out of range
  set(i: number, value: unknown): ImmutableList;  // NEW list with index i replaced; RangeError if out of range
  size(): number;                                 // element count
  isEmpty(): boolean;                             // no elements?
  toArray(): unknown[];                           // values front-to-back
}

Every method that "changes" the list returns a brand-new list; the list you called it on is never modified.

Examples

const base = persistentImmutableList(1, 2, 3);
base.toArray(); // [1, 2, 3]
base.first();   // 1
base.size();    // 3

const bigger = base.prepend(0);
bigger.toArray(); // [0, 1, 2, 3]
base.toArray();   // [1, 2, 3] — the original is untouched

const changed = base.set(1, 99);
changed.toArray(); // [1, 99, 3]
base.toArray();    // [1, 2, 3] — still intact

// The tail is shared, not copied: rest() hands back the very list we grew from.
base.prepend(0).rest() === base; // true

Notes

• Immutable — every update returns a new list. No method mutates the list it was called on, so a version handed out earlier always reads the same.
• O(1) prepend — adding to the front allocates a single node whose next points at the entire current list, shared by reference. Nothing is copied.
• set copies only the prefix — set(i, value) rebuilds the nodes at indices 0..i and shares everything from i + 1 onward. An out-of-range i throws a RangeError.
• Out of range — get(i) returns undefined for an index outside 0..size - 1; set throws instead. Mind the asymmetry.
• The empty list — call persistentImmutableList() with no arguments for the empty list: size() is 0, first() and get() return undefined, and rest() is the empty list again.
• Front-indexed — index 0 is the front (the head). items[0] becomes the first element; prepend and rest both act on the front.