16 ms·

The visitor pattern is essentially the same thing as Church encoding

177 points by lelf 6y ago

magicalhippo 6y ago
Having only a cursory knowledge of Haskell I found most of the examples rather impenetrable. From the text it seems this could be done in say C#, Java or C++, which sounds really interesting. Anyone have any examples or outlines of this in any such language for non-functional plebs like me?
- gampleman 6y ago
  This is a valid definition in TypeScript: type Shape<T> = ( circle: (x: number, y: number, r: number) => T, rectangle: (x: number, y: number, w: number, h: number) => T ) => T; function Circle<T>(x: number, y: number, r: number): Shape<T> { return (_Circle, _Rectangle) => _Circle(x, y, r); } function Rectangle<T>(x: number, y: number, w: number, h: number): Shape<T> { return (_Circle, _Rectangle) => _Rectangle(x, y, w, h); } const exampleCircle = Circle(2, 1.4, 4.5); const exampleRectangle = Rectangle(1.3, 3.1, 10.3, 7.7); function area(shape: Shape<unknown>): number { const s = shape as Shape<number>; return s( (x, y, r) => Math.PI * r * r, (x, y, w, h) => w * h ); } export function main() { console.log(area(exampleCircle)); console.log(area(exampleRectangle)); } Unfortunately I think the cast might be necessary, but happy to see another solution from someone with more typescript expertise.
  - magicalhippo 6y ago
    Thanks, that helps a lot! Never used TypeScript either (I feel like such a Luddite these days) but this is perfectly understandable.
  - DougBTX 6y ago
    It works without the cast if Shape is a generic function itself: type Shape = <T>( circle: (x: number, y: number, r: number) => T, rectangle: (x: number, y: number, w: number, h: number) => T ) => T; function Circle(x: number, y: number, r: number): Shape { return (_Circle, _Rectangle) => _Circle(x, y, r); } function Rectangle(x: number, y: number, w: number, h: number): Shape { return (_Circle, _Rectangle) => _Rectangle(x, y, w, h); } const exampleCircle = Circle(2, 1.4, 4.5); const exampleRectangle = Rectangle(1.3, 3.1, 10.3, 7.7); function area(shape: Shape): number { return shape( (x, y, r) => Math.PI * r * r, (x, y, w, h) => w * h ); } console.log(area(exampleCircle)); console.log(area(exampleRectangle));
    - throw_m239339 6y ago
      I'm embarrassed to admit it took me a while to make sense of that code snippet. Now, in order for it to work, a language has to support closures, not just functions.
      - Twisol 6y ago
        > Now, in order for it to work, a language has to support closures, not just functions. Objects are a reasonable stand-in for closures. Pass in the first batch of arguments to the constructor, and store them as fields. Access them from the method (which plays the role of the "returned" closure) when it's called later. (This is effectively the same as "closure conversion" in the literature, but we're taking advantage of the implicit-receiver convention to hide the parameter by which we're passing the prepared fields.)
  - lmm 6y ago
    You just need to make the function generic rather than the type: type Shape = <T extends unknown>( circle: (x: number, y: number, r: number) => T, rectangle: (x: number, y: number, w: number, h: number) => T ) => T; function Circle<T>(x: number, y: number, r: number): Shape { return (_Circle, _Rectangle) => _Circle(x, y, r); } function Rectangle<T>(x: number, y: number, w: number, h: number): Shape { return (_Circle, _Rectangle) => _Rectangle(x, y, w, h); } const exampleCircle = Circle(2, 1.4, 4.5); const exampleRectangle = Rectangle(1.3, 3.1, 10.3, 7.7); function area(shape: Shape): number { return shape( (_x, _y, r) => Math.PI * r * r, (_x, _y, w, h) => w * h ); } function main() { console.log(area(exampleCircle)); console.log(area(exampleRectangle)); } main()
  - monzee 6y ago
    You can generalize this with TS's fancy mapped types: type Sum<K> = <T> (cases: Pattern<K, T>) => T type Pattern<K, T> = { [V in keyof K]: K[V] extends any[] ? (...args: K[V]) => T : never } which takes TS very close to ML: type Shape = Sum<{ circle: [number, number, number], rectangle: [number, number, number, number] }> function Circle(x: number, y: number, r: number): Shape { return ({ circle }) => circle(x, y, r); } function Rectangle(x: number, y: number, w: number, h: number): Shape { return ({ rectangle }) => rectangle(x, y, w, h); } function area(shape: Shape): number { return shape({ circle: (x, y, r) => Math.PI * r * r, rectangle: (x, y, w, h) => w * h }); }
- Twisol 6y ago
  Here's a slightly different Java example, for variety in the examples you're getting ;) I also recommend checking out the paper on object algebras [0], which takes this approach much further. Notice that in some sense, the structure of the type is inferable from just the visitor interface. Everything else is just an explosion of boilerplate. (This is somewhat explained in the object algebras framework, as you can have multiple types accepting these visitors, just as much as having multiple visitors for the same type. In other words, this is related to the "expression problem".) [0] https://www.cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf https://www.cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf // An "external visitor", with the recursion external to the type being visited. // The visitor is responsible for visiting each of the children. public interface ExprVisitor1<Result> { Result lit(double x); Result add(Expr left, Expr right); Result sub(Expr left, Expr right); } // An "internal visitor", with the recursion internal to the type being visited. // I like these best, because the recursion can be turned into a tight loop // (defunctionalize the continuation!) in a single place (in Expr). // But you lose some expressivity, e.g. no short-circuiting the recursion. // You can elaborate the recursion scheme of course, e.g. // Result add(Supplier<Result> left, Supplier<Result> right); // (but now it might be impossible to flatten the stack) public interface ExprVisitor2<Result> { Result lit(double x); Result add(Result left, Result right); Result sub(Result left, Result right); } public abstract class Expr { private Expr() {} public abstract <Result> Result visit(ExprVisitor2<Result> visitor); public static Expr lit(final double x) { return new Expr() { public @Override <Result> Result visit(final ExprVisitor2<Result> visitor) { return visitor.lit(x); } } } public static Expr add(final Expr left, final Expr right) { return new Expr() { public @Override <Result> Result visit(final ExprVisitor2<Result> visitor) { return visitor.add(left.visit(visitor), right.visit(visitor)); } } } public static Expr sub(final Expr left, final Expr right) { return new Expr() { public @Override <Result> Result visit(final ExprVisitor2<Result> visitor) { return visitor.sub(left.visit(visitor), right.visit(visitor)); } } } }
- _old_dude_ 6y ago
  In Java, interface Shape<T> { interface _Circle<T> { T apply(int x, int y, int r); } interface _Rectangle<T> { T apply(int x, int y, int w, int h); } T apply(_Circle<T> circle, _Rectangle<T> rectangle); static <T> Shape<T> Circle(int x, int y, int r) { return (circle, rectangle) -> circle.apply(x, y, r); } static <T> Shape<T> Rectangle(int x, int y, int w, int h) { return (circle, rectangle) -> rectangle.apply(x, y, w, h); } static double area(Shape<?> shape) { var s = (Shape<Double>) shape; return s.apply( (x, y, r) -> Math.PI * r * r, (x, y, w, h) -> 1. * w * h ); } static void main(String[] args) { var exampleCircle = Circle(2, 1, 4); var exampleRectangle = Rectangle(1, 3, 10, 7); System.out.println(area(exampleCircle)); System.out.println(area(exampleRectangle)); } } BTW, you can use the same encoding when you write a Promise in JS.
  - Twisol 6y ago
    As with the TypeScript examples, we can make the top-level apply method generic instead of the whole class to avoid some casts. In particular, notice that the <T> inferred from calling Circle() and Rectangle() is the unmeaningful <Object>. The downside is that Java doesn't let you implement generic methods with lambdas, which is silly, so you have to use an anonymous subclass. But at least the call-side uses stay the same. (And then, combining the `_Circle` and `_Rectangle` interfaces gets you to a more canonical visitor pattern, at the expense of lambdas at the call-site.) public interface Shape { interface _Circle<T> { T apply(int x, int y, int r); } interface _Rectangle<T> { T apply(int x, int y, int w, int h); } <T> T apply(_Circle<T> circle, _Rectangle<T> rectangle); static Shape Circle(int x, int y, int r) { return new Shape() { public <T> T apply(_Circle<T> circle, _Rectangle<T> rectangle) { return circle.apply(x, y, r); } }; } static Shape Rectangle(int x, int y, int w, int h) { return new Shape() { public <T> T apply(_Circle<T> circle, _Rectangle<T> rectangle) { return rectangle.apply(x, y, w, h); } }; } static double area(Shape shape) { return shape.apply( (x, y, r) -> Math.PI * r * r, (x, y, w, h) -> 1. * w * h ); } static void main(String[] args) { var exampleCircle = Circle(2, 1, 4); var exampleRectangle = Rectangle(1, 3, 10, 7); System.out.println(area(exampleCircle)); System.out.println(area(exampleRectangle)); } }
- ts0000 6y ago
  In addition to the other TypeScript examples, here's one that I would actually use. Now, it's not encoding the types not as positional, but named arguments via objects. Allows me to destructure them, for added clarity. type Circle = {x: number; y: number; r: number}; type Rectangle = {x: number; y: number; w: number; h: number}; type Shape = <T>(xs: { circle: (args: Circle) => T; rectangle: (args: Rectangle) => T; }) => T; function Circle(x: Circle): Shape { return ({circle}) => circle(x); } function Rectangle(x: Rectangle): Shape { return ({rectangle}) => rectangle(x); } const exampleCircle = Circle({x: 2, y: 1.4, r: 4.5}); const exampleRectangle = Rectangle({x: 1.3, y: 3.1, w: 10.3, h: 7.7}); const area = (shape: Shape): number => shape({ circle: ({r}: Circle) => Math.PI * r * r, rectangle: ({w, h}: Rectangle) => w * h, }); console.log(area(exampleCircle)); console.log(area(exampleRectangle)); /edit: Fixed formatting. /edit: Clarify something.
  - jameshart 6y ago
    This feels like a pattern where the naming choices obscure the intent. The ‘Shape’ type doesn’t capture the essence of a ‘shape’ - it captures the essence of being ‘visitable by a visitor that knows about shapes’ or ‘able to handle shapes’. The things which are instances of Shape are functions that accept circles or rectangles, not actual circles or rectangles. So maybe call it ‘VisitableShape’, or ‘ShapeHandler’; and instead of calling its functions ‘circle’ and ‘rectangle’, call them ‘visitCircle’ or ‘handleCircle’... Also, you seem to have created functions and types with the same names (Circle and Rectangle) which seems dangerous.
    - Twisol 6y ago
      > The things which are instances of Shape are functions that accept circles or rectangles, not actual circles or rectangles. The naming is confusing, but it's misled you in the opposite direction. Things that are instances of Shape are functions that accept handlers of circles or rectangles. The handlers, unfortunately, are named `circle` and `rectangle`. I would prefer `onCircle` and `onRectangle` in this context, because we're lacking the context of a true `match` expression to disambiguate the naming. type Shape = <T>(handlers: { onCircle: (args: Circle) => T; onRectangle: (args: Rectangle) => T; }) => T; > Also, you seem to have created functions and types with the same names (Circle and Rectangle) which seems dangerous. I think this is an idiom for defining a canonical constructor for a type. It's a little funky here because they're returning Shape, not Circle or Rectangle, and the latter are not subtypes of Shape. But it mostly tracks alongside the rest of the encoding.
- scatters 6y ago
  Here's the first example in C++: #include <concepts> #include <iostream> #include <numbers> template<class shape> concept Shape = requires( shape s, shape (&&circle)(double, double, double), shape (&&rectangle)(double, double, double, double)) { { s(circle, rectangle) } -> std::same_as<shape>; }; auto Circle = [](double x, double y, double r) -> Shape auto { return [=](auto&& circle, auto&& rectangle) { return circle(x, y, r); }; }; auto Rectangle = [](double x, double y, double w, double h) -> Shape auto { return [=](auto&& circle, auto&& rectangle) { return rectangle(x, y, w, h); }; }; Shape auto exampleCircle = Circle(2.0, 1.4, 4.5); Shape auto exampleRectangle = Rectangle(1.3, 3.1, 10.3, 7.7); auto area = [](Shape auto shape) -> double { return shape( [](auto, auto, auto r) { return std::numbers::pi * r * r; }, [](auto, auto, auto w, auto h) { return w * h; }); }; int main() { std::cout << area(exampleCircle) << std::endl; std::cout << area(exampleRectangle) << std::endl; } Of course, this is missing type-erasure, which you'd need to pass `Shape` across TU boundaries, but that's unnecessary if you're happy to use parametric polymorphism.
  - pjmlp 6y ago
    Which could be done with a little help from std::any, just as info for others.
  - dfgdghdf 6y ago
    Is C++ cheating since it has such a powerful type-system? I would like to see an attempt in Java.
  - matheusmoreira 6y ago
    Whoa! C++ has become an almost completely different language since I learned it over 10 years ago...
    - jfengel 6y ago
      That was precisely what I was going to say. I don't recognize any of that.
- chriswarbo 6y ago
  We can think of "data" as simply deferring a choice/branch. For example consider this code: boolean function1(...) { FOO return true; } void function2(...) { BAR if (function1(...)) { BAZ } else { QUUX } } The boolean lets us separate how to make a decision (which we define in function1), from how to handle a decision (which we define in function2). We can always eliminate this data by bringing those two things together, e.g. // Inline function1 into function2 void function3(...) { FOO BAR if (true) { BAZ } else { QUUX } } // Simplify the if/then/else void function4(...) { FOO BAR BAZ } Of course, it's very useful to keep things separate and to pass data around (modularity, readability, etc.). My point is that the computer/language doesn't care about these things, so we can use refactorings like this to 'distill the essence' of what data 'really is' (from this one perspective, at least). So what can we do with a boolean? - We can discard it. Such code can always be refactored to eliminate the boolean (it's dead code). - Pass it to some other code. We can always refactor this to remove such intermediate steps, e.g. above we inlined 'function1' to avoid passing the boolean around. - Construct them. We do this by using the "constructors" 'true' or 'false', AKA the "introduction forms". - Branch on them using if/then/else. This is also called "destructing", where if/then/else is a "destructor" or "elimination form". - Simplify 'if(true) ...' and 'if(false) ...'. Here we are 'destructing a constructor', which can always be replaced by the relevant branch. If we apply these refactorings over and over we can eventually simplify-away every boolean value in a program. There are a couple of things to keep in mind: - Some languages have special-case boolean operations like '!foo'. Those are equivalent to functions containing branches, which can be refactored as above, e.g. boolean not(boolean x) { if (x) { return false; } else { return true; } } boolean and(boolean x, boolean y) { if (x) { return y; } else { return false; } } boolean or(boolean x, boolean y) { if (x) { return true; } else { return y; } } - To fully eliminate data, we need to include any 'external' code, e.g. 'inlining' external libraries, system calls, third-party APIs, etc. For simplicity I'll just assume we're using a single program in a single language, but the principle still holds in general. Note that inlining intermediate steps and removing unused parameters have nothing to do with booleans themselves; they apply to all forms of data. Hence the 'essence' of booleans is the simplification of 'if(true)...' and if(false)...'. We can do this with booleans since they are a "sum type", i.e. there are a few distinct forms of boolean (namely "true" and "false"). This is similar to the article's "Shape" type, which has a "Circle" form and a "Rectangle" form. OOP languages don't tend to support sum types directly; instead we can 'fake it' using subtypes. Here's an example, where I've implemented the simplification behaviour using subtype polymorphism: abstract class Boolean { T ifThenElse(T t, T e); } class True extends Boolean { T ifThenElse(T t, T e) { return t; } } class False extends Boolean { T ifThenElse(T t, T e) { return e; } } There's a slight wrinkle here, since calling 'ifThenElse(foo, bar)' will execute both 'foo' and 'bar'; we'll just get one of them returned back to us. If this is a problem, we can wrap our branches in zero-argument functions, pass those to 'ifThenElse', and call whichever function gets returned. Note that this is actually how Smalltalk implements boolean branching! https://rosettacode.org/wiki/Conditional_structures#Smalltalk https://rosettacode.org/wiki/Conditional_structures#Smalltal... Hopefully I've demonstrated that the three classed defined above are a complete implementation of booleans: we have the constructors ('new True()' and 'new False()'), the destructor 'ifThenElse(thenBranch, elseBranch)', and we don't need anything else. To drive this point home, here's how we can define boolean algebra, translated from the above: // not(x) x.ifThenElse(new False(), new True()) // and(x, y) x.ifThenElse(y, new False()) // or(x, y) x.ifThenElse(new True(), y) This implementation of Boolean is a rather simple form of "visitor pattern": the implementation of the "ifThenElse algorithm" is spread out amongst different implementations of the method, where each subclass knows how to handle its own case, and we just dispatch on whatever Boolean object we happen to have. The point of Church Encoding is that we don't actually need these classes and polymorphism at all: rather than wrapping up these methods into classes, defining a class hierarchy, constructing instances of these subclasses, invoking methods on those instances, dynamically dispatching on the vtables, etc.; we can just pass the functions around directly! Switching to JS, since it has first-class functions, here's my first example again: const trueIfThenElse = (t, e) => t; const falseIfThenElse = (t, e) => e; function1(...) { FOO return trueIfThenElse; } function2(...) { BAR function1(...)(BAZ, QUUX) } If we want to avoid executing both BAZ and QUUX, we could wrap them up in functions like 'function1(...)(() => BAZ, () => QUUX)()'. We could also rename these functions to simply 'true' and 'false', since they're completely equivalent to those values (although that would be a syntax error in JS). So now we've seen that (a) booleans can be completely implemented using if/then/else (b) the behaviour of if/then/else can be implemented using subclass polymorphism (c) subclass polymorphism can be emulated by passing around first-class functions. Note that we could have skipped all the OOP stuff and gone straight to functions, but I thought it might help some people, and it's also interesting in its own right. This also extends to sum types with any number of distinct forms (which we now know are "constructors"). The rule is simple: a type with N constructors can be represented as a function which takes N arguments, and returns one of them. For example, we could represent Colour, with Red/Green/Blue like this: const red = (r, g, b) => r; const green = (r, g, b) => g; const blue = (r, g, b) => b; function printColour(c) { console.log(c("Received red", "Given green", "Bestowed with blue")); } There are two other sorts of data to consider: "Product types" contain multiple sub-values, e.g. 'Coordinate(x, y, z)'. For these, the rule is that we call the corresponding argument as a function, passing it the sub-values as arguments. For example: const mkCoord = (x, y, z) => f => f(x, y, z); function showCoord(c) { c((x, y, z) => console.log( "x: " + x.toString + " y:" + y.toString + " z: " + z.toString )); } const origin = mkCoord(0, 0, 0); showCoord(origin); Note that I'm using raw JS numbers and strings for simplicity; we can implement these using Church Encoding (e.g. using 64 booleans to emulate a double-precision float), but it would be tedious for this example. We can combine sums and products, i.e. each constructor can contain sub-values. This is what the "Shape" example from the article does. We just need to combine the two rules: take N arguments (once for each constructor), and call the appropriate argument with the sub-values. For example: const circle = (x, y, r) => (ifCirc, ifRect) => ifCirc(x, y, z) const rectangle = (x, y, w, h) => (ifCirc, ifRect) => ifRect(x, y, w, h) const unitCircle = circle(0, 0, 1); const unitSquare = rectangle(0, 0, 1, 1); function drawShape(s) { s( (x, y, r) => console.log("Circle of radius " + r.toString), (x, y, w, h) => console.log("Rect of area " (w * h).toString) ); } The final possibility is recursive data, where the sub-values can be of the same type we're defining. The article uses a binary tree as an example, but a list is easier. In OOP: abstract class List<T> { U reduce(U init, Function<U, Pair<U, T>> f); } class Nil<T> extends List<T> { U reduce(U init, Function<U, Pair<U, T>> f) { return init; } } class Cons<T> extends List<T> { private T head; private List<T> tail; public Cons(T head, List<T> tail) { this.head = head; this.tail = tail; } U reduce(U init, Function<U, Pair<U, T>> f) { return this.tail.reduce( f(new Pair<U, T>(init, this.head)), f ); } } With first-class functions (this might be slightly off; it's been a while!): const nil = (ifNil, ifCons) => ifNil const cons = (head, tail) => (ifNil, ifCons) => ifCons( head, tail(ifNil, ifCons) ); const oneTwoThree = cons(1, cons(2, cons(3, nil))); const plus = (x, y) => x + y; function sum(lst) { return lst(0, plus); } console.log(sum(oneTwoThree).toString); So the trick to recursive data is that whenever we need to pass a sub-value to one of our N given functions, if that sub-value is of our recursive type (like the 'tail' of a list is another list) then we first call that sub-value with the same N functions we've been given. That way, the structure 'reduces' down to a single result.
- DarkWiiPlayer 6y ago
  Took me like ten minutes to really grok the essence of the second haskell example and now I'm wondering why anybody would ever do that.
- bob1029 6y ago
  Perhaps I haven't had enough caffeine yet, but this sounds exactly like what we get in the latest versions of C# w/ its pattern matching feature: https://docs.microsoft.com/en-us/dotnet/csharp/pattern-matching https://docs.microsoft.com/en-us/dotnet/csharp/pattern-match...
smlckz 6y ago
Enjoy this in Lua (for linked list): https://rextester.com/XGNR33292 https://rextester.com/XGNR33292
delibes 6y ago
Great, but ... why ? How does this benefit me? The code examples in other comments seem to have variations of : return (circle, rectangle) -> circle.apply(x, y, r); Why should my code for circles care about rectangles? This looks terrible to me. What am I missing?
- Twisol 6y ago
  The code you've selected is not "for circles", per se. This is classic double-dispatch -- the function itself represents a circle (via the `x, y, r` values it closes over), and it chooses which receiver to invoke based on its identity. (The parameters in the selected function may be better named `onCircle` and `onRectangle`.) If you just have a Shape, and you need to do something specific depending on the kind of Shape you have, you need some way to tell what kind of Shape you have. You can use `instanceof` and casting, but there's no guarantee that you've handled all cases(^). Moreover, it's painful in some languages (like Java) to extract the subclass-specific fields, as you need to rebind the value to a new variable of the right type first. The Visitor pattern is a classic object-oriented solution to this problem, typically using double dispatch. The Shape itself knows what kind of shape it is, so rather than asking it what type it is, you provide it a set of _strategies_ (no relation to the Strategy pattern), one for each type of Shape. The Shape doesn't know what you want to do with it, so it calls you right back, invoking the circle- or rectangle-specific logic depending on what kind of shape it is. (Hence, double-dispatch.) Gabriel (OP) observes that the Visitor pattern is exactly the Boehm-Berarducci encoding of a sum type. The Visitor pattern is very common in OO programming (see, for instance, abstract syntax trees), so the fact that we're so often using an encoding of a more direct concept is worth remarking on. I know I'd much rather use sum types in general than use the Visitor pattern. (^) As an aside, I've never found "Shape" to be a very convincing example of sum types, as it's much easier to imagine as an open family than as a closed family. In an open family of shapes, there is no "all cases", and instanceof/casting is inappropriate from the beginning. I think object algebras (see my other comment) give a more motivating class of examples of closed families, including ASTs.
  - keithb- 6y ago
    I would like to support your comment and add that I enjoy these articles because I like programming languages and thinking about program execution. However, I think what delibes is getting at is that this is article exhibits a classic trigger for most developers because it starts with naming some language (i.e. Haskell) and then it is filled with assertions that are always "What If": what if your language doesn't support sum types or recursion or algebraic data types or ... Most devs are looking for practical applications for their language of choice so there is a natural inclination toward a critical comparison of "their" language and "my" language. But we should follow Twisol here and not read this article as "language X is better than language Y" or, more precisely, "throw out unnecessary features from language X because you can still perform some task Z". Just take the article for what it is: a great "explanation"[1] of the relation between mathematical foundations and language features or characteristics. This article isn't some heretical tantrum so just sit back and enjoy the learning. [1] https://documentation.divio.com/ https://documentation.divio.com/
injidup 6y ago
If I want dark blood magic for my visitor pattern then I choose C++ over haskell. template <class ...Fs> struct overload : Fs... { template <class ...Ts> overload(Ts&& ...ts) : Fs{std::forward<Ts>(ts)}... {} using Fs::operator()...; }; template <class ...Ts> overload(Ts&&...) -> overload<std::remove_reference_t<Ts>...>; int main() { auto fn = overload( [](int x){ std::cerr << "got int " << x << std::endl;} ,[](std::string x) {std::cerr << "got string " << x << std::endl;} ,[](double x){ std::cerr << "got double " << x << std::endl;} ); fn(10); fn("10"); fn(10.); } outputs got int 10 got string 10 got double 10 See it and believe! http://coliru.stacked-crooked.com/a/71d8de3c82b84382 http://coliru.stacked-crooked.com/a/71d8de3c82b84382
- deleted 6y ago
  [deleted]
mattxxx 6y ago
Here's a better explanation of the visitor pattern than Wikipedia: https://sourcemaking.com/design_patterns/visitor https://sourcemaking.com/design_patterns/visitor ^ Helped me understand why-on-earth anyone would introduce this pattern
- DarkWiiPlayer 6y ago
  Reading that just reminded me of why I hate OOP so much. It's confusing.
- platz 6y ago
  The purpose of the OP post is not to provide an introduction to the visitor pattern. It's to explain the relationship of the visitor pattern with something else. Did you miss this part of the post? > I’m not going to provide a standalone explanation of the visitor pattern since the linked Wikipedia page already does that.
jameshart 6y ago
Like a lot of functional programming writing, this piece seems impenetrable because it comes at a problem from a peculiar angle: given that I have this hammer, what nails can I hit? Starting from the recognition that there’s a trick you can do with typed lambdas to represent ‘types’, it then proceeds to show that you can use pattern matching on those ‘types’ to implement something like the visitor pattern. It never even comes close to showing what that wins you. We found a gang-of-four shaped nail. Done. But the thing is the visitor pattern is a response to a particular problem: double dispatch. You have some logic that needs to vary based on two different types. The classic example is a game where you want to calculate damage effects for different kinds of attack against different kinds of monsters. If you start from a problem like that, the visitor pattern turns out to be useful (but is not the only way to solve it). It’s possible - hard to tell from first reading - that what this article is actually suggesting is that Church Encoding can be used to solve double dispatch problems, by letting you encode a visitor pattern in a particularly elegant way. Which would be a much more interesting insight! It’s far more likely that you are facing a double dispatch problem and looking for a programming tool to solve it with, than that you have elected to use Church encoding to build some types for some reason and are now looking to determine which gang-of-four patterns you can implement in your new type calculus...
- 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 ago
    Right. 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 ago
      I 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.
deleted 6y ago
[deleted]
johndoe42377 6y ago
Obviously, not. Not even apples versus oranges. Church encoding shows you that "all you need is lambda", which is the same to say all you need is a membrane in biology. Even further, Lambda calculus shows you that function creation and application are necessary and sufficient for everything, with obvious parallels to biology (enzymes are just proteins). Visitor pattern is just some wired wrapping to satisfy a rigid type system, which composition of Traits or typeclasses would solve. One just pass a function which knows the structure.
- Twisol 6y ago
  > Obviously, not. Not even apples versus oranges. Formally, `A + B` is isomorphic to `forall T. (A -> T, B -> T) -> T`, where the inner `(A -> T, B -> T)` is the type of a visitor. a + b -- CPS transform = forall t. ((a + b) -> t) -> t -- distribute -> over + = forall t. (a -> t, b -> t) -> t -- if you want to drop even the product, distribute -> over * -- but this loses you the ability to name a separable Visitor = forall t. (a -> t) -> (b -> t) -> t type Visitor a b t = (a -> t, b -> t) type Sum a b = forall t. Visitor a b t -> t iso :: Sum a b -> (a + b) iso s = s (Left, Right) osi :: (a + b) -> Sum a b osi (Left a) = \(onA, onB) -> onA a osi (Right b) = \(onA, onB) -> onB b
  - johndoe42377 6y ago
    I really don't know how to respond to this sectarian bullshit. Three is literally nothing in the ability to create another abstraction by finding an isomorphism, which is just a pair of functions.
    - Gabriel439 6y ago
      You're right that there is no benefit in creating another abstraction, but the point of the post is sometimes the language doesn't have support for the original abstraction (e.g. sum types), so in some cases the other abstraction (e.g. visitor pattern or Church encoding) is the only available abstraction.
jgwil2 6y ago
Recently came across a related article in a series on design pattern equivalents in FP, "Visitor as a sum type".[0] [0] https://blog.ploeh.dk/2018/06/25/visitor-as-a-sum-type/ https://blog.ploeh.dk/2018/06/25/visitor-as-a-sum-type/
deleted 6y ago
[deleted]
siraben 6y ago
More connections between FP and OOP: - Codata in action[0], FP emphasizes thinking about constructors, OOP emphasizes thinking about eliminators - Existential types[1], having higher-ranked types lets you express dynamic dispatch - Lenses[2], generalized getters, setters and traversals [0] https://www.javiercasas.com/articles/codata-in-action/ https://www.javiercasas.com/articles/codata-in-action/ [1] https://wiki.haskell.org/Existential_type https://wiki.haskell.org/Existential_type [2] https://www.schoolofhaskell.com/school/to-infinity-and-beyond/pick-of-the-week/a-little-lens-starter-tutorial https://www.schoolofhaskell.com/school/to-infinity-and-beyon...
guerrilla 6y ago
If the author is here, just a very minor nitpick: You could have done without the shadowing in the examples as that might be confusing to people not entirely awake or not familiar with Haskell.
- Gabriel439 6y ago
  Thank you for the feedback. I was conscientious of that shadowing issue when writing it, but I just wasn't sure what to change on either side to differentiate them.
  - guerrilla 6y ago
    Naming, the hardest problem in programming. I sympathize :)
tiew9Vii 6y ago
I use Church encoding quite a lot in Java for a poor mans pattern matching / ADTs. It's one of the more useful patterns I use. import java.util.function.Function; public abstract class Tree { // Constructor private so the type is sealed. private Tree() {} public abstract <T> T match(Function<Empty, T> a, Function<Leaf, T> b, Function<Node, T> c); public static final class Empty extends Tree { public <T> T match(Function<Empty, T> a, Function<Leaf, T> b, Function<Node, T> c) { return a.apply(this); } public Empty() {} } public static final class Leaf extends Tree { public final int n; public <T> T match(Function<Empty, T> a, Function<Leaf, T> b, Function<Node, T> c) { return b.apply(this); } public Leaf(int n) { this.n = n; } } public static final class Node extends Tree { public final Tree left; public final Tree right; public <T> T match(Function<Empty, T> a, Function<Leaf, T> b, Function<Node, T> c) { return c.apply(this); } public Node(Tree left, Tree right) { this.left = left; this.right = right; } } } Example usage: public String test(Tree t) { return t.match( empty -> "Empty", leaf -> "Leaf", node -> "Node" ); } Original ref: https://apocalisp.wordpress.com/2009/08/21/structural-pattern-matching-in-java/ https://apocalisp.wordpress.com/2009/08/21/structural-patter...

177 points by lelf 6y ago

Having only a cursory knowledge of Haskell I found most of the examples rather impenetrable. From the text it seems this could be done in say C#, Java or C++, which sounds really interesting. Anyone have any examples or outlines of this in any such language for non-functional plebs like me?

gampleman 6y ago
This is a valid definition in TypeScript: type Shape<T> = ( circle: (x: number, y: number, r: number) => T, rectangle: (x: number, y: number, w: number, h: number) => T ) => T; function Circle<T>(x: number, y: number, r: number): Shape<T> { return (_Circle, _Rectangle) => _Circle(x, y, r); } function Rectangle<T>(x: number, y: number, w: number, h: number): Shape<T> { return (_Circle, _Rectangle) => _Rectangle(x, y, w, h); } const exampleCircle = Circle(2, 1.4, 4.5); const exampleRectangle = Rectangle(1.3, 3.1, 10.3, 7.7); function area(shape: Shape<unknown>): number { const s = shape as Shape<number>; return s( (x, y, r) => Math.PI * r * r, (x, y, w, h) => w * h ); } export function main() { console.log(area(exampleCircle)); console.log(area(exampleRectangle)); } Unfortunately I think the cast might be necessary, but happy to see another solution from someone with more typescript expertise.
- magicalhippo 6y ago
  Thanks, that helps a lot! Never used TypeScript either (I feel like such a Luddite these days) but this is perfectly understandable.
- DougBTX 6y ago
  It works without the cast if Shape is a generic function itself: type Shape = <T>( circle: (x: number, y: number, r: number) => T, rectangle: (x: number, y: number, w: number, h: number) => T ) => T; function Circle(x: number, y: number, r: number): Shape { return (_Circle, _Rectangle) => _Circle(x, y, r); } function Rectangle(x: number, y: number, w: number, h: number): Shape { return (_Circle, _Rectangle) => _Rectangle(x, y, w, h); } const exampleCircle = Circle(2, 1.4, 4.5); const exampleRectangle = Rectangle(1.3, 3.1, 10.3, 7.7); function area(shape: Shape): number { return shape( (x, y, r) => Math.PI * r * r, (x, y, w, h) => w * h ); } console.log(area(exampleCircle)); console.log(area(exampleRectangle));
  - throw_m239339 6y ago
    I'm embarrassed to admit it took me a while to make sense of that code snippet. Now, in order for it to work, a language has to support closures, not just functions.
    - Twisol 6y ago
      > Now, in order for it to work, a language has to support closures, not just functions. Objects are a reasonable stand-in for closures. Pass in the first batch of arguments to the constructor, and store them as fields. Access them from the method (which plays the role of the "returned" closure) when it's called later. (This is effectively the same as "closure conversion" in the literature, but we're taking advantage of the implicit-receiver convention to hide the parameter by which we're passing the prepared fields.)
- lmm 6y ago
  You just need to make the function generic rather than the type: type Shape = <T extends unknown>( circle: (x: number, y: number, r: number) => T, rectangle: (x: number, y: number, w: number, h: number) => T ) => T; function Circle<T>(x: number, y: number, r: number): Shape { return (_Circle, _Rectangle) => _Circle(x, y, r); } function Rectangle<T>(x: number, y: number, w: number, h: number): Shape { return (_Circle, _Rectangle) => _Rectangle(x, y, w, h); } const exampleCircle = Circle(2, 1.4, 4.5); const exampleRectangle = Rectangle(1.3, 3.1, 10.3, 7.7); function area(shape: Shape): number { return shape( (_x, _y, r) => Math.PI * r * r, (_x, _y, w, h) => w * h ); } function main() { console.log(area(exampleCircle)); console.log(area(exampleRectangle)); } main()
- monzee 6y ago
  You can generalize this with TS's fancy mapped types: type Sum<K> = <T> (cases: Pattern<K, T>) => T type Pattern<K, T> = { [V in keyof K]: K[V] extends any[] ? (...args: K[V]) => T : never } which takes TS very close to ML: type Shape = Sum<{ circle: [number, number, number], rectangle: [number, number, number, number] }> function Circle(x: number, y: number, r: number): Shape { return ({ circle }) => circle(x, y, r); } function Rectangle(x: number, y: number, w: number, h: number): Shape { return ({ rectangle }) => rectangle(x, y, w, h); } function area(shape: Shape): number { return shape({ circle: (x, y, r) => Math.PI * r * r, rectangle: (x, y, w, h) => w * h }); }
Twisol 6y ago
Here's a slightly different Java example, for variety in the examples you're getting ;) I also recommend checking out the paper on object algebras [0], which takes this approach much further. Notice that in some sense, the structure of the type is inferable from just the visitor interface. Everything else is just an explosion of boilerplate. (This is somewhat explained in the object algebras framework, as you can have multiple types accepting these visitors, just as much as having multiple visitors for the same type. In other words, this is related to the "expression problem".) [0] https://www.cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf https://www.cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf // An "external visitor", with the recursion external to the type being visited. // The visitor is responsible for visiting each of the children. public interface ExprVisitor1<Result> { Result lit(double x); Result add(Expr left, Expr right); Result sub(Expr left, Expr right); } // An "internal visitor", with the recursion internal to the type being visited. // I like these best, because the recursion can be turned into a tight loop // (defunctionalize the continuation!) in a single place (in Expr). // But you lose some expressivity, e.g. no short-circuiting the recursion. // You can elaborate the recursion scheme of course, e.g. // Result add(Supplier<Result> left, Supplier<Result> right); // (but now it might be impossible to flatten the stack) public interface ExprVisitor2<Result> { Result lit(double x); Result add(Result left, Result right); Result sub(Result left, Result right); } public abstract class Expr { private Expr() {} public abstract <Result> Result visit(ExprVisitor2<Result> visitor); public static Expr lit(final double x) { return new Expr() { public @Override <Result> Result visit(final ExprVisitor2<Result> visitor) { return visitor.lit(x); } } } public static Expr add(final Expr left, final Expr right) { return new Expr() { public @Override <Result> Result visit(final ExprVisitor2<Result> visitor) { return visitor.add(left.visit(visitor), right.visit(visitor)); } } } public static Expr sub(final Expr left, final Expr right) { return new Expr() { public @Override <Result> Result visit(final ExprVisitor2<Result> visitor) { return visitor.sub(left.visit(visitor), right.visit(visitor)); } } } }
_old_dude_ 6y ago
In Java, interface Shape<T> { interface _Circle<T> { T apply(int x, int y, int r); } interface _Rectangle<T> { T apply(int x, int y, int w, int h); } T apply(_Circle<T> circle, _Rectangle<T> rectangle); static <T> Shape<T> Circle(int x, int y, int r) { return (circle, rectangle) -> circle.apply(x, y, r); } static <T> Shape<T> Rectangle(int x, int y, int w, int h) { return (circle, rectangle) -> rectangle.apply(x, y, w, h); } static double area(Shape<?> shape) { var s = (Shape<Double>) shape; return s.apply( (x, y, r) -> Math.PI * r * r, (x, y, w, h) -> 1. * w * h ); } static void main(String[] args) { var exampleCircle = Circle(2, 1, 4); var exampleRectangle = Rectangle(1, 3, 10, 7); System.out.println(area(exampleCircle)); System.out.println(area(exampleRectangle)); } } BTW, you can use the same encoding when you write a Promise in JS.
- Twisol 6y ago
  As with the TypeScript examples, we can make the top-level apply method generic instead of the whole class to avoid some casts. In particular, notice that the <T> inferred from calling Circle() and Rectangle() is the unmeaningful <Object>. The downside is that Java doesn't let you implement generic methods with lambdas, which is silly, so you have to use an anonymous subclass. But at least the call-side uses stay the same. (And then, combining the `_Circle` and `_Rectangle` interfaces gets you to a more canonical visitor pattern, at the expense of lambdas at the call-site.) public interface Shape { interface _Circle<T> { T apply(int x, int y, int r); } interface _Rectangle<T> { T apply(int x, int y, int w, int h); } <T> T apply(_Circle<T> circle, _Rectangle<T> rectangle); static Shape Circle(int x, int y, int r) { return new Shape() { public <T> T apply(_Circle<T> circle, _Rectangle<T> rectangle) { return circle.apply(x, y, r); } }; } static Shape Rectangle(int x, int y, int w, int h) { return new Shape() { public <T> T apply(_Circle<T> circle, _Rectangle<T> rectangle) { return rectangle.apply(x, y, w, h); } }; } static double area(Shape shape) { return shape.apply( (x, y, r) -> Math.PI * r * r, (x, y, w, h) -> 1. * w * h ); } static void main(String[] args) { var exampleCircle = Circle(2, 1, 4); var exampleRectangle = Rectangle(1, 3, 10, 7); System.out.println(area(exampleCircle)); System.out.println(area(exampleRectangle)); } }
ts0000 6y ago
In addition to the other TypeScript examples, here's one that I would actually use. Now, it's not encoding the types not as positional, but named arguments via objects. Allows me to destructure them, for added clarity. type Circle = {x: number; y: number; r: number}; type Rectangle = {x: number; y: number; w: number; h: number}; type Shape = <T>(xs: { circle: (args: Circle) => T; rectangle: (args: Rectangle) => T; }) => T; function Circle(x: Circle): Shape { return ({circle}) => circle(x); } function Rectangle(x: Rectangle): Shape { return ({rectangle}) => rectangle(x); } const exampleCircle = Circle({x: 2, y: 1.4, r: 4.5}); const exampleRectangle = Rectangle({x: 1.3, y: 3.1, w: 10.3, h: 7.7}); const area = (shape: Shape): number => shape({ circle: ({r}: Circle) => Math.PI * r * r, rectangle: ({w, h}: Rectangle) => w * h, }); console.log(area(exampleCircle)); console.log(area(exampleRectangle)); /edit: Fixed formatting. /edit: Clarify something.
- jameshart 6y ago
  This feels like a pattern where the naming choices obscure the intent. The ‘Shape’ type doesn’t capture the essence of a ‘shape’ - it captures the essence of being ‘visitable by a visitor that knows about shapes’ or ‘able to handle shapes’. The things which are instances of Shape are functions that accept circles or rectangles, not actual circles or rectangles. So maybe call it ‘VisitableShape’, or ‘ShapeHandler’; and instead of calling its functions ‘circle’ and ‘rectangle’, call them ‘visitCircle’ or ‘handleCircle’... Also, you seem to have created functions and types with the same names (Circle and Rectangle) which seems dangerous.
  - Twisol 6y ago
    > The things which are instances of Shape are functions that accept circles or rectangles, not actual circles or rectangles. The naming is confusing, but it's misled you in the opposite direction. Things that are instances of Shape are functions that accept handlers of circles or rectangles. The handlers, unfortunately, are named `circle` and `rectangle`. I would prefer `onCircle` and `onRectangle` in this context, because we're lacking the context of a true `match` expression to disambiguate the naming. type Shape = <T>(handlers: { onCircle: (args: Circle) => T; onRectangle: (args: Rectangle) => T; }) => T; > Also, you seem to have created functions and types with the same names (Circle and Rectangle) which seems dangerous. I think this is an idiom for defining a canonical constructor for a type. It's a little funky here because they're returning Shape, not Circle or Rectangle, and the latter are not subtypes of Shape. But it mostly tracks alongside the rest of the encoding.
scatters 6y ago
Here's the first example in C++: #include <concepts> #include <iostream> #include <numbers> template<class shape> concept Shape = requires( shape s, shape (&&circle)(double, double, double), shape (&&rectangle)(double, double, double, double)) { { s(circle, rectangle) } -> std::same_as<shape>; }; auto Circle = [](double x, double y, double r) -> Shape auto { return [=](auto&& circle, auto&& rectangle) { return circle(x, y, r); }; }; auto Rectangle = [](double x, double y, double w, double h) -> Shape auto { return [=](auto&& circle, auto&& rectangle) { return rectangle(x, y, w, h); }; }; Shape auto exampleCircle = Circle(2.0, 1.4, 4.5); Shape auto exampleRectangle = Rectangle(1.3, 3.1, 10.3, 7.7); auto area = [](Shape auto shape) -> double { return shape( [](auto, auto, auto r) { return std::numbers::pi * r * r; }, [](auto, auto, auto w, auto h) { return w * h; }); }; int main() { std::cout << area(exampleCircle) << std::endl; std::cout << area(exampleRectangle) << std::endl; } Of course, this is missing type-erasure, which you'd need to pass `Shape` across TU boundaries, but that's unnecessary if you're happy to use parametric polymorphism.
- pjmlp 6y ago
  Which could be done with a little help from std::any, just as info for others.
- dfgdghdf 6y ago
  Is C++ cheating since it has such a powerful type-system? I would like to see an attempt in Java.
- matheusmoreira 6y ago
  Whoa! C++ has become an almost completely different language since I learned it over 10 years ago...
  - jfengel 6y ago
    That was precisely what I was going to say. I don't recognize any of that.
chriswarbo 6y ago
We can think of "data" as simply deferring a choice/branch. For example consider this code: boolean function1(...) { FOO return true; } void function2(...) { BAR if (function1(...)) { BAZ } else { QUUX } } The boolean lets us separate how to make a decision (which we define in function1), from how to handle a decision (which we define in function2). We can always eliminate this data by bringing those two things together, e.g. // Inline function1 into function2 void function3(...) { FOO BAR if (true) { BAZ } else { QUUX } } // Simplify the if/then/else void function4(...) { FOO BAR BAZ } Of course, it's very useful to keep things separate and to pass data around (modularity, readability, etc.). My point is that the computer/language doesn't care about these things, so we can use refactorings like this to 'distill the essence' of what data 'really is' (from this one perspective, at least). So what can we do with a boolean? - We can discard it. Such code can always be refactored to eliminate the boolean (it's dead code). - Pass it to some other code. We can always refactor this to remove such intermediate steps, e.g. above we inlined 'function1' to avoid passing the boolean around. - Construct them. We do this by using the "constructors" 'true' or 'false', AKA the "introduction forms". - Branch on them using if/then/else. This is also called "destructing", where if/then/else is a "destructor" or "elimination form". - Simplify 'if(true) ...' and 'if(false) ...'. Here we are 'destructing a constructor', which can always be replaced by the relevant branch. If we apply these refactorings over and over we can eventually simplify-away every boolean value in a program. There are a couple of things to keep in mind: - Some languages have special-case boolean operations like '!foo'. Those are equivalent to functions containing branches, which can be refactored as above, e.g. boolean not(boolean x) { if (x) { return false; } else { return true; } } boolean and(boolean x, boolean y) { if (x) { return y; } else { return false; } } boolean or(boolean x, boolean y) { if (x) { return true; } else { return y; } } - To fully eliminate data, we need to include any 'external' code, e.g. 'inlining' external libraries, system calls, third-party APIs, etc. For simplicity I'll just assume we're using a single program in a single language, but the principle still holds in general. Note that inlining intermediate steps and removing unused parameters have nothing to do with booleans themselves; they apply to all forms of data. Hence the 'essence' of booleans is the simplification of 'if(true)...' and if(false)...'. We can do this with booleans since they are a "sum type", i.e. there are a few distinct forms of boolean (namely "true" and "false"). This is similar to the article's "Shape" type, which has a "Circle" form and a "Rectangle" form. OOP languages don't tend to support sum types directly; instead we can 'fake it' using subtypes. Here's an example, where I've implemented the simplification behaviour using subtype polymorphism: abstract class Boolean { T ifThenElse(T t, T e); } class True extends Boolean { T ifThenElse(T t, T e) { return t; } } class False extends Boolean { T ifThenElse(T t, T e) { return e; } } There's a slight wrinkle here, since calling 'ifThenElse(foo, bar)' will execute both 'foo' and 'bar'; we'll just get one of them returned back to us. If this is a problem, we can wrap our branches in zero-argument functions, pass those to 'ifThenElse', and call whichever function gets returned. Note that this is actually how Smalltalk implements boolean branching! https://rosettacode.org/wiki/Conditional_structures#Smalltalk https://rosettacode.org/wiki/Conditional_structures#Smalltal... Hopefully I've demonstrated that the three classed defined above are a complete implementation of booleans: we have the constructors ('new True()' and 'new False()'), the destructor 'ifThenElse(thenBranch, elseBranch)', and we don't need anything else. To drive this point home, here's how we can define boolean algebra, translated from the above: // not(x) x.ifThenElse(new False(), new True()) // and(x, y) x.ifThenElse(y, new False()) // or(x, y) x.ifThenElse(new True(), y) This implementation of Boolean is a rather simple form of "visitor pattern": the implementation of the "ifThenElse algorithm" is spread out amongst different implementations of the method, where each subclass knows how to handle its own case, and we just dispatch on whatever Boolean object we happen to have. The point of Church Encoding is that we don't actually need these classes and polymorphism at all: rather than wrapping up these methods into classes, defining a class hierarchy, constructing instances of these subclasses, invoking methods on those instances, dynamically dispatching on the vtables, etc.; we can just pass the functions around directly! Switching to JS, since it has first-class functions, here's my first example again: const trueIfThenElse = (t, e) => t; const falseIfThenElse = (t, e) => e; function1(...) { FOO return trueIfThenElse; } function2(...) { BAR function1(...)(BAZ, QUUX) } If we want to avoid executing both BAZ and QUUX, we could wrap them up in functions like 'function1(...)(() => BAZ, () => QUUX)()'. We could also rename these functions to simply 'true' and 'false', since they're completely equivalent to those values (although that would be a syntax error in JS). So now we've seen that (a) booleans can be completely implemented using if/then/else (b) the behaviour of if/then/else can be implemented using subclass polymorphism (c) subclass polymorphism can be emulated by passing around first-class functions. Note that we could have skipped all the OOP stuff and gone straight to functions, but I thought it might help some people, and it's also interesting in its own right. This also extends to sum types with any number of distinct forms (which we now know are "constructors"). The rule is simple: a type with N constructors can be represented as a function which takes N arguments, and returns one of them. For example, we could represent Colour, with Red/Green/Blue like this: const red = (r, g, b) => r; const green = (r, g, b) => g; const blue = (r, g, b) => b; function printColour(c) { console.log(c("Received red", "Given green", "Bestowed with blue")); } There are two other sorts of data to consider: "Product types" contain multiple sub-values, e.g. 'Coordinate(x, y, z)'. For these, the rule is that we call the corresponding argument as a function, passing it the sub-values as arguments. For example: const mkCoord = (x, y, z) => f => f(x, y, z); function showCoord(c) { c((x, y, z) => console.log( "x: " + x.toString + " y:" + y.toString + " z: " + z.toString )); } const origin = mkCoord(0, 0, 0); showCoord(origin); Note that I'm using raw JS numbers and strings for simplicity; we can implement these using Church Encoding (e.g. using 64 booleans to emulate a double-precision float), but it would be tedious for this example. We can combine sums and products, i.e. each constructor can contain sub-values. This is what the "Shape" example from the article does. We just need to combine the two rules: take N arguments (once for each constructor), and call the appropriate argument with the sub-values. For example: const circle = (x, y, r) => (ifCirc, ifRect) => ifCirc(x, y, z) const rectangle = (x, y, w, h) => (ifCirc, ifRect) => ifRect(x, y, w, h) const unitCircle = circle(0, 0, 1); const unitSquare = rectangle(0, 0, 1, 1); function drawShape(s) { s( (x, y, r) => console.log("Circle of radius " + r.toString), (x, y, w, h) => console.log("Rect of area " (w * h).toString) ); } The final possibility is recursive data, where the sub-values can be of the same type we're defining. The article uses a binary tree as an example, but a list is easier. In OOP: abstract class List<T> { U reduce(U init, Function<U, Pair<U, T>> f); } class Nil<T> extends List<T> { U reduce(U init, Function<U, Pair<U, T>> f) { return init; } } class Cons<T> extends List<T> { private T head; private List<T> tail; public Cons(T head, List<T> tail) { this.head = head; this.tail = tail; } U reduce(U init, Function<U, Pair<U, T>> f) { return this.tail.reduce( f(new Pair<U, T>(init, this.head)), f ); } } With first-class functions (this might be slightly off; it's been a while!): const nil = (ifNil, ifCons) => ifNil const cons = (head, tail) => (ifNil, ifCons) => ifCons( head, tail(ifNil, ifCons) ); const oneTwoThree = cons(1, cons(2, cons(3, nil))); const plus = (x, y) => x + y; function sum(lst) { return lst(0, plus); } console.log(sum(oneTwoThree).toString); So the trick to recursive data is that whenever we need to pass a sub-value to one of our N given functions, if that sub-value is of our recursive type (like the 'tail' of a list is another list) then we first call that sub-value with the same N functions we've been given. That way, the structure 'reduces' down to a single result.
DarkWiiPlayer 6y ago
Took me like ten minutes to really grok the essence of the second haskell example and now I'm wondering why anybody would ever do that.
bob1029 6y ago
Perhaps I haven't had enough caffeine yet, but this sounds exactly like what we get in the latest versions of C# w/ its pattern matching feature: https://docs.microsoft.com/en-us/dotnet/csharp/pattern-matching https://docs.microsoft.com/en-us/dotnet/csharp/pattern-match...

smlckz 6y ago

Enjoy this in Lua (for linked list): https://rextester.com/XGNR33292 https://rextester.com/XGNR33292

delibes 6y ago

Great, but ... why ? How does this benefit me? The code examples in other comments seem to have variations of : return (circle, rectangle) -> circle.apply(x, y, r); Why should my code for circles care about rectangles? This looks terrible to me. What am I missing?

Twisol 6y ago
The code you've selected is not "for circles", per se. This is classic double-dispatch -- the function itself represents a circle (via the `x, y, r` values it closes over), and it chooses which receiver to invoke based on its identity. (The parameters in the selected function may be better named `onCircle` and `onRectangle`.) If you just have a Shape, and you need to do something specific depending on the kind of Shape you have, you need some way to tell what kind of Shape you have. You can use `instanceof` and casting, but there's no guarantee that you've handled all cases(^). Moreover, it's painful in some languages (like Java) to extract the subclass-specific fields, as you need to rebind the value to a new variable of the right type first. The Visitor pattern is a classic object-oriented solution to this problem, typically using double dispatch. The Shape itself knows what kind of shape it is, so rather than asking it what type it is, you provide it a set of _strategies_ (no relation to the Strategy pattern), one for each type of Shape. The Shape doesn't know what you want to do with it, so it calls you right back, invoking the circle- or rectangle-specific logic depending on what kind of shape it is. (Hence, double-dispatch.) Gabriel (OP) observes that the Visitor pattern is exactly the Boehm-Berarducci encoding of a sum type. The Visitor pattern is very common in OO programming (see, for instance, abstract syntax trees), so the fact that we're so often using an encoding of a more direct concept is worth remarking on. I know I'd much rather use sum types in general than use the Visitor pattern. (^) As an aside, I've never found "Shape" to be a very convincing example of sum types, as it's much easier to imagine as an open family than as a closed family. In an open family of shapes, there is no "all cases", and instanceof/casting is inappropriate from the beginning. I think object algebras (see my other comment) give a more motivating class of examples of closed families, including ASTs.
- keithb- 6y ago
  I would like to support your comment and add that I enjoy these articles because I like programming languages and thinking about program execution. However, I think what delibes is getting at is that this is article exhibits a classic trigger for most developers because it starts with naming some language (i.e. Haskell) and then it is filled with assertions that are always "What If": what if your language doesn't support sum types or recursion or algebraic data types or ... Most devs are looking for practical applications for their language of choice so there is a natural inclination toward a critical comparison of "their" language and "my" language. But we should follow Twisol here and not read this article as "language X is better than language Y" or, more precisely, "throw out unnecessary features from language X because you can still perform some task Z". Just take the article for what it is: a great "explanation"[1] of the relation between mathematical foundations and language features or characteristics. This article isn't some heretical tantrum so just sit back and enjoy the learning. [1] https://documentation.divio.com/ https://documentation.divio.com/

injidup 6y ago

If I want dark blood magic for my visitor pattern then I choose C++ over haskell. template <class ...Fs> struct overload : Fs... { template <class ...Ts> overload(Ts&& ...ts) : Fs{std::forward<Ts>(ts)}... {} using Fs::operator()...; }; template <class ...Ts> overload(Ts&&...) -> overload<std::remove_reference_t<Ts>...>; int main() { auto fn = overload( [](int x){ std::cerr << "got int " << x << std::endl;} ,[](std::string x) {std::cerr << "got string " << x << std::endl;} ,[](double x){ std::cerr << "got double " << x << std::endl;} ); fn(10); fn("10"); fn(10.); } outputs got int 10 got string 10 got double 10 See it and believe! http://coliru.stacked-crooked.com/a/71d8de3c82b84382 http://coliru.stacked-crooked.com/a/71d8de3c82b84382

deleted 6y ago
[deleted]

mattxxx 6y ago

Here's a better explanation of the visitor pattern than Wikipedia: https://sourcemaking.com/design_patterns/visitor https://sourcemaking.com/design_patterns/visitor ^ Helped me understand why-on-earth anyone would introduce this pattern

DarkWiiPlayer 6y ago
Reading that just reminded me of why I hate OOP so much. It's confusing.
platz 6y ago
The purpose of the OP post is not to provide an introduction to the visitor pattern. It's to explain the relationship of the visitor pattern with something else. Did you miss this part of the post? > I’m not going to provide a standalone explanation of the visitor pattern since the linked Wikipedia page already does that.

jameshart 6y ago

Like a lot of functional programming writing, this piece seems impenetrable because it comes at a problem from a peculiar angle: given that I have this hammer, what nails can I hit? Starting from the recognition that there’s a trick you can do with typed lambdas to represent ‘types’, it then proceeds to show that you can use pattern matching on those ‘types’ to implement something like the visitor pattern. It never even comes close to showing what that wins you. We found a gang-of-four shaped nail. Done. But the thing is the visitor pattern is a response to a particular problem: double dispatch. You have some logic that needs to vary based on two different types. The classic example is a game where you want to calculate damage effects for different kinds of attack against different kinds of monsters. If you start from a problem like that, the visitor pattern turns out to be useful (but is not the only way to solve it). It’s possible - hard to tell from first reading - that what this article is actually suggesting is that Church Encoding can be used to solve double dispatch problems, by letting you encode a visitor pattern in a particularly elegant way. Which would be a much more interesting insight! It’s far more likely that you are facing a double dispatch problem and looking for a programming tool to solve it with, than that you have elected to use Church encoding to build some types for some reason and are now looking to determine which gang-of-four patterns you can implement in your new type calculus...

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 ago
  Right. 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 ago
    I 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.

deleted 6y ago

[deleted]

johndoe42377 6y ago

Obviously, not. Not even apples versus oranges. Church encoding shows you that "all you need is lambda", which is the same to say all you need is a membrane in biology. Even further, Lambda calculus shows you that function creation and application are necessary and sufficient for everything, with obvious parallels to biology (enzymes are just proteins). Visitor pattern is just some wired wrapping to satisfy a rigid type system, which composition of Traits or typeclasses would solve. One just pass a function which knows the structure.

Twisol 6y ago
> Obviously, not. Not even apples versus oranges. Formally, `A + B` is isomorphic to `forall T. (A -> T, B -> T) -> T`, where the inner `(A -> T, B -> T)` is the type of a visitor. a + b -- CPS transform = forall t. ((a + b) -> t) -> t -- distribute -> over + = forall t. (a -> t, b -> t) -> t -- if you want to drop even the product, distribute -> over * -- but this loses you the ability to name a separable Visitor = forall t. (a -> t) -> (b -> t) -> t type Visitor a b t = (a -> t, b -> t) type Sum a b = forall t. Visitor a b t -> t iso :: Sum a b -> (a + b) iso s = s (Left, Right) osi :: (a + b) -> Sum a b osi (Left a) = \(onA, onB) -> onA a osi (Right b) = \(onA, onB) -> onB b
- johndoe42377 6y ago
  I really don't know how to respond to this sectarian bullshit. Three is literally nothing in the ability to create another abstraction by finding an isomorphism, which is just a pair of functions.
  - Gabriel439 6y ago
    You're right that there is no benefit in creating another abstraction, but the point of the post is sometimes the language doesn't have support for the original abstraction (e.g. sum types), so in some cases the other abstraction (e.g. visitor pattern or Church encoding) is the only available abstraction.

jgwil2 6y ago

Recently came across a related article in a series on design pattern equivalents in FP, "Visitor as a sum type".[0] [0] https://blog.ploeh.dk/2018/06/25/visitor-as-a-sum-type/ https://blog.ploeh.dk/2018/06/25/visitor-as-a-sum-type/

deleted 6y ago

[deleted]

siraben 6y ago

More connections between FP and OOP: - Codata in action[0], FP emphasizes thinking about constructors, OOP emphasizes thinking about eliminators - Existential types[1], having higher-ranked types lets you express dynamic dispatch - Lenses[2], generalized getters, setters and traversals [0] https://www.javiercasas.com/articles/codata-in-action/ https://www.javiercasas.com/articles/codata-in-action/ [1] https://wiki.haskell.org/Existential_type https://wiki.haskell.org/Existential_type [2] https://www.schoolofhaskell.com/school/to-infinity-and-beyond/pick-of-the-week/a-little-lens-starter-tutorial https://www.schoolofhaskell.com/school/to-infinity-and-beyon...

guerrilla 6y ago

If the author is here, just a very minor nitpick: You could have done without the shadowing in the examples as that might be confusing to people not entirely awake or not familiar with Haskell.

Gabriel439 6y ago
Thank you for the feedback. I was conscientious of that shadowing issue when writing it, but I just wasn't sure what to change on either side to differentiate them.
- guerrilla 6y ago
  Naming, the hardest problem in programming. I sympathize :)

tiew9Vii 6y ago

I use Church encoding quite a lot in Java for a poor mans pattern matching / ADTs. It's one of the more useful patterns I use. import java.util.function.Function; public abstract class Tree { // Constructor private so the type is sealed. private Tree() {} public abstract <T> T match(Function<Empty, T> a, Function<Leaf, T> b, Function<Node, T> c); public static final class Empty extends Tree { public <T> T match(Function<Empty, T> a, Function<Leaf, T> b, Function<Node, T> c) { return a.apply(this); } public Empty() {} } public static final class Leaf extends Tree { public final int n; public <T> T match(Function<Empty, T> a, Function<Leaf, T> b, Function<Node, T> c) { return b.apply(this); } public Leaf(int n) { this.n = n; } } public static final class Node extends Tree { public final Tree left; public final Tree right; public <T> T match(Function<Empty, T> a, Function<Leaf, T> b, Function<Node, T> c) { return c.apply(this); } public Node(Tree left, Tree right) { this.left = left; this.right = right; } } } Example usage: public String test(Tree t) { return t.match( empty -> "Empty", leaf -> "Leaf", node -> "Node" ); } Original ref: https://apocalisp.wordpress.com/2009/08/21/structural-pattern-matching-in-java/ https://apocalisp.wordpress.com/2009/08/21/structural-patter...