# Iterating over the Rational Numbers with Rust

Functional Pearl: Enumerating the Rationals is a paper that's been on my "to-read" list for a long time. I finally got around to reading it a while back, and ended up implementing the algorithm it describes and publishing it as a crate. This article briefly describes that algorithm and some of the Rust-specific details of implementing it.

## The Algorithm

The paper describes an algorithm which, starting from a base case, iterates through every possible rational number (up to the limitations of machine precision). The algorithm is interesting because:

- each value of the iterator is calculated from only the previous value (no extra state), and
- each value can be calculated in a fixed number of arithmetic operations.

There's a lengthy proof of why the algorithm works, but the essence is just a few lines of Haskell:

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

Where iterate, recip, fromInteger, and properFraction are functions from the Haskell prelude.

The equivalent Rust code is something like:

```
fn next(&mut self) -> Option<Self::Item> {
let r = self.state.clone();
let n = r.trunc();
let y = r.fract();
let next = (n + T::one() - y).recip();
self.state = next;
Some(r)
}
```

The interesting part of the Rust implementation is how it's made generic over
any numeric type that supports `trunc`

, `fract`

, and `recip`

, and how that
integrates with the broader Rust ecosystem.

## The Implementation

The iterator is implemented on a struct which takes one generic parameter `T`

,
which must be an integer type. It yields ratios of integers of type `T`

. Rather
than just picking one integer type or implementing the iterator separately for
`u8`

, `u32`

, `u64`

, etc. we use:

### Generic Numeric Traits

Specifically, it's implemented as a `Ratio<Integer>`

, which together provide all
the operations we need for our algorithm.

These come from a two different crates:

`num-rational`

provides`Ratio`

`num-integer`

provides`Integer`

.

`Integer`

is implemented for all the native integer types, so we can iterator
over `Ratio`

s of `u8`

, `u32`

, `u64`

. There are also other types that implement
`Integer`

(e.g: `num_bigint::BigInt`

) which might be useful in different
circumstances (e.g: for arbitrary precision arithmetic which is accurate but
slow).

### Directly implementing `Iterator`

Rust has functions like `iter::repeat_with`

that would let us more or less
copy the Haskell code above, but it ended up being just as easy to
implement `Iterator`

directly. This also made the algorithm:

`no-std`

Since the implementation is just a bit of math and the types are all
straightforward (at least in terms of memory) it ended up not depending on the
Rust standard library (i.e. it's `no-std`

), although at the time of writing,
`num-traits`

was having some difficulty with it's `no-std`

builds that meant I
couldn't actually test this.