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.

 Robert Sedgewick also has created a Coursera course for analytic combinatorics where he develops some of the ideas in his book.https://www.coursera.org/course/acThe topic is incredible. Basically all the math you learn in Undergraduate mathematics gets pulled in to solve counting problems and perform algorithm analysis. It's inspiring. :)
 there is also the introductory article "Species and Functors and Types, Oh My!" which explores some of these ideas applied to examples from Haskell: http://158.130.69.163/~byorgey/pub/species-pearl.pdf

Applications are open for YC Winter 2018

Search: