[HN Gopher] The visitor pattern is essentially the same thing as...
___________________________________________________________________
The visitor pattern is essentially the same thing as Church
encoding
Author : lelf
Score : 166 points
Date : 2021-02-04 09:45 UTC (13 hours ago)
(HTM) web link (www.haskellforall.com)
(TXT) w3m dump (www.haskellforall.com)
| siraben wrote:
| 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/
|
| [1] https://wiki.haskell.org/Existential_type
|
| [2] https://www.schoolofhaskell.com/school/to-infinity-and-
| beyon...
| jameshart wrote:
| 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...
| titzer wrote:
| It's worthwhile noting that the example makes use of more than
| just typed lambdas. It uses first-class polymorphism right off
| the bat.
| brundolf wrote:
| A less-general but arguably more useful connection I've seen
| drawn is that the Visitor pattern is basically exchangeable
| with union types + pattern-matching (for languages that have
| these features); in the same way that objects can be exchanged
| with closures and iteration can be exchanged with recursion.
|
| Which one of the two is "better" probably comes down to
| personal preference and/or the language being used, but it's
| good to know that you have the option.
| haskellandchill wrote:
| Not everything is about hitting nails. This is more about
| thinking about what hammers and nails are made of. If you don't
| know Church Encodings already, well typed church encodings are
| going to be a bad place to start. Personally I would look at
| the
| https://en.wikipedia.org/wiki/Mogensen%E2%80%93Scott_encodin...
| it is simpler to teach as a first functional encoding of data
| types.
|
| The fact that it is a visitor pattern is linking insight from
| functional and object oriented design patterns together. I can
| see the confusion if one only views those design patterns on a
| practical level. The article is really teaching the Bohm-
| Berarducci encoding to more experienced functional programmers
| as a concept not as a hammer to solve problems.
| jimmaswell wrote:
| Right, these things are still interesting and valuable even
| if not immediately practical for a certain use. Like a regex
| being equivalent to a finite state machine or lots of other
| connections between seemingly disparate concepts in math.
| jimbokun wrote:
| This is just the kind of thing you file away in the back of
| your head as "huh, interesting", that may or may not have a
| practical application down the line. But occasionally the pay
| off for having a different way of thinking about a problem can
| be really big.
|
| For example, Joel Spolsky argued a long time ago that Google
| was able to solve some problems faster than Microsoft because
| their programmers understood functional programming:
|
| https://www.joelonsoftware.com/2005/12/29/the-perils-of-java...
|
| Will this article have a similar payoff for someone someday?
| Hard to say, but it was probably not clear to the CS students
| learning map and reduce it would lead to an elegant solution to
| how to run computations across a massive computing
| infrastructure someday, either.
| dfgdghdf wrote:
| It's particularly weird because most statically-type functional
| languages have discriminated unions as a practical alternative
| to the visitor pattern anyway.
| Gabriel439 wrote:
| Author 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
| jameshart wrote:
| 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.
| Twisol wrote:
| My 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-
| objec...
| skybrian wrote:
| That'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 wrote:
| I'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.
| matt-noonan wrote:
| This 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 wrote:
| Just a heads-up, but sealed classes (basically sum types)
| and proper pattern matching is coming to Java.
| Twisol wrote:
| After many years of not having them ;) I'll be very glad
| to be able to retire this well-used gripe.
| mrkeen wrote:
| We got Streams that don't short-circuit properly and
| Optionals that throw NullPointerExceptions, what creative
| fuck-ups do you reckon we'll get with sum types & pattern
| matching?
| Twisol wrote:
| Shh, you've said the quiet part out loud ;)
| dfgdghdf wrote:
| 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.
| dboreham wrote:
| Is that the same thing as algebraic data types?
| Twisol wrote:
| "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 wrote:
| Ah, 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 wrote:
| Some languages have sealed classes for this reason.
| tsimionescu wrote:
| The 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 wrote:
| 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 wrote:
| 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.
| guerrilla wrote:
| I think you missed the angle of the article. It's just pointing
| out the isomorphism between Church encoding, the visitor
| pattern and GADTs. You wouldn't use anything but GADTs in
| Haskell today, it's just an interesting curiosity unless you're
| actually a type theorist or something.
| layer8 wrote:
| The core essence of the visitor pattern is to implement case
| distinction on sum types in languages that do not natively
| support sum types. Double dispatch is merely the mechanism by
| which the visitor pattern achieves this.
| tsimionescu wrote:
| Double virtual dispatch is the core goal of the visitor
| pattern. If you don't have two families of types and subtypes
| (different subtypes of visitors and different subtypes of
| expressions), there are much simpler alternatives to the
| Visitor Pattern even in something like Java.
|
| In particular, if you have a single closed sum type, function
| overloading is the best way to handle distinctions. If you
| want it to be open, single virtual dispatch is a common
| option.
|
| It's only when you get two different sum types, with one or
| both being open, that you start benefitting from the visitor
| pattern.
| layer8 wrote:
| The benefit is that you can decouple the implementation of
| the operation from the implementation of the sum type. For
| example, a library can provide a sum type, and users of the
| library can implement their own operations on it. This is
| often necessary for proper separation of concerns. For
| example, the sum type may be a domain object, and the
| operations may be database operations, UI operations, or
| other I/O or conversion operations. You don't want the
| domain layer to have dependencies on the database, UI, I/O,
| etc., which it would have if those operations were
| implemented in the sum type itself.
|
| It's exactly the same benefits provided by language-native
| sum types with ADT pattern matching (aside from the visitor
| pattern requiring more boilerplate).
|
| The operation can itself be a polymorphic operation on a
| different type hierarchy or sum type, which is the scenario
| you are thinking of, but that's not necessary for being
| able to benefit from the visitor pattern.
|
| Read the original description of the visitor pattern in the
| GoF book. It's about implementing operations on an existing
| type hierarchy without having to modify the code of that
| type hierarchy.
| tsimionescu wrote:
| To illustrate how to implement what you are describing
| without a visitor pattern if we don't care about
| subtypes: //library code sealed
| class TreeNode{ Object[] children; }
| sealed class LeafNode { int value }
| //application code int sumTree(Object o) {
| if(o instanceof TreeNode) { var tn =
| (TreeNode)o; sum += sumTree(tn); } else
| if (o instanceof LeafNode) { var ln =
| (LeafNode) o; sum += sumTree(ln) ; }
| } int sumTree(TreeNode a) { var sum = 0;
| for (Object o in a.Children) { sum +=
| sumTree(o) ; } return sum; }
| int sumTree(LeafNode ln) { return ln.value;
| }
|
| For some added type safety, we could use a marker
| interface instead of Object, but the code would be
| equivalent. You don't need visitors or ADTs even if
| you're working with Java 1.0 (you could actually write
| this in C pretty easily).
|
| Now, if you start adding actual subtypes to TreeNode and
| LeafNode, this will quickly stop working, especially if
| you want more than one operation.
| [deleted]
| Ericson2314 wrote:
| "double dispatch" is not a problem. It's OO epicycles.
| "Deciding what to do based on the sort of input" is the
| problem.
|
| The point of these realizations not that "oh, just use church
| encoding". Church encoding, like the visor pattern, is annoying
| an obtuse: get a language with pattern marching.
|
| Rather, the point is to show that the theory is legit because
| it shows up even among the work of those ignorant of it. And
| church encoding remains useful theory because sometimes it's
| advantageous to boil everything down to functions.
| skybrian wrote:
| That is changing the problem definition, which may or may not
| be a feasible move.
|
| "Double dispatch" is indeed a problem when the language
| you're allowed to use has to be taken as given, as it usually
| is.
| dragonwriter wrote:
| > "Double dispatch" is indeed a problem when the language
| you're allowed to use has to be taken as given.
|
| No, it's not, at least with most modern real OO languages,
| because most support functional style as well.
|
| It's the low impedance solution course for certain problems
| when you have a preexisting idiomatic code base in some
| languages, though. But that's a different thing than being
| the _problem_.
|
| (Also, whether the language is usually an advance
| constraint rather than a trade-off depends on a lot of
| things, including your role; certainly, polyglot runtimes
| and the ability to link code from different languages are
| common enough that even "must integrate in-process with
| existing code base in language X" is usually not a
| _technical_ constraint that narrows the solution space to
| language X.)
| skybrian wrote:
| We should distinguish between "double dispatch" in the
| abstract and a concrete problem being solved with it. The
| concrete problem often has more constraints, not
| mentioned when talking about it abstractly.
|
| For example, using a different language means that the
| build system needs to support the other language, which
| can significantly complicate the difficulty for users of
| a library compared to a "pure" version written in the
| same language as the rest of the ecosystem. It may also
| limit portability, if the original language and the other
| language you pick don't support the same platforms. This
| isn't a good thing to inflict on users of your library.
|
| To be a bit more concrete about it, suppose you are
| writing code in Rust to target WebAssembly. Pure Rust
| libraries are more likely to work than those written in a
| different language.
|
| There are other ways to avoid this. In Go, you can use
| the "go generate" command to generate Go code from code
| written in another language, and check in the Go code, so
| downstream users of your library don't need any special
| tools. That's probably okay for private dependency on
| code written in another language, but less useful for
| datatypes used in public API's.
|
| Someone talking about OO "epicycles" is ignoring most of
| the constraints that library maintainers face. It seems
| unsympathetic and out of touch.
| Ericson2314 wrote:
| It's fine to justify how we write code based on the code
| we've already written, but that is the very "hammer-
| first" reasoning the original comment was disparaging!
|
| Even if we can't rewrite everything up front, it's used
| to think about the problem at hand from first principles,
| ignoring the constraints of any particular language. From
| the vantage point "double dispatch" will never arise.
| Gabriel439 wrote:
| Author here: it's not changing the problem definition. I
| can confirm that the original motivation for writing the
| post was to show the theoretical underpinnings of the
| visitor pattern, not to encourage people to gratuitously
| use double dispatch.
| jameshart wrote:
| Maybe the fundamental problem isn't double dispatch itself,
| fair.
|
| The fundamental problem is that you need to teach the
| computer how to choose which of a number of computations to
| run depending on two enumerable dimensions, and you need to
| embed that into your program in a way that covers all the
| possibilities, is bug free and maintainable.
|
| Like, I need to be able to add shapes to my program, and
| things I can calculate about shapes to my program, and
| whenever I do so I need to either add all the new
| calculations for my new shape, or add my calculation for
| every existing shape.
|
| That's the essential complexity at the heart of this problem.
|
| Double dispatch is the problem you then get when, in looking
| to solve that problem, you want to express the operations you
| want to run as functions that take every pairwise combination
| of types, and you are at a point in your code where you have
| a couple of objects and need to choose which of those
| functions to run. Like, I have an operation I want to run
| (could be calculate area, could be calculate perimeter), and
| a shape I want to run it on (could be a square, could be a
| circle) and I need the computer to go and run the correct one
| of four possible bits of code for me right now.
|
| This is a double dispatch problem no matter what facilities
| your language has to address it. If your language can pattern
| match on typed tuples you can use pattern matching to
| dispatch to the right piece of code. If not, maybe you need
| to use something like the visitor pattern.
| xaedes wrote:
| Python: import math def
| Circle(x, y, r): return (lambda visitCircle,
| visitRectangle : visitCircle(x, y, r)) def
| Rectangle(x, y, w, h): return (lambda visitCircle,
| visitRectangle : visitRectangle(x, y, w, h)) def
| area(shape): return shape( lambda
| x, y, r : math.pi * r * r, lambda x, y, w, h
| : w * h ) exampleCircle = Circle(2,
| 1.4, 4.5) exampleRectangle = Rectangle(1.3, 3.1, 10.3,
| 7.7) print(area(exampleCircle))
| print(area(exampleRectangle)) # 63.61725123519331
| # 79.31
| mdoms wrote:
| So every shape now has to reference every other shape? If I
| want to add a new shape I not only have to define the shape
| function, def Triangle(a,b,c): return
| (lambda visitCircle, visitRectangle, visitTriangle :
| visitTriangle(a, b, c))
|
| and update the area function, I also need to update every
| existing type like def Rectangle(x, y, w, h):
| return (lambda visitCircle, visitRectangle, visitTriangle :
| visitRectangle(x, y, w, h))
|
| Am I understanding this correctly? How is this a win? What if
| I have a hundred different shapes, now every shape definition
| is just a list of a hundred parameters and hopefully I called
| the correct one in my copy&paste-fest.
| h_anna_h wrote:
| Here you go import math def
| Circle(x, y, r): return (lambda d :
| d['visitCircle'](x, y, r)) def Rectangle(x, y,
| w, h): return (lambda d : d['visitRectangle'](x,
| y, w, h)) def area(shape): return
| shape({ 'visitCircle': lambda x, y, r :
| math.pi * r * r, 'visitRectangle': lambda x,
| y, w, h : w * h }) exampleCircle =
| Circle(2, 1.4, 4.5) exampleRectangle = Rectangle(1.3,
| 3.1, 10.3, 7.7) print(area(exampleCircle))
| print(area(exampleRectangle)) # 63.61725123519331
| # 79.31
| mdoms wrote:
| At this point I have to believe you functional
| programming guys are just taking the piss.
| Twisol wrote:
| That's why we usually group all of these handlers into a
| single Visitor interface. Then you only add one class and
| one extra method to the Visitor, and all the other variants
| stay the same.
|
| You're brushing up against the so-called "expression
| problem", though, where you can choose between adding types
| easily or adding algorithms easily, but not usually both.
| chombier wrote:
| 1. each case of the pattern matching is encoded by a lambda
| (the ones passed to "shape" in function "area")
|
| 2. each possible shape instance is a function that will
| accept these case lambdas, picking the one corresponding to
| it and passing its constructor arguments to it
|
| 3. the constructors ("Circle", "Rectangle") create the shape
| instances
| scaraffe wrote:
| can someone explain how this works? or where I can learn more
| about this.
| ajoseps wrote:
| I think it's best understood if you work backwards from the
| print calls
|
| 1. _print_ is fairly straightforward, prints to stdout what
| is inputted
|
| 2. _def area(shape)_ returns the result of shape call with
| the two lambda parameters representing the area of a circle
| as the first parameter, and the second representing the
| area of a rectangle.
|
| 3. _def Circle(x,y,r)_ & _def Rectangle(x, y, w, h)_ are
| functions which return a lambda that both accepts two
| parameters, _visitCircle_ and _visitRectangle_.
| _visitCircle_ corresponds to the _lambda x, y, r : math.pi
| * r * r_ in _def area(shape)_. _visitRectangle_ corresponds
| to the _lambda x, y, w, h : w *h_ in _def area(shape)_. So
| the _def Circle(x, y, r)_ returns a lambda that takes as
| input these two formulas, but chooses the formula for
| calculating a circle 's area, whereas _def Rectangle(x, y,
| w, h)_ takes as input the same two formulas, but chooses
| the formula for calculating a rectangle 's area.
| [deleted]
| kaba0 wrote:
| This is basically what the blog post explains, though
| without some Haskell knowledge it is probably hard to
| understand. (Sorry if I explain something you already know)
|
| The basic idea is that types can be "recreated" in an
| untyped way with only functions. It is also important to
| note the distinction between sum types and product types. A
| sum type is basically a (disjunct) set of types, for
| example Shape is a sum type on Rectangles and Circles (in
| this case only these things are considered the available
| shapes and every shape is either one or another). A product
| type is more straight-forward, basically any struct/class
| with multiple fields is an example, for example Circle is a
| product type with a radius and an x and y coord of its
| centerpoint.
|
| For example here the two-ary methods represents the two
| types: return (lambda visitCircle, visitRectangle :
| visitCircle(x, y, r)) Is going to represent circles, by
| awaiting two functions that work as constructors, and
| dispatching to the first one. Rectangle is similarly
| defined, only dispatching to the second function.
|
| The part that corresponds to pattern matching/the second
| dispatch is basically where we would like to use our sum-
| types (either a circle or a rectangle). It provides both
| implementation in the form of a pair of functions, the
| first one corresponds to the circle's area-definition the
| second to the rectangle's.
|
| The "magic" happens at calling area(exampleSomething). The
| area function will return as seen a pair of functions,
| basically every possible implementation on the possible
| types. Now that pair of functions will go to either a
| Circle 'constructor' function or a Rectangle one, and as we
| defined those, it will use up respectively the first or the
| second function in the pair based on its "type". Also note
| that the correct arity of parameters will be passed to the
| selected function.
| [deleted]
| magicalhippo wrote:
| 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?
| chriswarbo wrote:
| 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#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 wrote:
| 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.
| scatters wrote:
| 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.
| dfgdghdf wrote:
| Is C++ cheating since it has such a powerful type-system? I
| would like to see an attempt in Java.
| matheusmoreira wrote:
| Whoa! C++ has become an almost completely different language
| since I learned it over 10 years ago...
| jfengel wrote:
| That was _precisely_ what I was going to say. I don 't
| recognize any of that.
| pjmlp wrote:
| Which could be done with a little help from std::any, just as
| info for others.
| _old_dude_ wrote:
| 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.
| dfgdghdf wrote:
| This might get messy once you need hashCode and equals
| _old_dude_ wrote:
| You can keep the Circle and Rectangle as class (record
| here) and only see them as Shape when you want to do the
| double dispatch of the visitor. interface
| Shape { record Circle(int x, int w, int r) {}
| record Rectangle(int x, int y, int w, int h) {}
| <T> T apply(Function<Circle, T> _circle,
| Function<Rectangle, T> _rectangle); static <T>
| Shape shape(Circle circle) { return new Shape() {
| @Override public <T> T apply(Function<Circle,
| T> _circle, Function<Rectangle, T> _rectangle) {
| return _circle.apply(circle); } };
| } static <T> Shape shape(Rectangle rectangle) {
| return new Shape() { @Override
| public <T> T apply(Function<Circle, T> _circle,
| Function<Rectangle, T> _rectangle) { return
| _rectangle.apply(rectangle); } };
| } static double area(Shape shape) {
| return shape.apply( circle -> Math.PI *
| circle.r * circle.r, rectangle -> 1. *
| rectangle.w * rectangle.h ); }
| static void main(String[] args) { var aCircle =
| new Circle(2, 1, 4); var aRectangle = new
| Rectangle(1, 3, 10, 7);
| System.out.println(area(shape(aCircle)));
| System.out.println(area(shape(aRectangle))); }
| }
| Twisol wrote:
| 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)); }
| }
| _old_dude_ wrote:
| > The downside is that Java doesn't let you implement
| generic methods with lambdas ...
|
| yes, that exactly why i've chosen to make the type
| parametric and not the method apply, but you're right that
| the classical visitor pattern uses a polymorphic method
| (accept) not a polymorphic class.
| Twisol wrote:
| Sure. Then, if you're set on using lambdas, I'd recommend
| this, to at least take away the ability to choose <T>
| from the caller. static Shape<?>
| Circle(int x, int y, int r) { return (circle,
| rectangle) -> circle.apply(x, y, r); }
| static Shape<?> Rectangle(int x, int y, int w, int h) {
| return (circle, rectangle) -> rectangle.apply(x, y, w,
| h); }
| gampleman wrote:
| 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.
| monzee wrote:
| 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 }); }
| magicalhippo wrote:
| Thanks, that helps a lot!
|
| Never used TypeScript either (I feel like such a Luddite
| these days) but this is perfectly understandable.
| DougBTX wrote:
| 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 wrote:
| 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 wrote:
| > 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 wrote:
| 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()
| bob1029 wrote:
| 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-match...
| ts0000 wrote:
| 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 wrote:
| 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.
| ts0000 wrote:
| Agree, I intentionally didn't change the names to mirror
| the other examples in sibling comments as I meant to focus
| on the "named parameters" bit.
| Twisol wrote:
| > 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.
| jameshart wrote:
| Nah, the Circle function takes an instance of Circle and
| returns a Shape. It's not a constructor of circles.
|
| The 'exampleCircle' is not an instance of Circle, it's an
| instance of Shape.
|
| I like the 'onCircle' naming though.
| Twisol wrote:
| You're speaking at the level of the code, while I'm
| speaking at the level of the domain. Neither of us are
| wrong, but we're talking past each other.
|
| The Shape class itself is formally the sum of Circle and
| Rectangle -- you can think of this as a "prefer
| composition over inheritance" principle, but it's still a
| way of relating Circle to Shape. In particular, the
| Circle and Rectangle factories are canonical injections
| of these two classes into the Shape class. The naming of
| the factories is a little suspect, but if the only use of
| Circle and Rectangle is meant to be in the context of
| Shape, it mostly flies.
|
| > Nah
|
| This came across as excessively dismissive.
| Twisol wrote:
| 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
| // 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));
| } } } }
| injidup wrote:
| 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
| [deleted]
| jgwil2 wrote:
| 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/
| smlckz wrote:
| Enjoy this in Lua (for linked list):
| https://rextester.com/XGNR33292
| guerrilla wrote:
| 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.
| johndoe42377 wrote:
| 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 wrote:
| > 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 wrote:
| 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 wrote:
| 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.
| h_anna_h wrote:
| What is the point of doing forall T but not forall A and B?
| Twisol wrote:
| A and B are free to be chosen by a producer of the generic
| Sum type. However, T can be chosen "late", by a _consumer_
| of Sum; a value of type Sum A B must work for any T you
| decide to use down the line.
|
| If it helps, the equivalent Java signature is:
| interface Sum<A, B> { <T> T visit(Function<A, T>
| onA, Function<B, T> onB); }
|
| Hopefully this makes it more clear that A and B are fixed
| when you receive a value of type Sum A B, but you get to
| pick a T when consuming that value.
| johndoe42377 wrote:
| Oh, I forgot to mention, that "enzymes are proteins" is
| isomorphic (lol) to "procedures are list structures" (or "code
| is data") which explains the miracle of Lisp and it's macros
| and connects Lisp to life itself, and justifies why MIT folks
| ware so fascinated with it.
| [deleted]
| delibes wrote:
| 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 wrote:
| 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- wrote:
| 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/
| h_anna_h wrote:
| I have noticed a lot of random hate against Haskell devs
| specifically, see https://twitter.com/catachresthetic/statu
| s/13106325659556044... for another example.
| mattxxx wrote:
| Here's a better explanation of the visitor pattern than
| Wikipedia: https://sourcemaking.com/design_patterns/visitor
|
| ^ Helped me understand why-on-earth anyone would introduce this
| pattern
| DarkWiiPlayer wrote:
| Reading that just reminded me of why I hate OOP so much. It's
| confusing.
| platz wrote:
| 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.
___________________________________________________________________
(page generated 2021-02-04 23:02 UTC)