# Generating all rationals (dc)

Other implementations: C | dc | Haskell | Python

## theory

This one-liner is a translation of the Haskell algorithm given (and explained) in Jeremy Gibbons, David Lester and Richard Bird (2006). Enumerating the Rationals. which (unlike the standard algorithm given here in Python) generates elements of $\mathbb{Q}$ without duplication, by effectively feeding the tree of all bitsequences backwards through GCD.

## practice

```<<allrats.dc>>=
1sn1sd[lnn[/]Pldn[ ]Plnld~sasbldsnlb1+ld*la-sdlRx]dsRx
```

The Haskell is a little less opaque, and goes as follows:

```rats7 :: [ Rational]
rats7 = iterate next 1
next x = recip (fromInteger n +1 −y) where (n, y) = properFraction x
```

where

• ln ld ~ sa sb roughly corresponds to `(n, y) = properFraction x `,
• ld sn lb 1+ ld* la - sd to `recip (fromInteger n + 1 -y)`
• and 1sn 1sd to the 1 in `iterate next 1`.

for an explanation of why this works, please consult the Gibbons paper.

## wrapping up

Unfortunately the `dc` on my system is not properly tail-recursive and so fails to generate all the rationals. Also, it insists upon printing out escaped newlines from time to time.

Both of these issues can be mitigated by using the Desk calculator (Python) emulator, or avoided entirely by calling `dc` with the following command line:

```(echo "1sn1sd"; yes "lnn[/]Pldn[ ]Plnld~sasbldsnlb1+ld*la-sd") | dc | unvis
```

producing a string that starts with:

```1/1 1/2 2/1 1/3 3/2 2/3 3/1 1/4 4/3 3/5 5/2 2/5 5/3 3/4 4/1 1/5 5/4 4/7 7/3 3/8 8/5 5/7 7/2 2/7 7/5 5/8 8/3 3/7 7/4 4/5 5/1 1/6 ...
```
hijacker
hijacker
hijacker
hijacker