Make-rational-number-generator
John Cowan
(08 Feb 2015 01:17 UTC)
|
Re: Make-rational-number-generator
Alex Shinn
(16 Feb 2015 02:03 UTC)
|
Re: Make-rational-number-generator John Cowan (16 Feb 2015 02:29 UTC)
|
Re: Make-rational-number-generator
Alex Shinn
(16 Feb 2015 04:39 UTC)
|
Re: Make-rational-number-generator John Cowan 16 Feb 2015 02:29 UTC
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 xxxxxx@ccil.org 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