3 ms·

Author of the blog post here. It's amusing to see this submitted by Don Stewart, since it was his explanation[0] of algebraic data types that first made them "c

Author of the blog post here. It's amusing to see this submitted by Don Stewart, since it was his explanation[0] of algebraic data types that first made them "click" for me! I think I forgot to mention him in this post, but I remembered in the talk[1]. If anyone's interested in this and where else it might go, I recommend read Don's SO answer[0], this SO question and the related answers[2] and these papers [3,4] on derivatives and dissections by Conor McBride. There are also several good blog posts[5] and a paper[6] by Brent Yorgey on the topic of combinatorial species, and of course Dan Piponi's blog[7] is a treasure trove of interesting insights at the intersection of math, physics and computer science. [0] http://stackoverflow.com/a/5917133/546084 http://stackoverflow.com/a/5917133/546084 [1] http://www.youtube.com/watch?v=YScIPA8RbVE http://www.youtube.com/watch?v=YScIPA8RbVE (shitty audio for the first minute or 2 - it gets better). [2] http://stackoverflow.com/questions/9190352/abusing-the-algebra-of-algebraic-data-types-why-does-this-work http://stackoverflow.com/questions/9190352/abusing-the-algeb... [3] http://strictlypositive.org/diff.pdf http://strictlypositive.org/diff.pdf [4] https://personal.cis.strath.ac.uk/conor.mcbride/Dissect.pdf https://personal.cis.strath.ac.uk/conor.mcbride/Dissect.pdf [5] http://byorgey.wordpress.com/ http://byorgey.wordpress.com/ [6] http://www.cis.upenn.edu/~byorgey/papers/species-pearl.pdf http://www.cis.upenn.edu/~byorgey/papers/species-pearl.pdf [7] http://blog.sigfpe.com/2010/08/divided-differences-and-tomography-of.html http://blog.sigfpe.com/2010/08/divided-differences-and-tomog... Edit: It should go without saying, but because a few people last time around seemed to think I was trying to pass this off as my own ideas, let me state that there is nothing original in this blog post. It's a repackaging of the ideas and work of lots of other people, all of whom are way smarter than I am.

brudgers 13y ago
As I said earlier, great article. Since you're here, wanted to let you know there's a typo: Addition In principle we could [create? make? construct?] types corresponding to 3, 4, 5 and so on. Thought you might want to fix it. Thanks, again.
Ixiaus 13y ago
Yes, this is a great article series, thank you for it!! (I only had a vague intuition of why Either was a sum type or why pairs are a multiplication type)
ggchappell 13y ago
A very nice article. A fun fact: 0^0 is not undefined here. In fact, a^0 = 1 for all a. One suggestion: say "equivalence" of types, rather than "equality". (You do this, once.)
joe_the_user 13y ago
I don't mean to be negative, it's probably the material as much as you but as I read the article, I find a voice repeating "what is the point, where is this leading, why, why?". I mean, as I read the article, my impression is "here's verbose syntax that does describe types but whose relation to the tasks of an ordinary programming language, to getting things done is left unexplained for too long for attention span, if it is explained at all". And I'm fairly mathematically sophisticated (MA a while back with some effort to keep current). It seems like the constructions "thrown on the floor" everything that happens in the creation of a type. But I can't understand what that does except make simple operations look like a giant mess. I would add that the stack overflow mentions that the construction is a way to construct an algebraic with "polymorphic parameterization". IE, Haskel uses the laws of algebra and some supplied primitives (AddL AddR, which you mention but don't define!)to calculate A + B. Perhaps if you make that explicit, the article wouldn't have the "floating in the clouds and never coming down" quality that it has for me now.
- ekidd 13y ago
  The payoff is in part 3, here, where crntaylor explains how to take the derivative(!) of a type: http://chris-taylor.github.io/blog/2013/02/13/the-algebra-of-algebraic-data-types-part-iii/ http://chris-taylor.github.io/blog/2013/02/13/the-algebra-of... You can find a somewhat more mathematical explanation here, with explanations of why this is useful: http://pavpanchekha.com/blog/zippers/derivative.html http://pavpanchekha.com/blog/zippers/derivative.html The most obvious use for derivative types is the automated creation of "zipper" types for functional data structures. Among other uses, zipper types make certain purely functional data structures much more efficient. This is important both for Haskell and ML programmers, and also in situations where you need to leave older versions of a data structure intact, such as when implementing rollback or creating append-only file formats.
- kenko 13y ago
  Aside from the practical interest in defining zippers as noted in another response, isn't it enough that there be this interesting and (by many, anyway) unsuspected correspondence, that holds fairly deep down? I mean---taking the Taylor series of a type! After all, we are told that "anything that gratifies one's intellectual curiosity" is suitable for an HN submission, no?

brudgers 13y ago

As I said earlier, great article. Since you're here, wanted to let you know there's a typo: Addition In principle we could [create? make? construct?] types corresponding to 3, 4, 5 and so on. Thought you might want to fix it. Thanks, again.

Ixiaus 13y ago

Yes, this is a great article series, thank you for it!! (I only had a vague intuition of why Either was a sum type or why pairs are a multiplication type)

ggchappell 13y ago

A very nice article. A fun fact: 0^0 is not undefined here. In fact, a^0 = 1 for all a. One suggestion: say "equivalence" of types, rather than "equality". (You do this, once.)

joe_the_user 13y ago

I don't mean to be negative, it's probably the material as much as you but as I read the article, I find a voice repeating "what is the point, where is this leading, why, why?". I mean, as I read the article, my impression is "here's verbose syntax that does describe types but whose relation to the tasks of an ordinary programming language, to getting things done is left unexplained for too long for attention span, if it is explained at all". And I'm fairly mathematically sophisticated (MA a while back with some effort to keep current). It seems like the constructions "thrown on the floor" everything that happens in the creation of a type. But I can't understand what that does except make simple operations look like a giant mess. I would add that the stack overflow mentions that the construction is a way to construct an algebraic with "polymorphic parameterization". IE, Haskel uses the laws of algebra and some supplied primitives (AddL AddR, which you mention but don't define!)to calculate A + B. Perhaps if you make that explicit, the article wouldn't have the "floating in the clouds and never coming down" quality that it has for me now.

ekidd 13y ago
The payoff is in part 3, here, where crntaylor explains how to take the derivative(!) of a type: http://chris-taylor.github.io/blog/2013/02/13/the-algebra-of-algebraic-data-types-part-iii/ http://chris-taylor.github.io/blog/2013/02/13/the-algebra-of... You can find a somewhat more mathematical explanation here, with explanations of why this is useful: http://pavpanchekha.com/blog/zippers/derivative.html http://pavpanchekha.com/blog/zippers/derivative.html The most obvious use for derivative types is the automated creation of "zipper" types for functional data structures. Among other uses, zipper types make certain purely functional data structures much more efficient. This is important both for Haskell and ML programmers, and also in situations where you need to leave older versions of a data structure intact, such as when implementing rollback or creating append-only file formats.
kenko 13y ago
Aside from the practical interest in defining zippers as noted in another response, isn't it enough that there be this interesting and (by many, anyway) unsuspected correspondence, that holds fairly deep down? I mean---taking the Taylor series of a type! After all, we are told that "anything that gratifies one's intellectual curiosity" is suitable for an HN submission, no?