Re:Algebraic Data Types
by eru on Thursday July 31, 2014 @04:15AM
(#8112983)
ADTs are a bit like garbage collection: they originated in functional languages, they provide huge productivity gains, and they are (in theory) very easy to prop onto any kind of language. You can imagine a variant of C that has ADTs---they'd just be called tagged unions.
[ Parent
| on HN ]
ADTs and pattern matching go together. Having tagged unions is awful without a good way to discriminate upon them.
Switch statements are ok but not typesafe since nothing prevents you from desynchronizing the tag and data
If you think of ADT definitions as defining how you construct types then you get a natural method for destructing them or using them automatically. This could be pattern matching or it could be explicit functions
More concretely, even without pattern matching, so long as, for instance, these three functions are all defined
pair : a -> b -> Pair a b
pi1 : Pair a b -> a
pi2 : Pair a b -> b
C already has product types, so it's sums that are more interesting, and indeed the destructors for sums are harder in C. The constructors
in1 : a -> Sum a b
in2 : b -> Sum a b
sum : Sum a b -> (a -> c) -> (b -> c) -> c
There's a difference between "having a destructor" and having a first-class representation of it. For instance, basically every language has a destructor for booleans—it's just if.
The trick is that unless you have first-class functions you probably cannot reify such a destructor. It always just lives in your syntax.
On the flip side, that's really what it means for a language to, say, lack sum types. It's not that the language doesn't have the ability to have choice, it's that it lacks the ability to represent choice in data. In other words, you probably can eliminate choice using if/switch/case/what-have-you but you can't construct it.
Right. I interpreted your previous comment as meaning that you don't need pattern matching because you can just used the (reified) destructor. Conversely, you can avoid the higher-order destructor using pattern matching.
Yep! They are "the same".