# Generating all rationals (Haskell)

Other implementations: C | dc | Haskell | Python

## Generating Q from N2

We will first generate the non-invertible elements of the rationals ($\mathbb{Q}$), then follow with the remainder of $\mathbb{Q}$, in a monadic fashion.

<<generate rationals>>=
import Data.Ratio

--- an infinite list of all rationals
rationals :: [Rational]
rationals = generate non-invertible rationals
mplus
generate invertible rationals


The non-invertible elements are trivial: $0 = \frac {0}{1}$

<<generate non-invertible rationals>>=
return (0 % 1)


In order to generate the invertible elements, we use a diagonal construction, similar to the one in used in Generating all integer lattice points (Python) for $\mathbb{N}^2$. Now we wish to generate ascending diagonals, so we will count n up indefinitely, generating a diagonal for each value of n.

<<generate invertible rationals>>=
do
n <- [0..]
generate diagonal entries


The diagonal itself merely generates each formal rational whose numerator and denominator add up to n + 1. For instance, when n = 6, we will generate $\left \{ \frac{1}{6}, \frac{2}{5}, \frac{3}{4}, \frac{4}{3}, \frac{5}{2}, \frac{6}{1} \right \}$.

<<generate diagonal entries>>=
m <- [0..n-1]
filter for uniqueness


Unlike the problem of generating lattice points, in which for instance (1,2) and (2,4) would code for different screen pixels, we find that two formally different rational expressions can be equivalent: $\frac {1}{2} = \frac {2}{4}$. Therefore we calculate the greatest common denominator and use the resulting flag to select only the fully reduced fractions. For each positive rational, we also have to generate its negative.

<<filter for uniqueness>>=
let i = m + 1
j = n - m
guard $gcd i j == 1 sign <- [1, -1] return$ sign * i % j


## Finishing up

Finally, we output all the rationals. You can use the "take" function to take only the first so-many items of the infinite list if you want it to stop.

<<allrats.hs>>=
generate rationals

main :: IO ()
main = mapM_ print rationals

hijacker
hijacker
hijacker
hijacker