Step 7 of 7

Implementing Iterator for your own type

Any type can be an iterator: implement next, and you get every adapter and consumer (map, filter, take, sum, collect and about 70 more) for free, because they're default methods of the Iterator trait.

struct Fibonacci {
    current: u64,
    next: u64,
}

impl Fibonacci {
    fn new() -> Self {
        Fibonacci { current: 0, next: 1 }
    }
}

impl Iterator for Fibonacci {
    type Item = u64;

    fn next(&mut self) -> Option<Self::Item> {
        let value = self.current;
        self.current = self.next;
        self.next += value;
        Some(value)
    }
}

fn main() {
    let first: Vec<u64> = Fibonacci::new().take(10).collect();
    println!("{:?}", first);

    let even_sum: u64 = Fibonacci::new()
        .take_while(|&f| f < 4_000_000)
        .filter(|f| f % 2 == 0)
        .sum();
    println!("{even_sum}");
}

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
4613732

Piece by piece:

impl Iterator for Fibonacci: implementing a standard trait, as in the traits module.
type Item = u64;: the associated type: this iterator yields u64s. In the signature, Self::Item refers to it (writing Option<u64> is the same).
next(&mut self): moves the state stored in the struct forward and returns the next value. The struct's fields are the iterator's memory between calls.
This iterator never returns None: it's infinite, so callers bound it with take or take_while. A finite iterator returns None when it's done, and should keep returning None if asked again.

Returning iterators from functions

Often you don't need a new struct: return a chain built from existing iterators, typed as impl Iterator<Item = ...>. Callers decide what to do with it (count it, take a few, collect it), and nothing is allocated in between:

struct Team {
    members: Vec<(String, bool)>, // (name, active?)
}

impl Team {
    fn active(&self) -> impl Iterator<Item = &str> {
        self.members.iter().filter(|m| m.1).map(|m| m.0.as_str())
    }
}

fn main() {
    let team = Team {
        members: vec![
            (String::from("ann"), true),
            (String::from("bo"), false),
            (String::from("cy"), true),
        ],
    };
    println!("{}", team.active().count());
    let names: Vec<&str> = team.active().collect();
    println!("{}", names.join(", "));
}

2
ann, cy

This is a common pattern in libraries: return impl Iterator instead of a Vec when the caller might not need every item.

Common mistakes

Forgetting type Item:

struct Countdown {
    remaining: u32,
}

impl Iterator for Countdown {
    fn next(&mut self) -> Option<u32> {
        None
    }
}

fn main() {
    let c = Countdown { remaining: 3 };
    println!("{}", c.remaining);
}

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

Writing &self instead of &mut self. next must be able to change the state, and the trait says so: error[E0053]: method `next` has an incompatible type for trait.
Not moving the state forward in next: the iterator returns the same item forever, and a collect never finishes.

Your task

Implement Iterator for Countdown. Countdown::new(3) yields 3, 2, 1 and then None (and keeps returning None after that). Countdown::new(0) yields nothing.

Challenge 2

The Collatz sequence starts at a number n: if n is even the next number is n / 2, if it's odd the next is 3 * n + 1, and it ends when it reaches 1. Implement Iterator for Collatz so that Collatz::new(6) yields 6, 3, 10, 5, 16, 8, 4, 2, 1 and then None. The done field remembers that 1 has been yielded. (The start is always at least 1.)

Challenge 3

APIs often return results a page at a time. Implement Iterator for Pages, which walks a slice of ids in pages of size items: with ids [1, 2, 3, 4, 5] and size 2, it yields [1, 2], [3, 4], [5], then None. Each item is a sub-slice of the original (&'a [i32]), so nothing is copied. (size is always at least 1.)

You'll need split_at from the slices module, and min so the last page can be shorter.

Previous: collect, the turbofish, and collecting Results