6 ms·

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),

by Twisol 6y ago

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-object-algebras-to-finally-tagless-interpreters-2/ https://oleksandrmanzyuk.wordpress.com/2014/06/18/from-objec...

matt-noonan 6y ago
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 6y ago
Just a heads-up, but sealed classes (basically sum types) and proper pattern matching is coming to Java.
- Twisol 6y ago
  After many years of not having them ;) I'll be very glad to be able to retire this well-used gripe.
  - mrkeen 6y ago
    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 6y ago
      Shh, you've said the quiet part out loud ;)
skybrian 6y ago
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 6y ago
  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.
  - skybrian 6y ago
    I meant that you wouldn't use a Church encoding workaround for a visitor pattern. (That's what you seemed to mean by "here's a way to encode them precisely.") Instead, you'd use the visitor pattern in the normal way. So the Church encoding workaround is useful in neither Haskell nor Java.
    - Twisol 6y ago
      The point of the original article is that the Visitor pattern is the Church encoding of sum types. It sounds like you see a stronger difference between what the article describes and what I understand the Visitor pattern to be. There might be light differences in how you organize various elements (such as grouping all the handlers into a single interface or taking them as individual parameters), but I see those as all within the same overall Visitor aegis. The core of the Visitor pattern is a CPS transform, where you provide the value the code to run "next". Because this puts the sum type on the input side instead of the output side, you can distribute the types and get a pair of functions instead of a sum of values. Is there another difference I'm not accounting for?
      - skybrian 6y ago

by Twisol 6y ago

matt-noonan 6y ago

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 6y ago

Just a heads-up, but sealed classes (basically sum types) and proper pattern matching is coming to Java.

Twisol 6y ago
After many years of not having them ;) I'll be very glad to be able to retire this well-used gripe.
- mrkeen 6y ago
  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 6y ago
    Shh, you've said the quiet part out loud ;)

skybrian 6y ago

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 6y ago
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.
- skybrian 6y ago
  I meant that you wouldn't use a Church encoding workaround for a visitor pattern. (That's what you seemed to mean by "here's a way to encode them precisely.") Instead, you'd use the visitor pattern in the normal way. So the Church encoding workaround is useful in neither Haskell nor Java.
  - Twisol 6y ago
    The point of the original article is that the Visitor pattern is the Church encoding of sum types. It sounds like you see a stronger difference between what the article describes and what I understand the Visitor pattern to be. There might be light differences in how you organize various elements (such as grouping all the handlers into a single interface or taking them as individual parameters), but I see those as all within the same overall Visitor aegis. The core of the Visitor pattern is a CPS transform, where you provide the value the code to run "next". Because this puts the sum type on the input side instead of the output side, you can distribute the types and get a pair of functions instead of a sum of values. Is there another difference I'm not accounting for?
    - skybrian 6y ago