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

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.

*To*: Alex Shinn <alexshinn@xxxxxxxxx>*Subject*: Re: Make-rational-number-generator*From*: John Cowan <cowan@xxxxxxxxxxxxxxxx>*Date*: Sun, 15 Feb 2015 21:29:00 -0500*Cc*: srfi-121@xxxxxxxxxxxxxxxxx*Delivered-to*: srfi-121@xxxxxxxxxxxxxxxxx*In-reply-to*: <CAMMPzYORwVfSrUZBxwyvdpKJaqyiKA_Ji_pKjcDbwS8O3jceQA@mail.gmail.com>*References*: <20150208011715.GH14765@mercury.ccil.org> <CAMMPzYORwVfSrUZBxwyvdpKJaqyiKA_Ji_pKjcDbwS8O3jceQA@mail.gmail.com>*Sender*: John Cowan <cowan@xxxxxxxx>*User-agent*: Mutt/1.5.20 (2009-06-14)

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

**Follow-Ups**:**Re: Make-rational-number-generator***From:*Alex Shinn

**References**:**Make-rational-number-generator***From:*John Cowan

**Re: Make-rational-number-generator***From:*Alex Shinn

- Prev by Date:
**Re: Make-rational-number-generator** - Next by Date:
**Re: Make-rational-number-generator** - Previous by thread:
**Re: Make-rational-number-generator** - Next by thread:
**Re: Make-rational-number-generator** - Index(es):