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.
Alex Shinn scripsit:
> Cute. Proof?
It's the Calkins-Wilf sequence. There's a very clear discussion of it in
Gibbons, Jeremy; Lester, David; Bird, Richard (2006), "Functional pearl:
Enumerating the rationals", Journal of Functional Programming 16 (3):
281–291, doi:10.1017/S0956796806005880, which is accessible to all at
<http://www.cs.ox.ac.uk/jeremy.gibbons/publications/rationals.pdf>,
and is cited in SRFI 41.
The paper gives this Haskell definition:
rats :: [Rational]
rats = iterate next 1
next x = recip (fromInteger n+1−y) where (n,y) = properFraction x
where properFraction is (- x (truncate x)) and fromInteger is just
an integer->rational cast that Scheme doesn't need to write explicitly.
> (you missed 1 after 0)
Oops.
> You could also use a more intuitive diagonalization order, at the
> cost of some busy work to filter non-reduced forms.
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 [] [] = []
> 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.
I guess so.
--
John Cowan http://www.ccil.org/~cowan cowan@xxxxxxxx
The Penguin shall hunt and devour all that is crufty, gnarly and
bogacious; all code which wriggles like spaghetti, or is infested with
blighting creatures, or is bound by grave and perilous Licences shall it
capture. And in capturing shall it replicate, and in replicating shall
it document, and in documentation shall it bring freedom, serenity and
most cool froodiness to the earth and all who code therein. --Gospel of Tux