Composite

Work out the total size of a folder. It contains files, and other folders, which contain files, and other folders.

What people write first

Check what kind of thing each child is.

function size(node: File | Folder): number {
  if (node instanceof File) return node.bytes;

  let total = 0;
  for (const child of node.children) {
    if (child instanceof File) total += child.bytes;      // the check, again
    else total += size(child);
  }
  return total;
}

That check will appear in every operation: size, count, search, render, delete. Five functions, each carrying the same two-way branch, each a place to forget the folder case.

The pattern

Give the container and the item the same interface, and let the container’s implementation recurse.

interface Node {
  name: string;
  size(): number;
}

class FileNode implements Node {
  constructor(readonly name: string, private readonly bytes: number) {}
  size() { return this.bytes; }                          // base case
}

class FolderNode implements Node {
  constructor(readonly name: string, private readonly children: Node[]) {}

  size() {
    // No instanceof. Children are Nodes; Nodes know their own size.
    return this.children.reduce((total, child) => total + child.size(), 0);
  }
}

Click any row — files and folders answer the same question:

The awkward question

What is the interface, exactly? There are two answers and the catalogue is famously ambivalent about which is right.

Uniform — put add(child) on Node, so every node has it. Callers never type-check, and file.add(x) throws at runtime.

Safe — put add(child) only on FolderNode. Now the type system prevents the nonsense, and callers that want to add something must know they have a folder.

Where you have met it

The DOM: an element and a text node both answer textContent. React: a component returns elements, which may be components. Every abstract syntax tree. Every UI layout system, where a panel is a widget containing widgets.

Also, importantly, menus and permissions — a permission group containing permissions and other groups is the same shape, and so is an org chart.

What it costs

Type information is lost at the boundary. The interface is the intersection of leaf and container, so callers holding a Node cannot do folder things without narrowing.

Deep trees blow the stack. The recursion is as deep as the tree. A traversal with an explicit stack is the fix, at some cost in readability.

Cycles are fatal. If two folders can contain each other, size() never returns. Trees are assumed, and nothing enforces it — if your structure can gain a cycle, you need a visited set, and at that point you have a graph rather than a composite.