3 ms·

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

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 :(.