[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 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)))
             (set! diag (+ diag 1))
             (set! i 1))))
    (lambda ()
      (let lp ()
        (let ((res (/ i (+ 1 (- diag i)))))
          (if (= i (numerator res))