The visitor pattern is essentially the same thing as Church encoding

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 ]