Hacker News new | comments | show | ask | jobs | submit login

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

Robert Sedgewick also has created a Coursera course for analytic combinatorics where he develops some of the ideas in his book.


The 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:

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact