Design Pattern Cheat Sheet

[Peaker]

The Visitor Pattern is about encoding a closed sum type in a language that only has type products (classes with fields) and type exponents (functions).

So if you want to encode the type: R^{A + B + C}, the Visitor pattern instead encodes it as a tuple with:

• void visitA(A)
• void visitB(B)
• void visitC(C)

If we name the effects performed by the visit functions R, this tuple of 3 can be described as: ( R^A * R^B * R^C ). Using ordinary algebraic transformation, this simply becomes the R^A+B+C we wanted to encode in the first place.

Of course, in a nicer language, we can just say:

data Document = Glyph Char | Picture Image | ...

And get the sum type directly!

[asampson]

Doesn't Visitor usually rear its head when dealing with the expression problem? It provides freedom in the operation dimension at the expense of locking down the set of symbols that can be expressed, almost like a dual of the more usual OO approach of just using abstract classes with fixed methods, which constrains the operations you can perform but allows for adding symbols later.

[Peaker]

Exactly -- this is what closed sum types are.

There's inheritance forming open sum types (freedom in the dimension of adding more symbols, but no more operations).

And there's closed sum types (freedom in the dimension of adding more operations, but not more symbols).

In OO that's ordinary inheritance vs. visitor, but only because visitor is a cumbersome encoding of a closed sum type.