Re: Make-rational-number-generator

[Alex Shinn <alexshinn@xxxxxxxxx>]

On Sun, Feb 8, 2015 at 10:17 AM, John Cowan <cowan@xxxxxxxxxxxxxxxx> wrote:

Here's something I found too late to put it into the first draft:

(make-rational-number-generator [ q ] )

Returns a generator of rational numbers starting with q (default 0)
according to the following recurrence:

    x' = (/ 1 (+ (* 2 (truncate x)) 1 (- x)))

It will generate all exact rationals once and only once in in the infinite
sequence 0, 1/2, 2, 1/3, 3/2, 3, 1/4, 4/3, 3/5, 5/2, 2/5, 3/4, 4, ...

Cute.  Proof?  (you missed 1 after 0)

You could also use a more intuitive diagonalization order, at the

cost of some busy work to filter non-reduced forms.

I like this since it stands as proof of the countability of the rationals.

Even it not too useful it strikes well with Scheme's affection for math.

If we need to rationalize a use, it could always be helpful in testing,

to make sure something works for the first n rationals.

-- 

Alex