The visitor pattern is essentially the same thing as Church encoding

It's particularly weird because most statically-type functional languages have discriminated unions as a practical alternative to the visitor pattern anyway.

Python:

    import math

    def Circle(x, y, r):
        return (lambda visitCircle, visitRectangle : visitCircle(x, y, r))

    def Rectangle(x, y, w, h):
        return (lambda visitCircle, visitRectangle : visitRectangle(x, y, w, h))

    def area(shape):
        return shape(
            lambda x, y, r    : math.pi * r * r,
            lambda x, y, w, h : w * h
        )

    exampleCircle = Circle(2, 1.4, 4.5)
    exampleRectangle = Rectangle(1.3, 3.1, 10.3, 7.7)

    print(area(exampleCircle))
    print(area(exampleRectangle))
    # 63.61725123519331
    # 79.31

Not everything is about hitting nails. This is more about thinking about what hammers and nails are made of. If you don't know Church Encodings already, well typed church encodings are going to be a bad place to start. Personally I would look at the https://en.wikipedia.org/wiki/Mogensen%E2%80%93Scott_encodin... it is simpler to teach as a first functional encoding of data types.

The fact that it is a visitor pattern is linking insight from functional and object oriented design patterns together. I can see the confusion if one only views those design patterns on a practical level. The article is really teaching the Böhm-Berarducci encoding to more experienced functional programmers as a concept not as a hammer to solve problems.

The core essence of the visitor pattern is to implement case distinction on sum types in languages that do not natively support sum types. Double dispatch is merely the mechanism by which the visitor pattern achieves this.

"double dispatch" is not a problem. It's OO epicycles. "Deciding what to do based on the sort of input" is the problem.

The point of these realizations not that "oh, just use church encoding". Church encoding, like the visor pattern, is annoying an obtuse: get a language with pattern marching.

Rather, the point is to show that the theory is legit because it shows up even among the work of those ignorant of it. And church encoding remains useful theory because sometimes it's advantageous to boil everything down to functions.

It's worthwhile noting that the example makes use of more than just typed lambdas. It uses first-class polymorphism right off the bat.

A less-general but arguably more useful connection I've seen drawn is that the Visitor pattern is basically exchangeable with union types + pattern-matching (for languages that have these features); in the same way that objects can be exchanged with closures and iteration can be exchanged with recursion.

Which one of the two is "better" probably comes down to personal preference and/or the language being used, but it's good to know that you have the option.

This is just the kind of thing you file away in the back of your head as "huh, interesting", that may or may not have a practical application down the line. But occasionally the pay off for having a different way of thinking about a problem can be really big.

For example, Joel Spolsky argued a long time ago that Google was able to solve some problems faster than Microsoft because their programmers understood functional programming:

https://www.joelonsoftware.com/2005/12/29/the-perils-of-java...

Will this article have a similar payoff for someone someday? Hard to say, but it was probably not clear to the CS students learning map and reduce it would lead to an elegant solution to how to run computations across a massive computing infrastructure someday, either.

I think you missed the angle of the article. It's just pointing out the isomorphism between Church encoding, the visitor pattern and GADTs. You wouldn't use anything but GADTs in Haskell today, it's just an interesting curiosity unless you're actually a type theorist or something.

This is a valid definition in TypeScript:

    type Shape<T> = (
        circle: (x: number, y: number, r: number) => T,
        rectangle: (x: number, y: number, w: number, h: number) => T
    ) => T;

    function Circle<T>(x: number, y: number, r: number): Shape<T> {
        return (_Circle, _Rectangle) => _Circle(x, y, r);
    }

    function Rectangle<T>(x: number, y: number, w: number, h: number): Shape<T> {
        return (_Circle, _Rectangle) => _Rectangle(x, y, w, h);
    }

    const exampleCircle = Circle(2, 1.4, 4.5);
    const exampleRectangle = Rectangle(1.3, 3.1, 10.3, 7.7);

    function area(shape: Shape<unknown>): number {
        const s = shape as Shape<number>;
        return s(
            (x, y, r) => Math.PI * r * r,
            (x, y, w, h) => w * h
        );
    }

    export function main() {
        console.log(area(exampleCircle));
        console.log(area(exampleRectangle));
    }

Unfortunately I think the cast might be necessary, but happy to see another solution from someone with more typescript expertise.

Here's a slightly different Java example, for variety in the examples you're getting ;) I also recommend checking out the paper on object algebras [0], which takes this approach much further.

Notice that in some sense, the structure of the type is inferable from just the visitor interface. Everything else is just an explosion of boilerplate. (This is somewhat explained in the object algebras framework, as you can have multiple types accepting these visitors, just as much as having multiple visitors for the same type. In other words, this is related to the "expression problem".)

[0] https://www.cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf

    // An "external visitor", with the recursion external to the type being visited.
    // The visitor is responsible for visiting each of the children.
    public interface ExprVisitor1<Result> {
      Result lit(double x);
      Result add(Expr left, Expr right);
      Result sub(Expr left, Expr right);
    }

    // An "internal visitor", with the recursion internal to the type being visited.
    // I like these best, because the recursion can be turned into a tight loop
    // (defunctionalize the continuation!) in a single place (in Expr).
    // But you lose some expressivity, e.g. no short-circuiting the recursion.
    // You can elaborate the recursion scheme of course, e.g.
    //   Result add(Supplier<Result> left, Supplier<Result> right);
    // (but now it might be impossible to flatten the stack)
    public interface ExprVisitor2<Result> {
      Result lit(double x);
      Result add(Result left, Result right);
      Result sub(Result left, Result right);
    }

    public abstract class Expr {
      private Expr() {}

      public abstract <Result> Result visit(ExprVisitor2<Result> visitor);

      public static Expr lit(final double x) {
        return new Expr() {
          public @Override <Result> Result visit(final ExprVisitor2<Result> visitor) {
            return visitor.lit(x);
          }
        }
      }

      public static Expr add(final Expr left, final Expr right) {
        return new Expr() {
          public @Override <Result> Result visit(final ExprVisitor2<Result> visitor) {
            return visitor.add(left.visit(visitor), right.visit(visitor));
          }
        }
      }

      public static Expr sub(final Expr left, final Expr right) {
        return new Expr() {
          public @Override <Result> Result visit(final ExprVisitor2<Result> visitor) {
            return visitor.sub(left.visit(visitor), right.visit(visitor));
          }
        }
      }
    }

In Java,

  interface Shape<T> {
    interface _Circle<T> {
      T apply(int x, int y, int r);
    }
    interface _Rectangle<T> {
      T apply(int x, int y, int w, int h);
    }
    T apply(_Circle<T> circle, _Rectangle<T> rectangle);

    static <T> Shape<T> Circle(int x, int y, int r) {
      return (circle, rectangle) -> circle.apply(x, y, r);
    }
    static <T> Shape<T> Rectangle(int x, int y, int w, int h) {
      return (circle, rectangle) -> rectangle.apply(x, y, w, h);
    }

    static double area(Shape<?> shape) {
      var s = (Shape<Double>) shape;
      return s.apply(
          (x, y, r) -> Math.PI * r * r,
          (x, y, w, h) -> 1. * w * h
      );
    }

    static void main(String[] args) {
      var exampleCircle = Circle(2, 1, 4);
      var exampleRectangle = Rectangle(1, 3, 10, 7);

      System.out.println(area(exampleCircle));
      System.out.println(area(exampleRectangle));
    }
  }

BTW, you can use the same encoding when you write a Promise in JS.

In addition to the other TypeScript examples, here's one that I would actually use. Now, it's not encoding the types not as positional, but named arguments via objects. Allows me to destructure them, for added clarity.

  type Circle = {x: number; y: number; r: number};
  type Rectangle = {x: number; y: number; w: number; h: number};
  
  type Shape = <T>(xs: {
      circle: (args: Circle) => T;
      rectangle: (args: Rectangle) => T;
  }) => T;
  
  function Circle(x: Circle): Shape {
      return ({circle}) => circle(x);
  }
  
  function Rectangle(x: Rectangle): Shape {
      return ({rectangle}) => rectangle(x);
  }
  
  const exampleCircle = Circle({x: 2, y: 1.4, r: 4.5});
  const exampleRectangle = Rectangle({x: 1.3, y: 3.1, w: 10.3, h: 7.7});
  
  const area = (shape: Shape): number =>
      shape({
          circle: ({r}: Circle) => Math.PI * r * r,
          rectangle: ({w, h}: Rectangle) => w * h,
      });
  
  console.log(area(exampleCircle));
  console.log(area(exampleRectangle));

/edit: Fixed formatting. /edit: Clarify something.

Here's the first example in C++:

    #include <concepts>
    #include <iostream>
    #include <numbers>
    
    template<class shape>
    concept Shape = requires(
        shape s,
        shape (&&circle)(double, double, double),
        shape (&&rectangle)(double, double, double, double)) {
        { s(circle, rectangle) } -> std::same_as<shape>; };
    
    auto Circle = [](double x, double y, double r) -> Shape auto {
        return [=](auto&& circle, auto&& rectangle) { return circle(x, y, r); }; };
    auto Rectangle = [](double x, double y, double w, double h) -> Shape auto {
        return [=](auto&& circle, auto&& rectangle) { return rectangle(x, y, w, h); }; };
    
    Shape auto exampleCircle = Circle(2.0, 1.4, 4.5);
    Shape auto exampleRectangle = Rectangle(1.3, 3.1, 10.3, 7.7);
    
    auto area = [](Shape auto shape) -> double { return shape(
        [](auto, auto, auto r) { return std::numbers::pi * r * r; },
        [](auto, auto, auto w, auto h) { return w * h; }); };
    
    int main() {
        std::cout << area(exampleCircle) << std::endl;
        std::cout << area(exampleRectangle) << std::endl;
    }

Of course, this is missing type-erasure, which you'd need to pass `Shape` across TU boundaries, but that's unnecessary if you're happy to use parametric polymorphism.

We can think of "data" as simply deferring a choice/branch. For example consider this code:

    boolean function1(...) {
      FOO
      return true;
    }

    void function2(...) {
      BAR
      if (function1(...)) {
        BAZ
      } else {
        QUUX
      }
    }

The boolean lets us separate how to make a decision (which we define in function1), from how to handle a decision (which we define in function2). We can always eliminate this data by bringing those two things together, e.g.

    // Inline function1 into function2
    void function3(...) {
      FOO
      BAR
      if (true) {
        BAZ
      } else {
        QUUX
      }
    }

    // Simplify the if/then/else
    void function4(...) {
      FOO
      BAR
      BAZ
    }

Of course, it's very useful to keep things separate and to pass data around (modularity, readability, etc.). My point is that the computer/language doesn't care about these things, so we can use refactorings like this to 'distill the essence' of what data 'really is' (from this one perspective, at least).

So what can we do with a boolean?

- We can discard it. Such code can always be refactored to eliminate the boolean (it's dead code).

- Pass it to some other code. We can always refactor this to remove such intermediate steps, e.g. above we inlined 'function1' to avoid passing the boolean around.

- Construct them. We do this by using the "constructors" 'true' or 'false', AKA the "introduction forms".

- Branch on them using if/then/else. This is also called "destructing", where if/then/else is a "destructor" or "elimination form".

- Simplify 'if(true) ...' and 'if(false) ...'. Here we are 'destructing a constructor', which can always be replaced by the relevant branch.

If we apply these refactorings over and over we can eventually simplify-away every boolean value in a program. There are a couple of things to keep in mind:

- Some languages have special-case boolean operations like '!foo'. Those are equivalent to functions containing branches, which can be refactored as above, e.g.

    boolean not(boolean x) {
      if (x) {
        return false;
      } else {
        return true;
      }
    }

    boolean and(boolean x, boolean y) {
      if (x) {
        return y;
      } else {
        return false;
      }
    }

    boolean or(boolean x, boolean y) {
      if (x) {
        return true;
      } else {
        return y;
      }
    }

 - To fully eliminate data, we need to include any 'external' code, e.g. 'inlining' external libraries, system calls, third-party APIs, etc. For simplicity I'll just assume we're using a single program in a single language, but the principle still holds in general.

Note that inlining intermediate steps and removing unused parameters have nothing to do with booleans themselves; they apply to all forms of data. Hence the 'essence' of booleans is the simplification of 'if(true)...' and if(false)...'.

We can do this with booleans since they are a "sum type", i.e. there are a few distinct forms of boolean (namely "true" and "false"). This is similar to the article's "Shape" type, which has a "Circle" form and a "Rectangle" form.

OOP languages don't tend to support sum types directly; instead we can 'fake it' using subtypes. Here's an example, where I've implemented the simplification behaviour using subtype polymorphism:

    abstract class Boolean {
      T ifThenElse(T t, T e);
    }

    class True extends Boolean {
      T ifThenElse(T t, T e) {
        return t;
      }
    }

    class False extends Boolean {
      T ifThenElse(T t, T e) {
        return e;
      }
    }

There's a slight wrinkle here, since calling 'ifThenElse(foo, bar)' will execute both 'foo' and 'bar'; we'll just get one of them returned back to us. If this is a problem, we can wrap our branches in zero-argument functions, pass those to 'ifThenElse', and call whichever function gets returned. Note that this is actually how Smalltalk implements boolean branching! https://rosettacode.org/wiki/Conditional_structures#Smalltal...

Hopefully I've demonstrated that the three classed defined above are a complete implementation of booleans: we have the constructors ('new True()' and 'new False()'), the destructor 'ifThenElse(thenBranch, elseBranch)', and we don't need anything else. To drive this point home, here's how we can define boolean algebra, translated from the above:

    // not(x)
    x.ifThenElse(new False(), new True())

    // and(x, y)
    x.ifThenElse(y, new False())

    // or(x, y)
    x.ifThenElse(new True(), y)

This implementation of Boolean is a rather simple form of "visitor pattern": the implementation of the "ifThenElse algorithm" is spread out amongst different implementations of the method, where each subclass knows how to handle its own case, and we just dispatch on whatever Boolean object we happen to have.

The point of Church Encoding is that we don't actually need these classes and polymorphism at all: rather than wrapping up these methods into classes, defining a class hierarchy, constructing instances of these subclasses, invoking methods on those instances, dynamically dispatching on the vtables, etc.; we can just pass the functions around directly!

Switching to JS, since it has first-class functions, here's my first example again:

    const  trueIfThenElse = (t, e) => t;
    const falseIfThenElse = (t, e) => e;

    function1(...) {
      FOO
      return trueIfThenElse;
    }

    function2(...) {
       BAR
       function1(...)(BAZ, QUUX)
    }

If we want to avoid executing both BAZ and QUUX, we could wrap them up in functions like 'function1(...)(() => BAZ, () => QUUX)()'. We could also rename these functions to simply 'true' and 'false', since they're completely equivalent to those values (although that would be a syntax error in JS).

So now we've seen that (a) booleans can be completely implemented using if/then/else (b) the behaviour of if/then/else can be implemented using subclass polymorphism (c) subclass polymorphism can be emulated by passing around first-class functions. Note that we could have skipped all the OOP stuff and gone straight to functions, but I thought it might help some people, and it's also interesting in its own right.

This also extends to sum types with any number of distinct forms (which we now know are "constructors"). The rule is simple: a type with N constructors can be represented as a function which takes N arguments, and returns one of them. For example, we could represent Colour, with Red/Green/Blue like this:

    const red   = (r, g, b) => r;
    const green = (r, g, b) => g;
    const blue  = (r, g, b) => b;

    function printColour(c) {
      console.log(c("Received red", "Given green", "Bestowed with blue"));
    }

There are two other sorts of data to consider:

"Product types" contain multiple sub-values, e.g. 'Coordinate(x, y, z)'. For these, the rule is that we call the corresponding argument as a function, passing it the sub-values as arguments. For example:

    const mkCoord = (x, y, z) => f => f(x, y, z);

    function showCoord(c) {
      c((x, y, z) => console.log(
        "x: " + x.toString + " y:" + y.toString + " z: " + z.toString
      ));
    }

    const origin = mkCoord(0, 0, 0);
    showCoord(origin);

Note that I'm using raw JS numbers and strings for simplicity; we can implement these using Church Encoding (e.g. using 64 booleans to emulate a double-precision float), but it would be tedious for this example.

We can combine sums and products, i.e. each constructor can contain sub-values. This is what the "Shape" example from the article does. We just need to combine the two rules: take N arguments (once for each constructor), and call the appropriate argument with the sub-values. For example:

    const circle = (x, y, r) => (ifCirc, ifRect) => ifCirc(x, y, z)

    const rectangle = (x, y, w, h) => (ifCirc, ifRect) => ifRect(x, y, w, h)

    const unitCircle = circle(0, 0, 1);

    const unitSquare = rectangle(0, 0, 1, 1);

    function drawShape(s) {
      s(
        (x, y, r)    => console.log("Circle of radius " + r.toString),
        (x, y, w, h) => console.log("Rect of area " (w * h).toString)
      );
    }

The final possibility is recursive data, where the sub-values can be of the same type we're defining. The article uses a binary tree as an example, but a list is easier. In OOP:

    abstract class List<T> {
      U reduce(U init, Function<U, Pair<U, T>> f);
    }

    class Nil<T> extends List<T> {
      U reduce(U init, Function<U, Pair<U, T>> f) {
        return init;
      }
    }

    class Cons<T> extends List<T> {
      private      T  head;
      private List<T> tail;

      public Cons(T head, List<T> tail) {
        this.head = head;
        this.tail = tail;
      }

      U reduce(U init, Function<U, Pair<U, T>> f) {
        return this.tail.reduce(
          f(new Pair<U, T>(init, this.head)),
          f
        );
      }
    }

With first-class functions (this might be slightly off; it's been a while!):

    const nil  = (ifNil, ifCons) => ifNil

    const cons = (head, tail) => (ifNil, ifCons) => ifCons(
      head,
      tail(ifNil, ifCons)
    );

    const oneTwoThree = cons(1, cons(2, cons(3, nil)));

    const plus = (x, y) => x + y;

    function sum(lst) {
      return lst(0, plus);
    }

    console.log(sum(oneTwoThree).toString);

So the trick to recursive data is that whenever we need to pass a sub-value to one of our N given functions, if that sub-value is of our recursive type (like the 'tail' of a list is another list) then we first call that sub-value with the same N functions we've been given. That way, the structure 'reduces' down to a single result.

Took me like ten minutes to really grok the essence of the second haskell example and now I'm wondering why anybody would ever do that.

Perhaps I haven't had enough caffeine yet, but this sounds exactly like what we get in the latest versions of C# w/ its pattern matching feature:

https://docs.microsoft.com/en-us/dotnet/csharp/pattern-match...

The code you've selected is not "for circles", per se. This is classic double-dispatch -- the function itself represents a circle (via the `x, y, r` values it closes over), and it chooses which receiver to invoke based on its identity. (The parameters in the selected function may be better named `onCircle` and `onRectangle`.)

If you just have a Shape, and you need to do something specific depending on the kind of Shape you have, you need some way to tell what kind of Shape you have. You can use `instanceof` and casting, but there's no guarantee that you've handled all cases(^). Moreover, it's painful in some languages (like Java) to extract the subclass-specific fields, as you need to rebind the value to a new variable of the right type first.

The Visitor pattern is a classic object-oriented solution to this problem, typically using double dispatch. The Shape itself knows what kind of shape it is, so rather than asking it what type it is, you provide it a set of _strategies_ (no relation to the Strategy pattern), one for each type of Shape. The Shape doesn't know what you want to do with it, so it calls you right back, invoking the circle- or rectangle-specific logic depending on what kind of shape it is. (Hence, double-dispatch.)

Gabriel (OP) observes that the Visitor pattern is exactly the Boehm-Berarducci encoding of a sum type. The Visitor pattern is very common in OO programming (see, for instance, abstract syntax trees), so the fact that we're so often using an encoding of a more direct concept is worth remarking on. I know I'd much rather use sum types in general than use the Visitor pattern.

(^) As an aside, I've never found "Shape" to be a very convincing example of sum types, as it's much easier to imagine as an open family than as a closed family. In an open family of shapes, there is no "all cases", and instanceof/casting is inappropriate from the beginning. I think object algebras (see my other comment) give a more motivating class of examples of closed families, including ASTs.

Reading that just reminded me of why I hate OOP so much. It's confusing.

The purpose of the OP post is not to provide an introduction to the visitor pattern. It's to explain the relationship of the visitor pattern with something else.

Did you miss this part of the post?

> I’m not going to provide a standalone explanation of the visitor pattern since the linked Wikipedia page already does that.

> Obviously, not. Not even apples versus oranges.

Formally, `A + B` is isomorphic to `forall T. (A -> T, B -> T) -> T`, where the inner `(A -> T, B -> T)` is the type of a visitor.

    a + b
    -- CPS transform
    = forall t. ((a + b) -> t) -> t
    -- distribute -> over +
    = forall t. (a -> t, b -> t) -> t
    -- if you want to drop even the product, distribute -> over *
    -- but this loses you the ability to name a separable Visitor
    = forall t. (a -> t) -> (b -> t) -> t

    type Visitor a b t = (a -> t, b -> t)
    type Sum a b = forall t. Visitor a b t -> t

    iso :: Sum a b -> (a + b)
    iso s = s (Left, Right)
    
    osi :: (a + b) -> Sum a b
    osi (Left a) = \(onA, onB) -> onA a
    osi (Right b) = \(onA, onB) -> onB b

Oh, I forgot to mention, that "enzymes are proteins" is isomorphic (lol) to "procedures are list structures" (or "code is data") which explains the miracle of Lisp and it's macros and connects Lisp to life itself, and justifies why MIT folks ware so fascinated with it.

Thank you for the feedback. I was conscientious of that shadowing issue when writing it, but I just wasn't sure what to change on either side to differentiate them.