Item — HN Reader

The benefit is that you can decouple the implementation of the operation from the implementation of the sum type. For example, a library can provide a sum type, and users of the library can implement their own operations on it. This is often necessary for proper separation of concerns. For example, the sum type may be a domain object, and the operations may be database operations, UI operations, or other I/O or conversion operations. You don’t want the domain layer to have dependencies on the database, UI, I/O, etc., which it would have if those operations were implemented in the sum type itself.

It’s exactly the same benefits provided by language-native sum types with ADT pattern matching (aside from the visitor pattern requiring more boilerplate).

The operation can itself be a polymorphic operation on a different type hierarchy or sum type, which is the scenario you are thinking of, but that’s not necessary for being able to benefit from the visitor pattern.

Read the original description of the visitor pattern in the GoF book. It’s about implementing operations on an existing type hierarchy without having to modify the code of that type hierarchy.

1 comments

To illustrate how to implement what you are describing without a visitor pattern if we don't care about subtypes:

  //library code
  sealed class TreeNode{
    Object[] children;
  }
  sealed class LeafNode {
    int value
  } 

  //application code
  int sumTree(Object o) {
    if(o instanceof TreeNode) {
      var tn = (TreeNode)o;
      sum += sumTree(tn);
    } else if (o instanceof LeafNode) {
      var ln = (LeafNode) o;
      sum += sumTree(ln) ;
    } 
  } 
  int sumTree(TreeNode a) {
    var sum = 0;
    for (Object o in a.Children) {
      sum += sumTree(o) ;
    }
    return sum;
  }
  int sumTree(LeafNode ln) {
    return ln.value;
  }

For some added type safety, we could use a marker interface instead of Object, but the code would be equivalent. You don't need visitors or ADTs even if you're working with Java 1.0 (you could actually write this in C pretty easily).

Now, if you start adding actual subtypes to TreeNode and LeafNode, this will quickly stop working, especially if you want more than one operation.

For example, if you wanted to add a DictionaryTreeNode that stores its children in a dictionary instead of a list, the visitor-based version would not require any change to the SumTree visitor, as DictionaryTreeNode can just call visitTreeNode in its accept() method.

ADTs and pattern matching don't solve this problem in any way - you can't add a new node subtype, because the operation explicitly decides what to do based on the variant.

Ifs and type checks are not a substitute for the visitor pattern, at least in statically typed languages, because they don't give you compile-time checks (exhaustiveness checking, as you say).

The visitor pattern doesn't require you to have a hierarchy of operations. It doesn't even require the sum type options to form a public type hierarchy. For example, the following Java code implements the typical binary-tree sum type:

    public abstract class Tree<V>
    {
        public abstract <R> R apply(Visitor<? super V, R> visitor);

        public interface Visitor<V, R>
        {
            public R whenLeaf(V value);

            public R whenNode(Tree<? extends V> left, Tree<? extends V> right);
        }

        public static <V> Tree<V> leaf(V value)
        {
            return new Tree<V>()
            {
                @Override
                public <R> R apply(Visitor<? super V, R> visitor)
                {
                    return visitor.whenLeaf(value);
                }
            };
        }

        public static <V> Tree<V> node(Tree<? extends V> left, Tree<? extends V> right)
        {
            return new Tree<V>()
            {
                @Override
                public <R> R apply(Visitor<? super V, R> visitor)
                {
                    return visitor.whenNode(left, right);
                }
            };
        }
        
        private Tree() { }
    }

This is what I'm describing.

(Incidentally, that design also allows you to replace the implementation by a tagged-union approach. The result wouldn't be the full visitor pattern anymore, of course.)

EDIT: Another way to put this: The visitor pattern abstracts away the case-distinction mechanism into a single implementation. In your code example, every operation (like sumTree) has to re-implement the case-distinction mechanism, that is, the ifs and the type checks. The visitor pattern decouples the case-distinction mechanism from the concrete case distinctions.

The example you're showing is what I would call over complicated. It does an awful lot of work just to gain a little bit of extra type safety compared to mine. You are introducing an extra type parameter (V is good, I was just lazy, but R is only needed because of the Visitor formalism) and 3 extra methods (accept, whenLeaf and whenNode). This all makes the code much harder to follow, and all it gets you is a little bit of extra type safety. It's true that this code in particular is easily and even better replaced with a discriminated union.

But I maintain my opinion that this is not the purpose of the Visitor pattern. I would go so far as to say that this is an anti-pattern. The visitor pattern is only useful when your model actually needs double dispatch - when you have a hierarchy of types with proper subtypes that need to be handled by a hierarchy of operations. If you do have this problem, the only solutions are the visitor pattern or native multiple dispatch like in CLOS. ADTs and pattern matching can't solve this problem.