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

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 very close. (In analytic combinatorics, the goal is to count the objects in various combinatorial classes.) Part 2 of the linked-to article, for example, shows that the list data type data List a = Nil | Cons a (List a) can be mapped to the algebraic form L(a) = 1 + a * L(a), having the solution L(a) = 1 / (1 - a). In analytic combinatorics, the sequence operator F(a), representing sequences of the underlying class a, is given F(a) = 1 / (1 - f(a)) where f(a) is the ordinary generating function (OGF) representing the class a. 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. [1] http://algo.inria.fr/flajolet/Publications/book.pdf http://algo.inria.fr/flajolet/Publications/book.pdf