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