Re: Make-rational-number-generator

[Alex Shinn <alexshinn@xxxxxxxxx>]

On Mon, Feb 16, 2015 at 11:29 AM, John Cowan <cowan@xxxxxxxxxxxxxxxx> wrote:

Yes, that's the Stern-Brocot tree discussed in the same paper.  The trouble
is that you need to keep around more (indeed, increasingly more) state.
Here's the Haskell version from the paper:

rats :: [Rational]
rats = concat (unfolds infill [(0,1),(1,0)])
unfolds f a = let (b,a') = f a in b : unfolds f a0
infill xs = (map mkRat ys,interleave xs ys)
                 where ys = zipWith adj xs (tail xs)
interleave (x : xs) ys = x : interleave ys xs
interleave [] [] = []

The implementation I was envisioning only needs small constant space.

The proof is also simpler: completeness is trivial because we order over

all i/j, and uniqueness is guaranteed by skipping non-reduced forms.

(define (make-rational-number-generator)

  (let ((diag 1)

        (i 0))

    (define (next!)

      (cond ((<= (+ i 1) diag)

             (set! i (+ i 1)))

            (else

             (set! diag (+ diag 1))

             (set! i 1))))

    (lambda ()

      (let lp ()

        (next!)

        (let ((res (/ i (+ 1 (- diag i)))))

          (if (= i (numerator res))

              res

              (lp)))))))

-- 

Alex