jonnifyfsharp

Dive C2.04.3

From the Visitor pattern to a recursive DU

A tree of node types is data; the operation that walks it is a function.

When a hierarchy is a tree — an expression of numbers, additions, and multiplications, where each operand is itself an expression — C# has a problem. An operation that walks the tree cannot live as a single switch, because the language prefers dispatch on the node type; the classic answer is the Visitor pattern: an IVisitor interface, an Accept method on every node, and double dispatch to route each node to its visit method. F# needs none of it. A recursive discriminated union describes the tree — type Expr = Num of int | Add of Expr * Expr | Mul of Expr * Expr — and a recursive match walks it (verified: val eval : Expr -> int, eval (Add (Num 1, Mul (Num 2, Num 3))) is 7). The tree is data; the fold over it is one function. This dive closes the module on the case the pattern was built for.

Evaluate a tree Module hub
C2.04.3 · part 1

A union that references itself

A discriminated union becomes a tree when a case carries the union's own type. Expr has a leaf case, Num of int, and two branch cases, Add and Mul, each holding two more Expr values. There is no separate node interface and no base class — the one type is the whole grammar, and a value of it is a whole expression.

type Expr =
    | Num of int
    | Add of Expr * Expr
    | Mul of Expr * Expr

A value is built by nesting cases. Add (Num 1, Mul (Num 2, Num 3)) is the tree "one, plus the product of two and three" — an Add whose left operand is a Num and whose right operand is a Mul. The structure is the value; nothing else is needed to represent it.

let e = Add (Num 1, Mul (Num 2, Num 3))
// val e : Expr = Add (Num 1, Mul (Num 2, Num 3))
recursive DU
a union whose cases reference the union — Add of Expr * Expr — so a value is a tree of arbitrary depth.
Num
the leaf case: an int, the base of the recursion.
Add / Mul
branch cases, each holding two sub-expressions; the tree grows by nesting them.
vs. Visitor
no IVisitor, no Accept — the node types are the union's cases, named in one place.
C2.04.3 · part 2

A recursive match walks the tree

The operation is one function marked rec. eval matches the three cases: a Num returns its number, and an Add or Mul evaluates each sub-expression — calling eval again — and combines the results. The recursion bottoms out at the Num leaves and folds back up. The FSI echo is exact.

let rec eval e =                       // val eval : Expr -> int
    match e with
    | Num n -> n
    | Add (a, b) -> eval a + eval b
    | Mul (a, b) -> eval a * eval b

eval (Add (Num 1, Mul (Num 2, Num 3)))   // val it : int = 7

The C# version of this is the Visitor pattern. The node hierarchy needs an IExprVisitor with a Visit overload per node type, every node needs an Accept(visitor) method, and the evaluator is a visitor class whose Visit methods recurse through Accept — double dispatch, spread across the node classes and the visitor. The F# fold is the four lines above.

C# — the Visitor pattern: an interface, an Accept per node, double dispatch

interface IExprVisitor<T> { T Num(int n); T Add(Expr a, Expr b); T Mul(Expr a, Expr b); }
abstract class Expr { public abstract T Accept<T>(IExprVisitor<T> v); }
class NumE : Expr { public int N; public override T Accept<T>(IExprVisitor<T> v) => v.Num(N); }
class AddE : Expr { public Expr A, B; public override T Accept<T>(IExprVisitor<T> v) => v.Add(A, B); }
// ...plus a MulE, plus an EvalVisitor whose Add/Mul call a.Accept(this) — double dispatch

F# — a recursive union and a recursive match

type Expr = | Num of int | Add of Expr * Expr | Mul of Expr * Expr
let rec eval e =
    match e with
    | Num n -> n
    | Add (a, b) -> eval a + eval b
    | Mul (a, b) -> eval a * eval b
eval (Add (Num 1, Mul (Num 2, Num 3)))   // val it : int = 7

Step eval over the tree

The tree is Add (Num 1, Mul (Num 2, Num 3)). Step the recursion: each press evaluates the next node, deepest first, lighting it and posting its result, until the values fold up to the root. The leaves return their numbers; Mul multiplies its two; Add adds its two; the root lands on 7 — the value dotnet fsi prints for eval e.

eval (Add (Num 1, Mul (Num 2, Num 3))) · fold the tree

step 0 of 5
Add a + b = 7 Num 1 = 1 Mul a * b = 6 Num 2 = 2 Num 3 = 3
ready · eval (Add (Num 1, Mul (Num 2, Num 3))) — step to fold the tree, deepest first.
Without JavaScript: the fold, deepest node first
stepnodematch armresult
1Num 2| Num n -> n2
2Num 3| Num n -> n3
3Mul (2, 3)| Mul (a, b) -> eval a * eval b6
4Num 1| Num n -> n1
5Add (1, 6)| Add (a, b) -> eval a + eval b7

The tree is the value, and one recursive match reads it to the bottom and back. The pattern that took an interface and a method on every node is four lines that name the cases.

C2.04.3 · part 3

Why the pattern disappears

The Visitor pattern exists to add operations to a node hierarchy without editing every node class — it routes a node to the right visit method through Accept. A recursive DU removes the problem it solves: the node types are the union's cases, an operation is one recursive function that matches them, and a second operation — pretty-printing, simplifying, counting nodes — is a second function over the same union. The exhaustiveness check from the last dive still holds: forget a case in eval and the compiler warns FS0025.

A second operation over Expr is a new function, not a new visitor. let rec show e = match e with Num n -> string n | Add (a, b) -> show a + " + " + show b | Mul (a, b) -> show a + " * " + show b walks the same tree to a string, leaving eval and the union untouched.

C# habit

The Visitor pattern: an IVisitor, an Accept on every node, and double dispatch to walk a tree of node types.

F# form

A recursive union for the tree and a recursive match for the walk — the data named once, the fold a single function.

The module, closed

Across the three dives, an inheritance habit became a union: the class hierarchy became a closed set of cases, virtual dispatch became one exhaustive match, and the Visitor pattern became a recursive DU read by a recursive fold. Data sits in the union; behaviour sits in free functions; the compiler checks that the functions cover the data. That is the shape a C# team reaches for first in F#.

↑ C2.04 · From inheritance to discriminated unions C2.04.1 · From a class hierarchy to a DU C2.04.2 · From virtual dispatch to exhaustive match

References

Sources

Related in this course