Chapter 12: Behavioral Patterns V: Iterator & Visitor

Iterator

The problem it solves: you want to traverse a collection's elements sequentially without exposing its internal structure (an array, a tree, a linked list) to the code doing the traversal — so the collection's internal representation can change without breaking every piece of code that iterates over it.

interface Iterator<T> {
  hasNext(): boolean;
  next(): T;
}

class BinaryTreeNode<T> {
  left: BinaryTreeNode<T> | null = null;
  right: BinaryTreeNode<T> | null = null;
  constructor(public value: T) {}
}

class InOrderIterator<T> implements Iterator<T> {
  private stack: BinaryTreeNode<T>[] = [];

  constructor(root: BinaryTreeNode<T> | null) {
    this.pushLeft(root);
  }

  private pushLeft(node: BinaryTreeNode<T> | null): void {
    while (node) { this.stack.push(node); node = node.left; }
  }

  hasNext(): boolean { return this.stack.length > 0; }

  next(): T {
    const node = this.stack.pop()!;
    this.pushLeft(node.right);
    return node.value; // caller gets values in order, with zero knowledge of the tree's internal shape
  }
}

// Caller code doesn't know or care that this is a tree with a stack-based traversal internally:
const root = new BinaryTreeNode(5);
root.left = new BinaryTreeNode(3);
root.right = new BinaryTreeNode(8);
const it = new InOrderIterator(root);
while (it.hasNext()) console.log(it.next()); // 3, 5, 8

class InOrderIterator:
    def __init__(self, root: "BinaryTreeNode | None") -> None:
        self._stack: list[BinaryTreeNode] = []
        self._push_left(root)

    def _push_left(self, node: "BinaryTreeNode | None") -> None:
        while node:
            self._stack.append(node)
            node = node.left

    def __iter__(self) -> "InOrderIterator":
        return self

    def __next__(self):
        if not self._stack:
            raise StopIteration
        node = self._stack.pop()
        self._push_left(node.right)
        return node.value

[IN PRACTICE] Both languages have first-class support for this pattern built directly into their syntax — TypeScript/JavaScript's for...of works with anything implementing Symbol.iterator; Python's for...in works with anything implementing __iter__/__next__ (as shown above). This is worth calling out explicitly: you rarely need to hand-roll the Iterator pattern's interface from scratch in modern code — you implement your language's native iteration protocol instead, and get for...of/for...in support for free.

When to use it: you have a custom collection type (a tree, a graph, a paginated remote data source) and want consumers to traverse it with standard language iteration syntax, without knowing its internal structure.

When to avoid it: the underlying collection is already a built-in array/list — wrapping it in a custom iterator adds nothing, since the language's native iteration already works.

Complexity cost: low, especially when implemented via your language's native iteration protocol rather than a hand-rolled interface — one of the cheapest patterns in the catalog when it's actually needed (a genuinely custom traversal), because it plugs directly into syntax the language already provides.

Visitor

The problem it solves: you need to add a new operation across a family of related classes, without modifying each class every time a new operation is added — the inverse problem from Chapter 3's Open/Closed discussion, which was about adding new types easily; Visitor is for adding new operations easily, at the cost of making new types harder to add.

Before — adding a new operation means touching every class in the family:

interface Shape {
  area(): number;
  // Adding "exportToSvg()" here means implementing it in every Shape subclass.
}

After — Visitor moves the operation outside the type hierarchy:

interface ShapeVisitor {
  visitCircle(circle: Circle): string;
  visitSquare(square: Square): string;
}

interface Shape {
  accept(visitor: ShapeVisitor): string; // the one method every Shape needs, ever
}

class Circle implements Shape {
  constructor(public radius: number) {}
  accept(visitor: ShapeVisitor): string { return visitor.visitCircle(this); }
}
class Square implements Shape {
  constructor(public side: number) {}
  accept(visitor: ShapeVisitor): string { return visitor.visitSquare(this); }
}

// A new operation ("export to SVG") is a new Visitor — no Shape class needs to change:
class SvgExportVisitor implements ShapeVisitor {
  visitCircle(circle: Circle): string { return `<circle r="${circle.radius}" />`; }
  visitSquare(square: Square): string { return `<rect width="${square.side}" height="${square.side}" />`; }
}

// A second new operation, again with zero changes to Circle or Square:
class AreaVisitor implements ShapeVisitor {
  visitCircle(circle: Circle): string { return String(Math.PI * circle.radius ** 2); }
  visitSquare(square: Square): string { return String(square.side ** 2); }
}

const shapes: Shape[] = [new Circle(3), new Square(4)];
const svgExporter = new SvgExportVisitor();
shapes.forEach(s => console.log(s.accept(svgExporter)));

from abc import ABC, abstractmethod

class ShapeVisitor(ABC):
    @abstractmethod
    def visit_circle(self, circle: "Circle") -> str: ...
    @abstractmethod
    def visit_square(self, square: "Square") -> str: ...

class Shape(ABC):
    @abstractmethod
    def accept(self, visitor: ShapeVisitor) -> str: ...

class Circle(Shape):
    def __init__(self, radius: float) -> None:
        self.radius = radius
    def accept(self, visitor: ShapeVisitor) -> str:
        return visitor.visit_circle(self)

class SvgExportVisitor(ShapeVisitor):
    def visit_circle(self, circle: Circle) -> str:
        return f'<circle r="{circle.radius}" />'

[SENIOR INSIGHT] Visitor is the clearest example in this book of a genuine trade-off with no free lunch: it inverts Open/Closed relative to a normal type hierarchy. Adding a new operation (a new Visitor) requires zero changes to existing Shape classes. But adding a new type (a new Triangle class) requires updating the ShapeVisitor interface and every existing visitor implementation — the exact opposite trade-off from ordinary polymorphism (OOP book, Chapter 6), where adding a new type is cheap and adding a new operation across all types is what's expensive. Choosing Visitor is a bet that your system's family of types is stable and its set of operations is what's actually going to keep growing — get that bet wrong, and Visitor makes your code harder to extend, not easier.

When to use it: the set of types in a hierarchy is stable (rarely changes) and you anticipate needing to add many new operations across that hierarchy over time — compilers and interpreters (walking a stable set of AST node types with many different passes: type-checking, optimization, code generation) are the classic real-world case.

When to avoid it: the set of types is what's actually expected to grow and change, while operations are stable — that's the normal polymorphism case (OOP book, Chapter 6), and Visitor would make adding each new type unnecessarily expensive.

Complexity cost: significant — an extra interface, an accept method on every type, and every visitor implementing every type. This is the most structurally complex pattern in this chapter, and its cost is only justified by the specific type-stable/operation-growing bet described above.

Common mistakes

1. Hand-rolling an Iterator interface when the language's native iteration protocol already covers the need — unnecessary reinvention in TypeScript/JavaScript (Symbol.iterator) and Python (__iter__/__next__).
2. Choosing Visitor when types are actually what's growing, not operations — this is the costliest possible mismatch, since every new type then requires editing every existing visitor, the opposite of the intended payoff.
3. Underestimating Visitor's cost during initial design because the first one or two operations feel manageable — the pain shows up specifically when a new type needs to be added later and the interface (and every visitor) has to change.
4. Using Visitor for a small, stable, unlikely-to-grow set of operations where straightforward methods on each type would be simpler — Visitor's indirection only pays for itself against genuine, anticipated operation growth.

Discussion / interview questions

1. "What problem does Visitor solve, and what does it cost in exchange?" Strong answer: Lets you add new operations across a family of types without modifying the types themselves; in exchange, adding a new type requires updating the visitor interface and every existing visitor implementation — an inversion of ordinary polymorphism's trade-off.

2. "When would Visitor be the wrong choice, even though the 'family of types with shared operations' shape seems to fit?" Strong answer: When the set of types is what's actually expected to grow, while operations are stable — Visitor makes each new type expensive, which is the opposite of what's needed in that situation; ordinary polymorphism fits better there.

3. "Why don't you usually need to implement the Iterator pattern's classic interface by hand in a modern TypeScript or Python codebase?" Strong answer: Both languages have native iteration protocols (Symbol.iterator / for...of, __iter__/__next__ / for...in) built into the language — implementing those gets standard iteration syntax for free, without a hand-rolled hasNext()/next() interface.

4. "Give a real-world example where Visitor is the right choice, and explain why the type-hierarchy is stable there." Strong answer: A compiler's AST — node types (literal, binary expression, function call, etc.) are relatively fixed once a language's grammar is defined, while operations over that AST (type-checking, optimization passes, code generation, pretty-printing) keep growing — exactly the type-stable/operation-growing shape Visitor is built for.

Chapter summary / cheat sheet

• Iterator: traverses a collection without exposing its internal structure — usually implemented via your language's native iteration protocol rather than a hand-rolled interface.
• Visitor: adds new operations across a family of types without modifying the types — at the cost of making new types expensive to add (every visitor must be updated). An explicit bet that types are stable and operations will keep growing.
• Visitor is the clearest "no free lunch" trade-off in the pattern catalog — verify which axis (types or operations) is actually expected to grow before choosing it.
• With behavioral patterns now complete (Chapters 8–12), the next chapter turns to what happens when any of these patterns are applied without this chapter-by-chapter discipline of checking the real, current need first.

---