6 ms·
It's particularly weird because most statically-type functional languages have discriminated unions as a practical alternative to the visitor pattern anyway.
by dfgdghdf 6y ago
It's particularly weird because most statically-type functional languages have discriminated unions as a practical alternative to the visitor pattern anyway.
- jameshart 6y agoRight. 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.
- dfgdghdf 6y agoI 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.
- Twisol 6y agoMy 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-object-algebras-to-finally-tagless-interpreters-2/ https://oleksandrmanzyuk.wordpress.com/2014/06/18/from-objec...
- matt-noonan 6y agoThis 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.
- kaba0 6y agoJust a heads-up, but sealed classes (basically sum types) and proper pattern matching is coming to Java.
- Twisol 6y agoAfter many years of not having them ;) I'll be very glad to be able to retire this well-used gripe.
- skybrian 6y agoThat'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.
- Twisol 6y agoI'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.
- skybrian 6y agoI 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.
- Twisol 6y agoThe 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?
- skybrian 6y ago
- dboreham 6y agoIs that the same thing as algebraic data types?
- Twisol 6y ago"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.
- dboreham 6y agoAh, 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.
- kaba0 6y agoSome languages have sealed classes for this reason.
- tsimionescu 6y agoThe 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.
- dwohnitmok 6y agoDiscriminated 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
- Gabriel439 6y agoAuthor 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