The Algebra of Data and the Calculus of Mutation
blog.lab49.com
The Algebra of Data and the Calculus of Mutation
1–10 of 11 posts
Re: The Algebra of Data and the Calculus of Mutation
#2I didn't get the + operation on types until he compared it to C's union. I don't know why he didn't appeal to the logical operations "and" and "or" for * and +, because that's what finally made them click and be consistent for me. For example, you can read int * int as "A type with an int and an int," and you can read int + int as "A type with an int on the left or an int on the right."
The links to the papers by Conor McBride are broken, but you can find them here: http://strictlypositive.org/publications.html
Re: The Algebra of Data and the Calculus of Mutation
#3I didn't get the + operation on types until he compared it to C's union. I don't know why he didn't appeal to the logical operations "and" and "or" for * and +, because that's what finally made them click and be consistent for me. For example, you can read int * int as "A type with an int and an int," and you can read int + int as "A type with an int on the left or an int on the right." The links to the papers by Con…
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
#4I didn't get the + operation on types until he compared it to C's union. I don't know why he didn't appeal to the logical operations "and" and "or" for * and +, because that's what finally made them click and be consistent for me. For example, you can read int * int as "A type with an int and an int," and you can read int + int as "A type with an int on the left or an int on the right." The links to the papers by Con…
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
#5I didn't get the + operation on types until he compared it to C's union. I don't know why he didn't appeal to the logical operations "and" and "or" for * and +, because that's what finally made them click and be consistent for me. For example, you can read int * int as "A type with an int and an int," and you can read int + int as "A type with an int on the left or an int on the right." The links to the papers by Con…
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.
"+" 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
#6I didn't get the + operation on types until he compared it to C's union. I don't know why he didn't appeal to the logical operations "and" and "or" for * and +, because that's what finally made them click and be consistent for me. For example, you can read int * int as "A type with an int and an int," and you can read int + int as "A type with an int on the left or an int on the right." The links to the papers by Con…
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
#7Earlier quoted context omitted.
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.
"+" 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.
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.)
Re: The Algebra of Data and the Calculus of Mutation
#8This is a great explanation of algebraic datatypes!
The notion of one-hole context, its connection to differentiation, and its application to zippers is really interesting stuff. Another (much more detailed) discussion of it can be found here: http://en.wikibooks.org/wiki/Haskell/Zippers
Re: The Algebra of Data and the Calculus of Mutation
#9Further explanations on the "Mu" thing and its relation with catamorphism[0](a fold[1] that works on every datatype): http://stackoverflow.com/questions/4434292/catamorphism-and-... and http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/acmmp...
[0]: https://secure.wikimedia.org/wikipedia/en/wiki/Catamorphism
[1]: https://secure.wikimedia.org/wikipedia/en/wiki/Fold_%28highe...
Re: The Algebra of Data and the Calculus of Mutation
#10This is a great explanation of algebraic datatypes! The notion of one-hole context, its connection to differentiation, and its application to zippers is really interesting stuff. Another (much more detailed) discussion of it can be found here: http://en.wikibooks.org/wiki/Haskell/Zippers
Agreed, the "if this looks like a derivative it's because it is" punchline made my jaw drop. I never expected to see calculus show up when discussing ADT's and mutation.
The notion is so contrary to the way I'm used to thinking about programming and yet so appropriate given that mutation is change and a derivative describes the rate of change.
I want some more!