Visitor pattern vs sum types and pattern matching

index.ts

// First, let's look at the traditional visitor pattern
// This is how we might implement a simple expression evaluator

// Traditional Visitor Pattern
namespace Traditional {
  // Abstract base class for expressions
  abstract class Expr {
    abstract accept<T>(visitor: ExprVisitor<T>): T;
  }

  // Concrete expression classes
  class NumberExpr extends Expr {
    constructor(public value: number) {
      super();
    }

    accept<T>(visitor: ExprVisitor<T>): T {
      return visitor.visitNumber(this);
    }
  }

  class AddExpr extends Expr {
    constructor(public left: Expr, public right: Expr) {
      super();
    }

    accept<T>(visitor: ExprVisitor<T>): T {
      return visitor.visitAdd(this);
    }
  }

  class MultiplyExpr extends Expr {
    constructor(public left: Expr, public right: Expr) {
      super();
    }

    accept<T>(visitor: ExprVisitor<T>): T {
      return visitor.visitMultiply(this);
    }
  }

  // Visitor interface
  interface ExprVisitor<T> {
    visitNumber(expr: NumberExpr): T;
    visitAdd(expr: AddExpr): T;
    visitMultiply(expr: MultiplyExpr): T;
  }

  // Concrete visitor that evaluates expressions
  class Evaluator implements ExprVisitor<number> {
    visitNumber(expr: NumberExpr): number {
      return expr.value;
    }

    visitAdd(expr: AddExpr): number {
      return expr.left.accept(this) + expr.right.accept(this);
    }

    visitMultiply(expr: MultiplyExpr): number {
      return expr.left.accept(this) * expr.right.accept(this);
    }
  }

  // Usage example
  const expr = new AddExpr(
    new NumberExpr(5),
    new MultiplyExpr(new NumberExpr(2), new NumberExpr(3))
  );
  const evaluator = new Evaluator();
  console.log(expr.accept(evaluator)); // Outputs: 11
}

// Now, let's see how we can represent the same thing using sum types
// and pattern matching in TypeScript

namespace Modern {
  // Sum type representing all possible expressions
  type Expr =
    | { type: 'number'; value: number }
    | { type: 'add'; left: Expr; right: Expr }
    | { type: 'multiply'; left: Expr; right: Expr };

  // Helper functions to create expressions (optional but convenient)
  const num = (value: number): Expr => ({ type: 'number', value });
  const add = (left: Expr, right: Expr): Expr => ({ type: 'add', left, right });
  const multiply = (left: Expr, right: Expr): Expr => ({ type: 'multiply', left, right });

  // Evaluation function using pattern matching
  function evaluate(expr: Expr): number {
    switch (expr.type) {
      case 'number':
        return expr.value;
      case 'add':
        return evaluate(expr.left) + evaluate(expr.right);
      case 'multiply':
        return evaluate(expr.left) * evaluate(expr.right);
    }
  }

  // We can easily add new operations without modifying existing code
  function stringify(expr: Expr): string {
    switch (expr.type) {
      case 'number':
        return expr.value.toString();
      case 'add':
        return `(${stringify(expr.left)} + ${stringify(expr.right)})`;
      case 'multiply':
        return `(${stringify(expr.left)} * ${stringify(expr.right)})`;
    }
  }

  // Usage example
  const expr = add(
    num(5),
    multiply(num(2), num(3))
  );
  console.log(evaluate(expr)); // Outputs: 11
  console.log(stringify(expr)); // Outputs: (5 + (2 * 3))
}

// Key differences and advantages of the modern approach:
// 1. No class hierarchy or inheritance needed
// 2. No need for accept methods or visitor interfaces
// 3. Adding new operations is just creating new functions
// 4. Pattern matching makes it impossible to forget handling a case
// 5. The compiler ensures exhaustive matching
// 6. More functional and declarative style
// 7. Easier to serialize/deserialize
// 8. Better type inference and safety