Functional Pearl: Enumerating the Rationals [pdf]

This is a really wonderful paper. For several years now we have been teaching a seminar about functional programming every year, where students present functional pearls (for the most part). This paper has been a staple of the seminar and I never got tired of seeing it presented or explaining it to people.

There are two things that could be improved about the paper in my opinion, but they are minor. First, the proof of the formula for the next sibling in the Calkin-Wilf tree (Figure 3 in the paper) becomes much more obvious when you express x and x_0' in terms of y instead of expressing y and x_0' in terms of x. Second, the Stern-Brocot tree is a bit of a detour without any real payoff. It's just as easy to go from the traced gcd directly to the Calkin-Wilf tree.

The latter part is a bit of a shame, since there are plenty of things that could be said about the Stern-Brocot tree (see e.g. Concrete Mathematics by Graham, Knuth, and Patashnik), but then it would have to be moved to the end of the paper. The paper doesn't do this in order to have the nice closed form solution for the titular enumeration at the end instead...

Related: the Farey sequence [1]. Well worth investigating if you found this paper interesting.

[1] https://en.wikipedia.org/wiki/Farey_sequence

An interesting (later) paper about generating the Stern-Brocot tree and the Calkin-Wilf tree simultaneously from a sequence of 2x2 matrices: http://www.cs.nott.ac.uk/~psarb2/MPC/RecountingRationalsTwic...

This looks very weird in my pdf-viewer.