4 ms·
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 matt
by dwohnitmok 6y ago
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
- tsimionescu 6y agoThat 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.