3 ms·

I really don't understand why more languages don't include tagged unions. For one, even in C, most uses of unions fall into two kinds. There are unions that em

by tikhonj 14y ago

I really don't understand why more languages don't include tagged unions. For one, even in C, most uses of unions fall into two kinds. There are unions that emulate sub-typing and unions that have a manually implemented tag system. Basically, C programmers have to work around the language's deficiencies manually and hope to avoid errors--nothing surprising, I suppose. More importantly, tagged unions simply make more sense. They are the mathematical dual of structs, which means that having both exposes a natural symmetry in language design. And, just like in physics, symmetry almost always means you're on the right track! And, of course, once you have tagged unions and structs, you've added algebraic data types to your language. Now just throw in pattern matching and you have a basic system that is both safer and more expressive than the common alternatives. What's not to like? This is one of the many reasons I'm very excited about Rust and not excited at all about Go.

tobinfricke 13y ago
In what way are tagged unions "the mathematical dual of structs"?
- jules 13y ago
  In this context, the mathematical dual of something is the consumer of the something. So "tagged unions are the mathematical dual of structs" means that a tagged union consumer is isomorphic to a struct. If you have a tagged union consisting of the elements Foo(int), Bar(char) and Baz(int,string) then to consume such a thing you have to specify what to do with a Foo, what to do with a Bar and what to do with a Baz. You can specify this by giving a struct with a function that consumes Foos, a function that consumes Bars and a function that consumes Bazs. In ML syntax we have: type Qux = Foo of int | Bar of char | Baz of int * string type QuxDual = Consumer of (int -> result) * (char -> result) * (char * string -> result) Now if you have a QuxDual, you can consume a Qux by picking the appropriate function depending on what kind of Qux you get, and then calling that function on the data inside that Qux. You can see that because of these `result` types duality is not particularly nice in languages based on functions. It's nicer in languages based on processes or continuations, because they have a direct notion of a consumer of something. A consumer of an int is an `int -> result` function but in languages based on processes we can directly take a process that takes an int as an input or a continuation C(int). So in those kind of languages we don't have extra result types hanging around.
- burntsushi 13y ago
  I'm not the GP, but I suspect it's because structs are product types and unions are sum types.
- tikhonj 13y ago
  Structs are an example of a "universal construction" called a product. Other examples of this include cartesian products, logical AND and join in a lattice (e.g. getting the least upper bound of two partially ordered elements). For types, this is defined exclusively based on the functions it has. Roughly speaking, the product of two types A and B is the "simplest" structure that has a function to A and a function to B--that is, if you imagine a nice diagram, there is an arrow from A × B to A and an arrow from A × B to B. For structs, these two functions are just field accesses. The notion of "simplest" here essentially just means that given any other object C with these criteria--that is, a function to A and a function to B--there has to also exist a function C to A × B. I'm skipping some details, but you should get the general gist. The notion of duality just means taking the above diagram and flipping all the arrows. So the co-product of two types A and B is the "simplest" type A + B that has a function from A to A + B and a function from B to A + B. These functions correspond to tagging elements from A or B as appropriate. For logical AND, the dual is logical OR. For getting the least upper bound, the dual is getting the greatest lower bound. And, following that same logic, for structs the dual is tagged unions. I hope that made sense. This is the sort of thing that's much easier to describe interactively with a whiteboard instead of trying to just use ASCII--it practically begs me to draw some diagrams, but my ASCII art is simply not up to par :(.
jules 13y ago
Many languages have type safe tagged unions with pattern matching. It's called the visitor pattern. The syntax is atrocious though.

by tikhonj 14y ago

tobinfricke 13y ago

In what way are tagged unions "the mathematical dual of structs"?

jules 13y ago
In this context, the mathematical dual of something is the consumer of the something. So "tagged unions are the mathematical dual of structs" means that a tagged union consumer is isomorphic to a struct. If you have a tagged union consisting of the elements Foo(int), Bar(char) and Baz(int,string) then to consume such a thing you have to specify what to do with a Foo, what to do with a Bar and what to do with a Baz. You can specify this by giving a struct with a function that consumes Foos, a function that consumes Bars and a function that consumes Bazs. In ML syntax we have: type Qux = Foo of int | Bar of char | Baz of int * string type QuxDual = Consumer of (int -> result) * (char -> result) * (char * string -> result) Now if you have a QuxDual, you can consume a Qux by picking the appropriate function depending on what kind of Qux you get, and then calling that function on the data inside that Qux. You can see that because of these `result` types duality is not particularly nice in languages based on functions. It's nicer in languages based on processes or continuations, because they have a direct notion of a consumer of something. A consumer of an int is an `int -> result` function but in languages based on processes we can directly take a process that takes an int as an input or a continuation C(int). So in those kind of languages we don't have extra result types hanging around.
burntsushi 13y ago
I'm not the GP, but I suspect it's because structs are product types and unions are sum types.
tikhonj 13y ago
Structs are an example of a "universal construction" called a product. Other examples of this include cartesian products, logical AND and join in a lattice (e.g. getting the least upper bound of two partially ordered elements). For types, this is defined exclusively based on the functions it has. Roughly speaking, the product of two types A and B is the "simplest" structure that has a function to A and a function to B--that is, if you imagine a nice diagram, there is an arrow from A × B to A and an arrow from A × B to B. For structs, these two functions are just field accesses. The notion of "simplest" here essentially just means that given any other object C with these criteria--that is, a function to A and a function to B--there has to also exist a function C to A × B. I'm skipping some details, but you should get the general gist. The notion of duality just means taking the above diagram and flipping all the arrows. So the co-product of two types A and B is the "simplest" type A + B that has a function from A to A + B and a function from B to A + B. These functions correspond to tagging elements from A or B as appropriate. For logical AND, the dual is logical OR. For getting the least upper bound, the dual is getting the greatest lower bound. And, following that same logic, for structs the dual is tagged unions. I hope that made sense. This is the sort of thing that's much easier to describe interactively with a whiteboard instead of trying to just use ASCII--it practically begs me to draw some diagrams, but my ASCII art is simply not up to par :(.

jules 13y ago

Many languages have type safe tagged unions with pattern matching. It's called the visitor pattern. The syntax is atrocious though.