The visitor pattern is essentially the same thing as Church encoding

Re:The visitor pattern is essentially the same thing as Chur... by tsimionescu on Thursday February 04, 2021 @05:51PM (#26030714)

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.

[ Parent | on HN ]

Re:The visitor pattern is essentially the same thing as Chur... by layer8 on Thursday February 04, 2021 @06:05PM (#26030829)

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.

[ Parent | on HN ]

Re:The visitor pattern is essentially the same thing as Chur... by tsimionescu on Thursday February 04, 2021 @07:05PM (#26031294)

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.

[ Parent | on HN ]