[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Make-rational-number-generator

This page is part of the web mail archives of SRFI 121 from before July 7th, 2015. The new archives for SRFI 121 contain all messages, not just those from before July 7th, 2015.

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.