4 ms·
That 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 equivalen
by tsimionescu 6y ago
That 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.
- tsimionescu 6y agoForgot one other important distinction: if we wanted to add a new expression subtype that can behave like one of the existing types for existing operations, that is not possible with the discriminated union variant. Say we wanted to add an SmallAddition, that stores its two numbers as bytes, but converts them to int when needed. We could add this without modifying any code in the visitors in the C# version (well, technically we may have a problem because we accessed the fields directly, but that's inconsequential). In the pseudo-Haskell version, we would need to modify all 6 evaluation functions just to handle the new Expression subtype.
- dwohnitmok 6y ago> In the pseudo-Haskell version, we would need to modify all 6 evaluation functions just to handle the new Expression subtype. That's not true. I think you may be misunderstanding open unions (or polymorphic variants) here. Tags are types in and of themselves. That's why these are all `type alias`es. You could decide to modify the type alias if you'd like, but you don't have to. You can add the additional tag just to the call site.
- tsimionescu 6y agoSo how would a subtype of Addition look here? Who would tell stringEvaluator how to handle this SmallNumberAddition?
- dwohnitmok 6y agoThere wouldn't be a subtype of Addition because Haskell doesn't have a notion of subtyping in the same way C# does. It would depend on the particulars of what the difference between SmallNumberAddition and Addition look like (in particular which parts are kept with the same functionality and which are different). The answer could be either a simple function or a typeclass depending on that.
- dwohnitmok 6y agointerface ExpressionOpen { T accept<T>(Evaluator<T> eval) => throw new NotImplementedException("Unsupported combination"); } interface ComplexExpressionOpen : ExpressionOpen { T accept<T>(ComplexEvaluator<T> eval) => throw new NotImplementedException("Unsupported combination"); } Those don't really count though. Heck if you allow that I can write the code way shorter in true Haskell (not pseudo-Haskell) as well. In particular //we don't need any kind of boilerplate similar to evaluateExtendedExpression. That was purely for combinatorial safety. You could remove it altogether if you wanted. The whole point of the visitor pattern is to prevent you from being able to put unsupported combinations together. If you get rid of that requirement you don't need types at all and there are far far easier ways of doing this than either with the visitor pattern or with discriminated unions (just do it all with nested dictionaries for a fraction of the code). Throwing this exception is basically a cheat is it not? > support for recursive types I think every statically typed language I know has support for recursive types. Certainly C# does. > pattern matching Eh... I'm not really using pattern matching in any real sense here. They could be replaced by if statements. The only reason it's there is because there's total type erasure in Haskell so runtime dynamic dispatch isn't really a thing in the same way it is in C#.