William Lee Irwin III wrote:
>
> The rationals may be enumerated according to the construction given by
> Cantor, or by various other means. Cantor's construction was to arrange
> pairs of natural numbers (i,j) in a big 2-D array, strike out the entries
> with gcd(i,j) /= 1, and then traverse the diagonals of the array. Some
> Haskell code which does this is the following:
>
> zipDiag :: [a] -> [b] -> [(a,b)]
> zipDiag xs ys = concat $ zipWith (map . (,)) xs (tail $ inits ys)
> diag :: [a] -> [(a,a)]
> diag xs = zipDiag xs xs
> diagZ :: [(Integer, Integer)]
> diagZ = [mn | mn <- diag [1..], (uncurry gcd) mn == 1]
> nthRational :: Integral a => a -> Ratio Integer
> nthRational n = uncurry (%) $ diagZ `genericIndex` n
> rationals = map (uncurry (%)) diagZ
>
> I suppose this only handles the positive rationals. It shouldn't be
> terribly hard to (a) stick zero in there somewhere and (b) interleave
> the positive and negative rationals. On the other hand, there isn't a
> terribly obvious way to get the next rational in this enumeration. If
> anybody knows of a better way, do tell. There is also the fact that
> this enumeration (and probably most others as well) of the rationals
> isn't terribly useful in programming contexts to worry about, but I
> suppose the point is made.
Here's another way of generating sequences of fractions based on continued
fractions. It generates each fraction already in reduced form once and once
only
{-
fracts is an infinite enumeration of the positive fractions
It operates by generating an infinite binary tree of all the
finite continued fractions and then traversing it.
A tree with the (reduced) fraction f at its root has f+1 and 1/(f+1) at
the roots of its sub-trees. These are already in reduced form.
Different traversals will
give different enumerations. Two (one commented) are given here.
As the tree is infinite, care must
be taken not to traverse it depth first!
-}
one = (1%1)
fracts = sequ one
sequ f = f : intersperse (sequ f')(sequ(recip f')) where f' = f + one
-- intersperse (x:xs) (y:ys) = x:y:intersperse xs ys -- naive interleaving,
breadth first
intersperse xx@(x:xs) yy@(y:ys) | size x < size y = x : intersperse xs yy
| otherwise = y : intersperse xx ys
where size x = numerator x + denominator x
--
Tony Davie, Computer Science, St.Andrews University, North Haugh, St.Andrews
Scotland, KY16 9SS, Tel: +44 1334 463257, Fax: +44 1334 463278
mailto:[EMAIL PROTECTED] Home: http://www.dcs.st-and.ac.uk/~ad/Home.html
Handel Index and Chronology:
http://bruichladdich.dcs.st-and.ac.uk/HandelWWW/HandelCat.html
