Author here: Go does not have support for discriminated unions.

The trick is not limited to functional programming languages but it is limited to languages that support generic programming / polymorphism

The visitor pattern is only helpful when you have two polymorphic types and want to write code which needs to dispatch on the real type of BOTH arguments.

For example, you have a an expression tree, where each node can have a different type that is a subtype of Expression; and you have an Evaluator type with many subtypes of evaluators.

At runtime, every specific subtype of Evaluator may need different code for every specific subtype of Expression. Furthermore, new Expression types and new Evaluator types can be created by libraries that you don't have access to. Discriminated unions don't solve this problem.

Discriminated unions exactly solve this problem (just "inside out" in the same way that Church encodings are algebraic datatypes "inside out"). It's only a matter of whether you have closed or open unions. That then just governs whether you have to nest types or not.

In fact, you can get even more code reuse than with your standard visitor pattern using openly recursive unions.

  // This is all pseudo code with open unions to reduce nesting.
  // Doable with closed unions, just more cluttered

  // Note these are all type aliases, since open unions imply structural types,
  // but nonetheless these are truly (open) discriminated unions

  // ------ BEGIN : In some external library
  type alias Evaluator = PrintEvaluator or ExecutionEvaluator

  // Open here is referring to open recursion rather than open unions
  // This gives us even more reuse than the standard visitor pattern
  type alias ExpressionOpen a = Literal Int or Addition a a

  stringEvaluator : ExpressionOpen String -> String
  stringEvaluator (Literal n) = intToString n
  stringEvaluator (Addition x y) = x ++ " + " ++ y

  executionEvaluator : ExpressionOpen Int -> Int
  executionEvaluator (Literal n) = n
  executionEvaluator (Addition x y) = x + y

  evaluate : Evaluator -> Fix ExpressionOpen -> String
  // This fold is a generalized version of the usual fold on list, meant to work on fixed point types
  evaluate PrintEvaluator expr = fold stringEvaluator expr
  evaluate ExecutionEvaluator expr = intToString (fold executionEvaluator expr)

  // ------ END : No longer in some external library

  // ------ BEGIN : My own code
  type alias ComplexEvaluator = HexadecimalEvaluator or Evaluator

  hexadecimalEvaluator : ExpressionOpen String -> String
  hexadecimalEvaluator (Literal n) = intToHexString n
  hexadecimalEvaluator (Addition x y) = x ++ " + " ++ y

  type alias ComplexExpressionOpen a = BasicExpressionOpen a or Multiplication a a

  extendedEvaluator : ComplexEvaluator -> Fix ExpressionOpen -> String
  // This may look like dynamic dispatch but it isn't
  // ": Evaluator" expands out to a case match on the union tags of Evaluator
  // In both branches of the match we then just call evaluate
  extendedEvaluator (evaluator : Evaluator) expr = evaluate evaluator expr
  extendedEvaluator HexadecimalEvaluator expr = fold hexadecimalEvaluator expr

  stringEvaluatorExtended : ComplexExpressionOpen String -> String
  stringEvaluatorExtended (expr : ExpressionOpen String) = stringEvaluator expr
  stringEvaluatorExtended (Multiplication x y) = x ++ " * " ++ y

  executionEvaluatorExtended : ComplexExpressionOpen Int -> Int
  executionEvaluatorExtended (expr : ExpressionOpen Int) = executionEvaluator expr
  executionEvaluatorExtended (Multiplication x y) = x * y

  hexadecimalEvaluatorExtended : ComplexExpressionOpen String -> String
  hexadecimalEvaluatorExtended (expr : ExpressionOpen String) = hexadecimalEvaluator expr
  hexadecimalEvaluatorExtended (Multiply x y) = x ++ " * " ++ y

  // If you want to extend both evaluator and expression at the same time you need
  // to repeat yourself a little
  // But you would need to repeat even more with the visitor pattern!
  // Namely none of your old evaluators work nor do any of your old expression trees!
  evaluateExtendedExpression : ComplexEvaluator -> Fix ComplexExpressionOpen -> String
  evaluateExtendedExpression PrintEvaluator expr = fold stringEvaluatorExtended expr
  evaluateExtendedExpression ExecutionEvaluator expr = fold executionEvaluatorExtended expr
  evaluateExtendedExpression HexadecimalEvaluator expr = fold hexadecimalEvaluatorExtended expr

  // ------ END : Finished with my own code

That doesn't look like an alternative to the visitor pattern, that basically IS the visitor pattern. If you replaced the magic of Fix T + fold with an equivalent to accept(), you would end up having written exactly the Visitor pattern just with pattern matching instead of virtual dispatch and sum types instead of subtypes.

Here is the exact same example in fully working C# (you can do the same in Java or C++, C# is just a little more terse; you could do it in Go as well, but it would be much uglier because you don't have generics).

  // ------ BEGIN : In some external library
  interface ExpressionOpen { T accept<T>(Evaluator<T> eval) => throw new NotImplementedException("Unsupported combination"); }
  record Literal(int n) : ExpressionOpen{
    public T accept<T>(Evaluator<T> eval) => eval.visitLiteral(this);
  }
  record Addition(ExpressionOpen x, ExpressionOpen y) : ExpressionOpen {
    public T accept<T>(Evaluator<T> eval) => eval.visitAddition(this);
  }

  interface Evaluator<T> {
    T visitLiteral(Literal l);
    T visitAddition(Addition a);
  }
  class StringEvaluator : Evaluator<string> {
    public virtual string visitLiteral(Literal l) => l.n.ToString();
    public string visitAddition(Addition a) => a.x.accept(this) + "+" + a.y.accept(this);
  }
  class ExecutionEvaluator : Evaluator<int> {
    public int visitLiteral(Literal l) => l.n;
    public int visitAddition(Addition a) => a.x.accept(this) + a.y.accept(this);
  }
  // ------ END : No longer in some external library

  // ------ BEGIN : My own code

  //note: no need for ComplexEvaluator here
  class HexadecimalEvaluator : StringEvaluator {
    public override string visitLiteral(Literal x) => x.n.ToString("x");

    // thanks to inheritance, the existing expressions can already accept this
    // so no need for an equivalent for extendedEvaluator;
    // we're also inheriting visit(Addition) but that is not fundamental
  }

  interface ComplexExpressionOpen : ExpressionOpen { T accept<T>(ComplexEvaluator<T> eval) => throw new NotImplementedException("Unsupported combination"); }
  record Multiplication(ExpressionOpen x, ExpressionOpen y) : ComplexExpressionOpen {
    public T accept<T> (ComplexEvaluator<T> eval) => eval.visitMultiplication(this);
  }

  //but we do need ComplexEvaluator to go with ComplexExpression
  interface ComplexEvaluator<T> : Evaluator<T> { T visitMultiplication(Multiplication x); }

  class StringEvaluatorExtended : StringEvaluator, ComplexEvaluator<string> {
    public string visitMultiplication(Multiplication m) => m.x.accept(this) + " * " + m.y.accept(this);
  }

  class ExecutionEvaluatorExtended : ExecutionEvaluator, ComplexEvaluator<int> {
    public int visitMultiplication(Multiplication m) => m.x.accept(this) * m.y.accept(this);
  }

  class HexadecimalEvaluatorExtended: HexadecimalEvaluator, ComplexEvaluator<string> {
    public string visitMultiplication(Multiplication m) => m.x.accept(this) + " * " + m.y.accept(this);
  }
  class HexadecimalEvaluatorExtended: HexadecimalEvaluator, ComplexEvaluator<string> {
    public string visit(Multiplication m) => m.x.accept(this) + " * " + m.y.accept(this);
    //if C# supported multiple inheritance, we wouldn't have needed to repeat ourselves here:
    //we could have just inherited both HexadecimalEvaluator and StringEvaluatorExtended
  }

  //we don't need any kind of boilerplate similar to evaluateExtendedExpression.

  // ------ END : Finished with my own code

You'll notice that (disregarding how verbose the language still is) we have actually written significantly less code - we haven't repeated a single line of code.

Also note that your example only works in languages which have discriminated unions, pattern matching, compiler macros, and support for recursive types. Without any of these, it becomes even more verbose and harder to extend than the actual visitor pattern.

  interface ExpressionOpen { T accept<T>(Evaluator<T> eval) => throw new NotImplementedException("Unsupported combination"); }

  interface ComplexExpressionOpen : ExpressionOpen { T accept<T>(ComplexEvaluator<T> eval) => throw new NotImplementedException("Unsupported combination"); }

Those don't really count though. Heck if you allow that I can write the code way shorter in true Haskell (not pseudo-Haskell) as well.

In particular

  //we don't need any kind of boilerplate similar to evaluateExtendedExpression.

That was purely for combinatorial safety. You could remove it altogether if you wanted.

The whole point of the visitor pattern is to prevent you from being able to put unsupported combinations together. If you get rid of that requirement you don't need types at all and there are far far easier ways of doing this than either with the visitor pattern or with discriminated unions (just do it all with nested dictionaries for a fraction of the code).

Throwing this exception is basically a cheat is it not?

> support for recursive types

I think every statically typed language I know has support for recursive types. Certainly C# does.

> pattern matching

Eh... I'm not really using pattern matching in any real sense here. They could be replaced by if statements. The only reason it's there is because there's total type erasure in Haskell so runtime dynamic dispatch isn't really a thing in the same way it is in C#.

> Those don't really count though. Heck if you allow that I can write the code way shorter in true Haskell (not pseudo-Haskell) as well.

We could get rid of those base cases; we would then have to make ComplexExpression not a subtype of ExpressionOpen, and that in turn would mean we can't extend any of the extended evaluators from the old evaluators. This would just add the same boilerplate you have (copying the StringEvaluator implementation in StringEvaluatorExtended etc), all to prevent multiply.accept(printEvaluator). I'm not sure this extra bit of type safety would be worth it, but it certainly depends on the specifics.

> The whole point of the visitor pattern is to prevent you from being able to put unsupported combinations together.

While that is an important part, this is not an all-or-nothing problem. Type safety is a spectrum, and we can choose where to give up some safety to gain something else.

> Type safety is a spectrum, and we can choose where to give up some safety to gain something else.

I agree, but I'm saying that if you're willing to give up the type safety of verified combinations, you can have a solution that is just as (or even more) extensible as the visitor pattern (or discriminated unions) that is fewer lines of code and might even perform faster. Namely you can just downcast in the evaluator to the cases you can handle and then just bail if the downcast fails. This is the exact same functionality, can be extended in the same way (and in fact in more ways), and is fewer lines of code.

As far as I can tell the only reason you'd want to use the visitor pattern (or discriminated unions) here is some notion of "purity," e.g. in the case of OO that you're violating some notion of the Liskov Substitution principle by explicitly downcasting and in the case of FP that you're violating parametric polymorphism. But neither notions of purity feel particularly convincing to me.

As an aside

> This would just add the same boilerplate you have

In fact I think in the C# version it would be even more code because you can't reuse the same match patterns; you'd have to repeat way more of each evaluator.

> As far as I can tell the only reason you'd want to use the visitor pattern (or discriminated unions) here is some notion of "purity," e.g. in the case of OO that you're violating some notion of the Liskov Substitution principle by explicitly downcasting and in the case of FP that you're violating parametric polymorphism. But neither notions of purity feel particularly convincing to me.

In an OO language, the reason you'd prefer the Visitor pattern to downcasting is that it allows extending behavior by simply declaring new subtypes, instead of having to edit the central evaluator. This is why I keep insisting that the Visitor pattern is about double virtual dispatch, not about discriminated unions.

> In fact I think in the C# version it would be even more code because you can't reuse the same match patterns; you'd have to repeat way more of each evaluator.

Here is the C# version without the default NotImplementedException escape hatch:

  // ------ BEGIN : In some external library
  interface ExpressionOpen { T accept<T>(Evaluator<T> eval); }
  record Literal(int n) : ExpressionOpen{
    public T accept<T>(Evaluator<T> eval) => eval.visitLiteral(this);
  }
  record Addition(ExpressionOpen x, ExpressionOpen y) : ExpressionOpen {
    public T accept<T>(Evaluator<T> eval) => eval.visitAddition(this);
  }

  interface Evaluator<T> {
    T visitLiteral(Literal l);
    T visitAddition(Addition a);
  }
  class StringEvaluator : Evaluator<string> {
    public virtual string visitLiteral(Literal l) => l.n.ToString();
    public string visitAddition(Addition a) => a.x.accept(this) + "+" + a.y.accept(this);
  }
  class ExecutionEvaluator : Evaluator<int> {
    public int visitLiteral(Literal l) => l.n;
    public int visitAddition(Addition a) => a.x.accept(this) + a.y.accept(this);
  }
  // ------ END : No longer in some external library

  // ------ BEGIN : My own code

  //note: no need for ComplexEvaluator here
  class HexadecimalEvaluator : StringEvaluator {
    public override string visitLiteral(Literal x) => x.n.ToString("x");

    // thanks to inheritance, the existing expressions can already accept this
    // so no need for an equivalent for extendedEvaluator;
    // we're also inheriting visit(Addition) but that is not fundamental
  }

  interface ComplexExpressionOpen { T accept<T>(ComplexEvaluator<T> eval); }
  record Multiplication(ExpressionOpen x, ExpressionOpen y) : ComplexExpressionOpen {
    public T accept<T> (ComplexEvaluator<T> eval) => eval.visitMultiplication(this);
  }

  //but we do need ComplexEvaluator to go with ComplexExpression
  interface ComplexEvaluator<T> : Evaluator<T> { T visitMultiplication(Multiplication x); }

  class StringEvaluatorExtended : ComplexEvaluator<string> {
    public virtual string visitLiteral(Literal l) => l.n.ToString();
    public string visitAddition(Addition a) => a.x.accept(this) + "+" + a.y.accept(this);
    public string visitMultiplication(Multiplication m) => m.x.accept(this) + " * " + m.y.accept(this);
  }

  class ExecutionEvaluatorExtended : ComplexEvaluator<int> {
    public int visitLiteral(Literal l) => l.n;
    public int visitAddition(Addition a) => a.x.accept(this) + a.y.accept(this);
    public int visitMultiplication(Multiplication m) => m.x.accept(this) * m.y.accept(this);
  }

  class HexadecimalEvaluatorExtended: StringEvaluatorExtended  {
    public string visit(Multiplication m) => m.x.accept(this) + " * " + m.y.accept(this);
    public override string visitLiteral(Literal x) => x.n.ToString("x");
  }

  //we don't need any kind of boilerplate similar to evaluateExtendedExpression.

  // ------ END : Finished with my own code

However, this version has a major problem that neither your version nor my initial one do: I can't represent something like Addition(Multiplication(1,2),3). I don't think this problem is fixable in .NET, since you can't construct generic types that depend on runtime values, such as an ExpressionOpen<V> where V is anything which implements Evaluator<T>. We could probably hack around it with a lot more boilerplate and some convention (an associated Evaluator interface that Evaluator<T> extends, and explicit casts from Evaluator to Evaluator<T> in the accept methods, plus a convention that no one should implement Evaluator except Evaluator<T>).

> // thanks to inheritance...

Ah ha! You're totally right. I totally forgot about using inheritance to deal with overlapping patterns even though I use it all the time in Java (you could do the same overlap with open unions, but there's other ergonomic reasons you don't want to do that if you have exhaustiveness checking.)

> In an OO language, the reason you'd prefer the Visitor pattern to downcasting is that it allows extending behavior by simply declaring new subtypes, instead of having to edit the central evaluator. This is why I keep insisting that the Visitor pattern is about double virtual dispatch, not about discriminated unions.

I don't think that's true. If you give up statically checked combinations I don't think you need double dispatch at all.

Here's a version that does everything with downcasting (and the accompanying error). One class has disappeared altogether because we don't need them anymore (ComplexExpression) and we don't need any classes for the evaluators (other than a container to hold them as a sort of utility class with a bunch of static methods). And we don't have visitors at all.

And it represents Addition(Multiplication(1, 2), 3) just fine.

Am I missing something here?

  // ------ BEGIN : In some external library
  
  interface Expression { // This could be empty
  }
  record Literal(int n) : Expression {}
  record Addition(Expression x, Expression y) : Expression {}

  // Your evaluator doesn't even need to be a true class anymore and can just be
  // a bag of static methods
  // You could if you wanted to, but there's isn't a lot of value
  class BuiltInEvaluators {
    public static string StringEvaluator(Expression expression) {
      switch(expression) {
        case Literal literal: return literal.n.ToString();
        case Addition addition: return $"{StringEvaluator(addition.x)} + {StringEvaluator(addition.y)}";
        // You could remove this boilerplate if you wanted by wrapping this in a true class
        // and then throwing the exception in a wrapper method
        default: throw new ArgumentException("Expression incompatible with evaluator!");
      }
    }
    public static int ExecutionEvaluator(Expression expression) {
      switch(expression) {
        case Literal literal: return literal.n;
        case Addition addition: return ExecutionEvaluator(addition.x) + ExecutionEvaluator(addition.y);
        default: throw new ArgumentException("Expression incompatible with evaluator!");
      }
    }
  }
  // ------- END : No longer in some external library

  // ------- BEGIN : My own code
  record Multiply(Expression x, Expression y) : Expression {}

  class MyOwnEvaluators {
    public static string ExtendedStringEvaluator(Expression expression) {
      switch(expression) {
        case Multiply multiply: return $"{ExtendedStringEvaluator(multiply.x)} * {ExtendedStringEvaluator(multiply.y)}";
        case Expression x: return BuiltInEvaluators.StringEvaluator(x);
        default: throw new ArgumentException("Expression incompatible with evaluator!");
      }
    }
    public static int ExtendedExecutionEvaluator(Expression expression) {
      switch(expression) {
        case Multiply multiply: return ExtendedExecutionEvaluator(multiply.x) * BuiltInEvaluators.ExecutionEvaluator(multiply.y);
        case Expression x: return BuiltInEvaluators.ExecutionEvaluator(x);
        default: throw new ArgumentException("Expression incompatible with evaluator!");
      }
    }
    public static string HexadecimalEvaluator(Expression expression) {
      switch(expression) {
        // Our only interesting case
        case Literal l: return l.n.ToString("x");
        case Expression x: return ExtendedStringEvaluator(x);
        default: throw new ArgumentException("Expression incompatible with evaluator!");
      }
    }
  }
  // ------- END : My own code

Well, one thing that this solution misses is virtual dispatch - HexadecimalEvaluator won't work for Addition(Literal(1),Literal(2)) for example, because ExtendedStringEvaluator doesn't know to call HexadecimalEvaluator back.

Still, this is easily fixable by transforming the static functions into virtual methods on a class:

  //keeping all of the definitions so far the same

  class ExtendedStringEvaluator : BuiltInEvaluators.StringEvaluator {
    public override string visit(Expression expression) {
      
      switch(expression) {
        case Multiply multiply: return $"{ExtendedStringEvaluator(multiply.x)} * {ExtendedStringEvaluator(multiply.y)}";
        default : return super(expression);
      }
    }
  }

  class HexadecimalEvaluator : ExtendedStringEvaluator {    
    public override string visit(Expression expression) {
  
      switch(expression) {
        case Literal literal: return return l.n.ToString("x");
        default : return super(expression);
      }
    }
  }

Still, this switch on the class type is essentially exactly a virtual call on the type of Expression, just controlled by someone other than the original class. That is, the Expression doesn't "know" any more that it is being visited, so you couldn't create a LoggingExpression let's say. On the other hand, the Visitor now has more control over the way it interprets expression subtypes. So even here we are doing double dispatch: we are dispatching manually based on the runtime type of `expression`, and then allowing the language to dispatch based on the runtime type of `this`.

> Well, one thing that this solution misses is virtual dispatch - HexadecimalEvaluator won't work for Addition(Literal(1),Literal(2)) for example, because ExtendedStringEvaluator doesn't know to call HexadecimalEvaluator back.

Ah of course, I accidentally switched back into closed recursion rather than open recursion (that was ExpressionOpen). This indeed is exactly analogous to early binding vs late binding. You can't exactly write the same form of open recursion I wrote earlier because C# doesn't have higher-kinded generics (so for example you can't write

  interface Mappable<L> { 
    public abstract L<B>Map<A>(Func<A, B> f, L<A> x) 
  }

which prevents you from writing

  record Fix<F>(F<Fix<F>> x)

), but that's a language-specific thing. If you had higher-kinded generics you could exactly model virtual dispatch with open recursion because they're the same thing.

> That is, the Expression doesn't "know" any more that it is being visited, so you couldn't create a LoggingExpression let's say. On the other hand, the Visitor now has more control over the way it interprets expression subtypes. So even here we are doing double dispatch: we are dispatching manually based on the runtime type of `expression`, and then allowing the language to dispatch based on the runtime type of `this`.

You can call it visitor, but at this point it really is the same as discriminated unions (indeed this is exactly analogous to the first iteration of code just without the last bit to ensure that combinations matched up). And you can exactly replicate `LoggingExpression` in the evaluator, there is no difference in expressivity.

This shouldn't be surprising; after all the whole thing that kicked off all of this is that there is an isomorphism between discriminated unions and the visitor pattern. It should not be a surprise that it is possible to interpret one in the other.

My point at the beginning of all this was to object to the statement that this was not an isomorphism. Anything you can do with the visitor pattern you can do with discriminated unions and vice versa. The only differences are in ancillary language support (e.g. virtual dispatch and higher-kinded generics). Hence in a very real real sense the visitor pattern is just discriminated unions and vice versa.

The only preference for one or the two comes down to issues of code size and maintenance.

Forgot one other important distinction: if we wanted to add a new expression subtype that can behave like one of the existing types for existing operations, that is not possible with the discriminated union variant. Say we wanted to add an SmallAddition, that stores its two numbers as bytes, but converts them to int when needed. We could add this without modifying any code in the visitors in the C# version (well, technically we may have a problem because we accessed the fields directly, but that's inconsequential). In the pseudo-Haskell version, we would need to modify all 6 evaluation functions just to handle the new Expression subtype.

> In the pseudo-Haskell version, we would need to modify all 6 evaluation functions just to handle the new Expression subtype.

That's not true. I think you may be misunderstanding open unions (or polymorphic variants) here. Tags are types in and of themselves. That's why these are all `type alias`es. You could decide to modify the type alias if you'd like, but you don't have to. You can add the additional tag just to the call site.

So how would a subtype of Addition look here? Who would tell stringEvaluator how to handle this SmallNumberAddition?

There wouldn't be a subtype of Addition because Haskell doesn't have a notion of subtyping in the same way C# does. It would depend on the particulars of what the difference between SmallNumberAddition and Addition look like (in particular which parts are kept with the same functionality and which are different). The answer could be either a simple function or a typeclass depending on that.

Right. I don’t have well-developed enough Haskell taste to tell whether this approach leads towards a more elegant or alternatively beneficial way of representing this kind of scenario than matching over a discriminated union type.

My takeaway from the article is that you almost always want a proper sum (discriminated union) type, but if you find yourself in a world without (hello, Java), here's a way to encode them precisely. As the OP notes, though, this still relies on having generics in your language, so you can't even perform this encoding if you don't have generics.

For a counterpoint, take a look at the relationship between object algebras and final tagless style [0]. It goes well beyond the basic visitor pattern, but gives you a lot of expressivity in exchange.

[0] https://oleksandrmanzyuk.wordpress.com/2014/06/18/from-objec...

This is exactly right. The relevant quote from the article is this:

> The reason we care about Church-encoding is because not all programming languages natively support sum types or recursion (although most programming languages support product types in the form of records / structs).

> However, most programming languages do support functions, so if we have functions then we can use them as a “backdoor” to introduce support for sum types or recursion into our language. This is the essence of the visitor pattern: using functions to Church-encode sum types or recursion into a language that does not natively support sum types or recursion.

That's contrived. If you're in Java, you would use a visitor pattern.

It is weird to given an example in Haskell of something you don't need to do in Haskell, but would theoretically want to do in some other language, but actually in these other languages you'd do something different.

I'm not sure I follow your point, because the thing you don't need to do in Haskell is precisely the visitor pattern, and you don't need to do it in Haskell because you have sum types; but you don't have sum types in Java, so of course you'd use the visitor pattern -- you have no other option.

I meant that you wouldn't use a Church encoding workaround for a visitor pattern. (That's what you seemed to mean by "here's a way to encode them precisely.") Instead, you'd use the visitor pattern in the normal way. So the Church encoding workaround is useful in neither Haskell nor Java.

The point of the original article is that the Visitor pattern is the Church encoding of sum types. It sounds like you see a stronger difference between what the article describes and what I understand the Visitor pattern to be. There might be light differences in how you organize various elements (such as grouping all the handlers into a single interface or taking them as individual parameters), but I see those as all within the same overall Visitor aegis.

The core of the Visitor pattern is a CPS transform, where you provide the value the code to run "next". Because this puts the sum type on the input side instead of the output side, you can distribute the types and get a pair of functions instead of a sum of values. Is there another difference I'm not accounting for?

I’ve seen the visitor pattern used mostly in compilers where there might be 50 cases in the AST for a compiler for a production language. So when looking at how the code is written for a visitor pattern, I think about how the code might look in a compiler if you had a lot of cases. Does it scale? The amount of boilerplate you need matters because it’s multiplied by 50.

The examples I’ve seen of Church encoding don’t look like code I’d want to read or write. Who wants to write a function that takes 50 functions as parameters? At least use a struct of functions. The struct serves as a vtable, so you might as well use an object-oriented language’s built-in vtables.

(Although I suppose in C, you’d need to implement the vtable yourself. Structs of functions are how OOP is commonly done in C.)

I understand how mathematically they’re equivalent but that’s ignoring practical differences in how they appear on the screen. It was neat when in Structure and Interpretation of Computer Programming they showed how you could implement data structures using only functions but that doesn’t make it a design pattern you want to use, it’s just trivia.

> Who wants to write a function that takes 50 functions as parameters? At least use a struct of functions. The struct serves as a vtable, so you might as well use an object-oriented language’s built-in vtables.

Okay, I think I see where we're missing each other. Church encoding doesn't have to be an all-or-nothing -- you don't have to commit to only function types and no other types. It's still useful when you apply it in localized contexts.

The key idea with the visitor pattern is that `A + B` is not a type you have in most languages. You can get an equivalent with generics and functions, but that doesn't mean you can't use products if it makes sense. The equivalent is an object with a method `<T> T visit(Visitor<T> v)`, where `Visitor<T>` is a pair of two methods, `T onA(A a)` and `T onB(B b)`.

Sure, you can always replace `(X, Y) -> Z` with `X -> Y -> Z` to get rid of even the product type, but that's not what anyone is proposing fundamentally here. It's just currying; it's not essential to the encoding being discussed.

The original blog post is using Haskell norms, and in Haskell, currying is very normal. But that doesn't mean it's a necessary ingredient of the demonstration. The key idea is to use a continuation-passing transform, to move the `A + B` value into the negative position of a function type (`forall T. (A + B -> T) -> T`), and then distribute over the function type so you're not relying on having a primitive sum type at all (`forall T. (A -> T, B -> T) -> T`). The extra step of currying (`forall T. (A -> T) -> (B -> T) -> T`) is unnecessary; it's just common in Haskell.

As you say:

> Who wants to write a function that takes 50 functions as parameters? At least use a struct of functions.

That's what `(A -> T, B -> T)` is. I suppose it could be confused for an argument list, but in Haskell, functions only take one argument. The type `(A -> T, B -> T)` is literally the type of a pair of two functions. It's isomorphic to a record type like `data Handlers { onA :: A -> T, onB :: B -> T }` -- you're just changing the indices from 0,1 to onA,onB.

If you ignore the details of implementation by treating isomorphic code refactorings as equivalent, it all looks kind of the same and there is no new technique here? In Java you would notice that a struct of functions can be replaced with methods and inheritance, and we’re back to the visitor pattern.

I guess maybe it’s that you could implement the visitor pattern in Haskell using a record that contains functions. But that’s a straightforward vtable implementation, and you wouldn’t really want to anyway.

> I guess maybe it’s that you could implement the visitor pattern in Haskell using a record that contains functions. But that’s a straightforward vtable implementation, and you wouldn’t really want to anyway.

On the contrary: typeclasses are exactly "records that contain functions", and Haskell desugars typeclass constraints to vtable-passing (if it can't otherwise inline the typeclass for known call sites). Pushing in this direction leads to the final tagless representation, which compares favorably with object algebras, a mild generalization of the idea of the Visitor pattern. [1]

I maintain that the core idea here is the replacement of `A + B -> T` with `(A -> T, B -> T)` to erase the sum type, and the use of the CPS transform from `A + B` to `forall T. ((A + B) -> T) -> T` to get the sum into a negative position in the first place. How you actually organize the resulting handler functions is a far smaller distinction. Even the Gang of Four is clear that their patterns are islands within a broader spectrum, and that each pattern has related variants based on the same idea. Currying (`(A, B) -> C` vs. `A -> B -> C`) is a separate and orthogonal idea from CPS, and I just don't see the value in including a choice of currying style in the Visitor pattern when it's an inessential flavoring.

> it all looks kind of the same and there is no new technique here?

Yes, that really is the point. The OP is explaining how these two different things in two different paradigms are actually the same thing, under the hood, and illustrates exactly how that's the case. It illuminates precisely where the Visitor pattern is useful: anywhere you'd use a sum type. Because both model closed families of options.

[1] https://oleksandrmanzyuk.wordpress.com/2014/06/18/from-objec...

I find it fascinating that while we mostly understand each other, it seems like we still disagree on what sort of knowledge is useful. There is a weird gap here.

It seems like this is starting with something I basically knew? The visitor pattern in an object-oriented language is used for same things that a sum type and pattern-matching are used for in a functional language.

And then re-explaining it using a lot of mathematical jargon, which makes it considerably more obscure than the more hand-wavy explanation. And then saying "isn't that useful?"

But I was happy just informally knowing that they were equivalent, and I would be happier explaining this to someone else informally, using examples of the same code written in Java (say) and Haskell. I don't feel like the mathematical jargon helped? I guess it's sort of neat that you can explain it that way.

(Thanks for continuing to engage on this. It's a fun conversation :) )

Yes, I suspect the blog post is more interesting if you already have a theoretical background, and are interested in the various ways that theory plays out in applications. I certainly doubt the post was written with the HN audience in mind in particular.

For me, theory is like a compression algorithm for knowledge. The more I can interrelate things, the less I have to duplicate the commonalities, and the more I can focus on remembering (and judging based on) the differences. So I get a lot out of this kind of thing.

(Personally, I use these kinds of transforms all the time -- especially "defunctionalize the continuation", which is lovely for mechanically making a simple recursive algorithm into an iterative one more suitable for something like Java. The theoretical background makes me more comfortable going between different representations and keeping track of precisely what is changing and what is being held fixed.)

I guess it's more about fluency in changing code than fluency in reading or writing code. Dynamics rather than statics. I think I can appreciate that if you're just looking at Visitor or sum types in isolation, it's not worth getting into the weeds over. But it's comforting to me to know that if I need to change various parts of a system, I know exactly what and where my degrees of freedom are. I can redefine the module boundaries one step at a time, and relatively smoothly and slowly shift the mass of the codebase around.

I agree that the "defunctionalize the continuation" refactoring is neat and non-obvious.

My feeling about refactorings is that you can use a tool that does it automatically (preferred, when available) or you can do it by hand (when not). I'm not sure I need to be thinking abstractly in math to do the hand-refactoring though. If I know where I'm starting from and where I want to end up then I can informally pattern-match. But I guess it's a more intuitive approach and it sounds like you prefer to think about it a different way.

Refactoring in small mechanical steps is generally less risky, though good tests can also reduce the risk.

Possibly one difference is that in Haskell, you're close to thinking in math already.

Just a heads-up, but sealed classes (basically sum types) and proper pattern matching is coming to Java.

After many years of not having them ;) I'll be very glad to be able to retire this well-used gripe.

We got Streams that don't short-circuit properly and Optionals that throw NullPointerExceptions, what creative fuck-ups do you reckon we'll get with sum types & pattern matching?

Shh, you've said the quiet part out loud ;)

I know in F# it is much better to use a discriminated union because you get automatic comparison and equals implementations.

You can't use functions as map keys, for example.

Is that the same thing as algebraic data types?

"Algebraic data types" refers to having both product and sum types, where products are the records/structs that just about every language has, and sums are indeed the "discriminated unions" under discussion.

Most languages don't have built-in syntax for sum types, so most developers are familiar with sum types only by the shadows cast by a variety of encodings. One of them is the subject of the OP, the Visitor pattern. Another is the "tagged union" seen in C, effectively:

    struct Rectangle { int x, y, w, h; }
    struct Circle { int x, y, r; }

    struct Shape {
      enum {
        RectangleTag,
        CircleTag,
      } tag;

      union {
        struct Rectangle rectangle;
        struct Circle circle;
      };
    };

Which doesn't look too bad until you realize I haven't explained how to use the thing, and then it's similarly involved and even more delicate than the Visitor pattern.

Ah, very interesting thanks. I've seen sum types implemented in terms of inheritance (or fancy modern inheritance such as traits). Doesn't get you exclusive case enforcement, which imho is the thing that's actually useful here.

Some languages have sealed classes for this reason.