# 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:

`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.