Hacker Newsnew | 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.

https://www.coursera.org/course/ac

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: http://158.130.69.163/~byorgey/pub/species-pearl.pdf

-----




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

Search: