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].<p>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.<p>[0] <a href="http://stackoverflow.com/a/5917133/546084" rel="nofollow">http://stackoverflow.com/a/5917133/546084</a><p>[1] <a href="http://www.youtube.com/watch?v=YScIPA8RbVE" rel="nofollow">http://www.youtube.com/watch?v=YScIPA8RbVE</a> (shitty audio for the first minute or 2 - it gets better).<p>[2] <a href="http://stackoverflow.com/questions/9190352/abusing-the-algebra-of-algebraic-data-types-why-does-this-work" rel="nofollow">http://stackoverflow.com/questions/9190352/abusing-the-algeb...</a><p>[3] <a href="http://strictlypositive.org/diff.pdf" rel="nofollow">http://strictlypositive.org/diff.pdf</a><p>[4] <a href="https://personal.cis.strath.ac.uk/conor.mcbride/Dissect.pdf" rel="nofollow">https://personal.cis.strath.ac.uk/conor.mcbride/Dissect.pdf</a>
[5] <a href="http://byorgey.wordpress.com/" rel="nofollow">http://byorgey.wordpress.com/</a><p>[6] <a href="http://www.cis.upenn.edu/~byorgey/papers/species-pearl.pdf" rel="nofollow">http://www.cis.upenn.edu/~byorgey/papers/species-pearl.pdf</a><p>[7] <a href="http://blog.sigfpe.com/2010/08/divided-differences-and-tomography-of.html" rel="nofollow">http://blog.sigfpe.com/2010/08/divided-differences-and-tomog...</a><p>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 <i>nothing</i> 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.
If you find this way of looking at of algebraic data types strange, or want to understand why it is sound, pick up a textbook on analytic combinatorics (a great one is free [1]) because the parallels are <i>very</i> close. (In analytic combinatorics, the goal is to count the objects in various combinatorial classes.)<p>Part 2 of the linked-to article, for example, shows that the list data type<p><pre><code> data List a = Nil | Cons a (List a)
</code></pre>
can be mapped to the algebraic form<p><pre><code> L(a) = 1 + a * L(a),
</code></pre>
having the solution<p><pre><code> L(a) = 1 / (1 - a).
</code></pre>
In analytic combinatorics, the sequence operator <i>F</i>(<i>a</i>), representing sequences of the underlying class <i>a</i>, is given<p><pre><code> F(a) = 1 / (1 - f(a))
</code></pre>
where <i>f</i>(<i>a</i>) is the ordinary generating function (OGF) representing the class <i>a</i>. It's basically the same as the list data type's representation, which is what we ought to expect since a list is just a sequence.<p>[1] <a href="http://algo.inria.fr/flajolet/Publications/book.pdf" rel="nofollow">http://algo.inria.fr/flajolet/Publications/book.pdf</a>
For me, this was a great article. I deepened my admittedly limited understanding of algebra, and picked up a little of the flavor of Haskell in the process.<p>"Every little bit helps," said the old lady as she pissed in the ocean. I now own a little less dumbass.
The idea that types are the same because the cardinalities of their sets of values are the same is weird. So my type for the days of the week is "equal" to my enumeration of the Seven Dwarves, and the sum of Maybe Bool and Bool->Bool? How is that a useful definition?