Implement Iterator by hand: the Collatz sequence

Write your own iterator, then use the standard adapters on it.

pub struct Collatz { pub n: u64 }

impl Iterator for Collatz { /* ... */ }

pub fn collatz_stats(starts: Vec<u64>) -> Vec<(u64, usize, u64)>

Collatz { n } yields the Collatz sequence starting at n: each value is followed by n / 2 if it is even, or 3n + 1 if it is odd. It yields 1 and then stops. Collatz { n: 0 } is an empty iterator — it yields nothing at all.

Collatz { n: 6 }  ->  6, 3, 10, 5, 16, 8, 4, 2, 1
Collatz { n: 1 }  ->  1
Collatz { n: 0 }  ->  (nothing)

collatz_stats returns one tuple per start: (start, length, max) — how many values the sequence has, and the largest of them. For an empty sequence both are 0. Compute them with adapters on your own iterator (.count(), .max()), not with a hand-rolled loop.

Why one method buys you eighty

Iterator has exactly one required method:

pub trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
    // ~75 provided methods, all defined in terms of next()
}

Everything else — map, filter, zip, take, sum, fold, max, chain, rev (with one extra trait), collect — is a provided method with a default body written against next. So the moment your next compiles, this works, with no further code:

let n: u64 = Collatz { n: 27 }
    .filter(|v| v.is_multiple_of(3))
    .zip(1u64..)
    .map(|(v, i)| v * i)
    .sum();

That is what a trait with provided methods buys, and it is worth stopping to appreciate: you wrote nine lines and joined a vocabulary of eighty. This is the single strongest argument for expressing “a source of values” as an Iterator impl rather than as a function returning a Vec.

type Item is an associated type, not a parameter

Leave it out and you get the error this problem’s starter ships with:

error[E0046]: not all trait items implemented, missing: `Item`

Item is an associated type, which means a given type can implement Iterator once, with one item type. It is not Iterator<T>. That is a deliberate design decision: it is why for x in thing never needs a type annotation to say which iterator impl you meant, and why it.map(f) can infer f‘s parameter type. Item 7.16 is the general treatment; here just note that the single-impl restriction is what makes iterator inference pleasant.

Where hand-written iterators go wrong

Termination. The state machine must reach a state where next returns None and keeps returning it. Get this wrong and you have not written a bug — you have written a hang. There is no diagnostic, no panic, no stack trace; the test times out. Note the two distinct stopping conditions here: the sequence stops after yielding 1, and n == 0 yields nothing at all. The neatest way to express both is a sentinel: set the state to 0 after yielding 1, and return None whenever the state is 0.

Off-by-one at the start. Collatz { n: 6 } yields 6 first. Compute the next state, but yield the current one — a next that advances and then yields drops the first element and is the most common version of this bug.

Yielding after None. An iterator that returns None and then Some again is legal Rust but breaks the expectations of fuse-dependent code. Item 9.22 covers FusedIterator; for now, once you are done, stay done.

Clippy will teach you a method you did not know

On unsigned integers, n % 2 == 0 is now flagged:

error: manual implementation of `.is_multiple_of()`
       [clippy::manual_is_multiple_of]

u64::is_multiple_of reads better and, for a non-constant divisor, avoids a sign-handling branch the remainder version would need. The lint is default-on for unsigned types only — on i64 the two are not equivalent for negative values, so clippy stays quiet there.

Iterating twice

count() and max() each consume an iterator. You need two, so construct two: Collatz { n: start } is a cheap struct literal — one u64 — and building it twice costs nothing. Reaching for Clone or collecting into a Vec first would be strictly more work.

Afterwards

Once this works, look up std::iter::successors. It builds exactly this shape of iterator from a seed and a step closure, and now that you have written the state machine by hand you will recognise precisely what it is doing. Item 9.17 is about that family.

Grade is compile + tests + clippy -D warnings.