Commissioned for this museum · after Gamma, Helm, Johnson & Vlissides, 1994

Visitor

TypeScript·1994·38 lines·1205 bytes

/**
 * Visitor — add new operations over a fixed set of shapes, without editing
 * the shapes.
 */
type Node =
	| { kind: "literal"; value: number }
	| { kind: "add"; left: Node; right: Node }
	| { kind: "negate"; operand: Node };

// This mapped type is the pattern's teeth. A visitor must supply a case for
// every kind of node, so adding a fourth kind to Node breaks every visitor
// in the codebase at compile time — which is exactly the reminder you want.
type Visitor<T> = {
	[K in Node["kind"]]: (node: Extract<Node, { kind: K }>) => T;
};

const walk = <T>(node: Node, visitor: Visitor<T>): T =>
	visitor[node.kind](node as never);

const evaluate: Visitor<number> = {
	literal: (n) => n.value,
	add: (n) => walk(n.left, evaluate) + walk(n.right, evaluate),
	negate: (n) => -walk(n.operand, evaluate),
};

const show: Visitor<string> = {
	literal: (n) => String(n.value),
	add: (n) => `(${walk(n.left, show)} + ${walk(n.right, show)})`,
	negate: (n) => `-${walk(n.operand, show)}`,
};

const tree: Node = {
	kind: "add",
	left: { kind: "literal", value: 2 },
	right: { kind: "negate", operand: { kind: "literal", value: 5 } },
};

console.log(`${walk(tree, show)} = ${walk(tree, evaluate)}`);

Curator’s note

This is the pattern people find hardest to love, and it answers a genuinely awkward question: your data has a fixed set of shapes and you keep needing new operations over them. Put each operation on the shapes as a method and every new operation edits every shape. Visitor turns that inside out — the shapes stay closed, and each operation becomes one object holding all the cases.

The trade is not free and deserves to be said plainly. Visitor makes adding an *operation* cheap and adding a *shape* expensive: define a fourth kind of node and every visitor stops compiling. Methods on the shapes make exactly the opposite trade. Neither is correct in general — they are opposing bets about which axis will grow, and betting wrong is why people come to resent this one.

The Visitor<T> mapped type is doing what the 1994 version needed an abstract class and a double-dispatch dance to achieve. It says: one handler per kind, exhaustively, and the compiler will hold you to it. In a language with unions that exhaustiveness is the entire reason to reach for this.

node as never is the one wart, and it is left visible on purpose. At that point walk knows visitor[node.kind] is *some* handler and node is *some* node, but not that the two agree — a fact that is true and that the type system cannot yet follow. Every real implementation has this wrinkle somewhere; hiding it behind an overload would make the exhibit less honest, not less awkward.