Re:The Algebra of Data and the Calculus of Mutation
by tel on Wednesday April 27, 2011 @01:25PM
(#2490270)
There's a parallelism all the way through (Tuple, Either), (*, +), (and, or), and (intersect, union) depending on the language you want to use and the underlying objects they're operating on.
Each is a (blurry) picture of algebraic ring structure.
Re:The Algebra of Data and the Calculus of Mutation
by munificent on Wednesday April 27, 2011 @12:47PM
(#2490091)
It's important to remember that + is a little different from a C union in that it's automatically tagged, which C unions are not. If you have int+int in a functional language, you always know which arm was chosen. If you have a union of two ints in C you have to add a third boolean field yourself to keep track of which one is active.
Re:The Algebra of Data and the Calculus of Mutation
by joeyespo on Wednesday April 27, 2011 @12:14PM
(#2489973)
Yeah it's definitely helpful to think of it that way.
I usually relate it to sets. Types are sets of possible objects, "+" indicates set-based union, and "*" is just the Cartesian product of the types.
Re:The Algebra of Data and the Calculus of Mutation
by munificent on Wednesday April 27, 2011 @12:48PM
(#2490095)
"+" isn't set union. If it was, int+int would just be int. The extra tag distinguishes it. Raw unions in C are like set union though.
Re:The Algebra of Data and the Calculus of Mutation
by joeyespo on Wednesday April 27, 2011 @02:52PM
(#2490615)
Right, it's a tagged union. I mean conceptually. You still end up with the same domain of objects as a union. The tag just tells you which domain you're object is in. (Or which side rather, since the domains can intersect.)
The links to the papers by Conor McBride are broken, but you can find them here: http://strictlypositive.org/publications.html