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 recently, and ended up implementing the algorithm it describes and publishing it as a crate.

This article briefly describes the paper and some of the Rust-specific details of the implementation I arrived at.

The Algorithm

The paper describes an algorithm which, starting from a base case, iterates through every possible rational number. The algorithm is interesting because:

• each value of the iterator is calculated from the previous value (no extra state), and
• each value can be calculated in a fixed number of arithmetics steps.

The Implementation

Generic Numeric Traits

Directly implementing Iterator

no-std

I didn't have a particular

• implemented in Rust
  • num-integer & num-rational
  • Direct implementation of Iterator<>
  • ended up being no-std (was v. easy; yay all the work that goes into Rust!)