5 ms·
Functional Pearl: Enumerating the Rationals [pdf]
- mlonkibjuyhv 8y agoThis looks very weird in my pdf-viewer.
- Stratoscope 8y agoTry a different PDF viewer? It looks fine here in Chrome and Adobe Reader, both on Windows 10.
- jolmg 8y agoAlso looks fine in Firefox in Linux
- fmap 8y agoThis 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...
- lpage 8y agoRelated: the Farey sequence [1]. Well worth investigating if you found this paper interesting. [1] https://en.wikipedia.org/wiki/Farey_sequence https://en.wikipedia.org/wiki/Farey_sequence
- user2994cb 8y agoAn 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/RecountingRationalsTwice.pdf http://www.cs.nott.ac.uk/~psarb2/MPC/RecountingRationalsTwic...