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!)