skip to content

In Rust, what must you write to turn a struct generating a Fibonacci-like ID sequence into an iterator usable with for, map and take?

level: juniorimportance: must knowfreq 55%

answer

  1. one associated type, one method
  2. the type of each yielded value
  3. next takes &mut self
  4. Option marks the end
  5. adapters are provided methods

basics

~20 s

Implement Iterator for the struct: declare type Item = u64 and write fn next(&mut self) -> Option<u64>, returning None when the sequence ends. Adapters such as map and take, and for loops, then work with no further code.

solid answer

~40 s

The `Iterator` trait has one associated type and one required method: `type Item` names what each step yields, and `fn next(&mut self) -> Option<Self::Item>` advances the state held in the struct and returns `Some(value)`, or `None` once the sequence is over. Everything else — `map`, `filter`, `take`, `count`, `last`, `collect` — is a provided method whose default body calls `next`, so the struct gets it for free. A `for` loop works because std has a blanket `impl<I: Iterator> IntoIterator for I` that returns the iterator itself. Leaving out `type Item` is E0046, and returning `u64` instead of `Option<u64>` is E0053. For an ID sequence, compute the next value with `checked_add` so the sequence ends with `None` instead of overflowing.

code

rust · 32 lines
rust
struct IdSeq {
    cur: Option<u64>,
    nxt: Option<u64>,
}

impl IdSeq {
    fn new() -> Self {
        IdSeq { cur: Some(1), nxt: Some(2) }
    }
}

impl Iterator for IdSeq {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let out = self.cur.take()?; // None once the sequence is over
        self.cur = self.nxt;
        self.nxt = self.nxt.and_then(|n| out.checked_add(n));
        Some(out)
    }
}

fn main() {
    for id in IdSeq::new().take(5) {
        print!("{id} ");
    }
    println!();
    let evens: Vec<u64> = IdSeq::new().filter(|n| n % 2 == 0).take(3).collect();
    println!("{evens:?}");
    println!("ids before overflow: {}", IdSeq::new().count());
    println!("last: {:?}", IdSeq::new().last());
}

go deeper

for a junior

Recall the two pieces: type Item and fn next(&mut self) -> OptionSelf::Item, with None meaning the sequence is over. Be ready to write the impl on a whiteboard.

for a middle

Explain that adapters are provided methods built on next, that for works through the blanket IntoIterator impl, and how the struct carries state between calls.

for a senior

Show care for the end condition: checked arithmetic instead of an overflow panic in debug and wrapping in release, plus an honest size_hint if you override it.

for a principal

Weigh exposing a named iterator struct, which callers can store and which can implement extra traits, against returning an opaque impl Iterator from a function.

## The trait you implement In Rust an **iterator** is any type that implements the standard trait `Iterator`. The trait asks for exactly two things: - an **associated type** `type Item`, which names the type of every value the iterator yields; - a **required method** `fn next(&mut self) -> Option<Self::Item>`, which advances the iterator by one step. `next` returns `Some(value)` while there is a value to give and `None` when the sequence is finished. It takes `&mut self` because each call changes state stored inside the iterator — the position, the previous values, a buffer — but it must not consume the iterator, since you call it again and again. The struct is where that state lives between calls. A Fibonacci-like ID sequence (each ID is the sum of the previous two) needs to remember the current and the next value. ## The ID sequence, step by step ```rust struct IdSeq { cur: Option<u64>, nxt: Option<u64> } impl Iterator for IdSeq { type Item = u64; fn next(&mut self) -> Option<u64> { let out = self.cur.take()?; // None once finished self.cur = self.nxt; self.nxt = self.nxt.and_then(|n| out.checked_add(n)); Some(out) } } ``` 1. `self.cur.take()?` moves the current value out and returns `None` early if the sequence is already over. 2. The next value becomes the current one. 3. The value after that is computed with `checked_add`, which yields `None` instead of overflowing; that `None` ripples forward, so the iterator yields every representable ID and then ends. With plain `+`, after about ninety IDs the sum no longer fits in a `u64`: a debug build panics with an overflow error, and a release build wraps by default, quietly producing a small, wrong ID. Checked arithmetic turns the end of the representable range into the end of the sequence. ## What you get for free The trait has dozens of **provided methods** — methods with a default body written in terms of `next`. Once `next` exists, the struct can call all of them: | Call | What it does with `next` | |---|---| | `take(5)` | wraps the iterator and stops after five `Some`s | | `filter(p)` | calls `next` until `p` accepts a value | | `map(f)` | calls `next` and applies `f` to each value | | `count()` / `last()` | call `next` until `None` | | `collect::<Vec<_>>()` | gathers every value through `FromIterator` | Adapters such as `take`, `map` and `filter` are lazy: they build a new iterator and do nothing until something calls `next` on it. Because `next` borrows the iterator mutably rather than consuming it, `it.by_ref().take(3)` lets you take a prefix and keep using `it` afterwards; most adapters take `self` by value, and `by_ref` hands them a `&mut` instead, which is itself an iterator. You may override a provided method when you can do better — `size_hint` and `nth` are the usual candidates — but you never have to. A `for` loop over the struct needs no extra impl either. `for id in seq` calls `IntoIterator::into_iter(seq)`, and std provides `impl<I: Iterator> IntoIterator for I`, whose `into_iter` returns the iterator unchanged. ## The mistakes rustc catches - **Missing `type Item`**: rustc reports E0046, "not all trait items implemented, missing: `Item`". - **Wrong return type** — `fn next(&mut self) -> u64`: E0053, "method `next` has an incompatible type for trait", with a hint to return `Option<u64>`. - **Writing `impl Iterator<u64> for IdSeq`**: `Item` is an associated type, not a generic parameter, so the trait takes no type argument. - **Calling `next` on a binding that is not `mut`**: `next` needs `&mut self`, so `let it = IdSeq::new(); it.next()` is rejected; `let mut it` fixes it. ## Design notes - **Infinite is fine.** An iterator need not end; callers bound it with `take` or `take_while`. Ending at overflow simply makes the end explicit. - **Keep the struct small and the constructor obvious** — `IdSeq::new()` sets the two seed values so callers cannot build an inconsistent state. - **Test both ends.** Assert the first values with `take(5).collect::<Vec<_>>()` and the end with `count()` or `last()`; an off-by-one in the state update shows up immediately in one of the two. - **Generator or collection?** A type whose whole purpose is producing values implements `Iterator` itself. A collection that owns data instead offers `iter()` and `IntoIterator` returning a separate iterator type, so walking it does not consume or mutate the collection.

  • Why does Iterator::next take &mut self rather than self or &self?
    Each call has to change state inside the iterator, so it needs mutable access, but it must not consume the iterator because you call it repeatedly. That is also why calling `next` by hand needs `let mut it`, and why `by_ref()` lets you consume part of an iterator and keep using the rest.
  • Must the ID sequence override size_hint?
    No. The default returns `(0, None)`, which is correct for any iterator. Overriding it only helps consumers such as `collect` pre-allocate, and the bound you return must be honest. For a sequence that ends at overflow, keep the default unless you compute the remaining count exactly.
  • Should a collection type implement Iterator on itself?
    Usually not. Iterating would then consume or mutate the collection's own state. A collection offers `iter()` returning a separate iterator type and implements `IntoIterator` for itself and for a reference to itself; a pure generator like the ID sequence implements `Iterator` directly.

  • A custom iterator must implement map, filter and collect itself.
  • next returns the item directly and signals the end with a sentinel value.
  • A for loop needs a separate IntoIterator impl on top of Iterator.
  • Item is a generic parameter, so you write impl Iterator<u64> for IdSeq.
  • Plain + on u64 always wraps silently at the end of the sequence.