Iterators that keep state

An iterator is a state machine with one method: next returns the next value or says there is none. A struct with a few fields is enough state for most sequences, and a vector used as a stack is enough for a walk over a tree. The adaptors of the earlier lessons work on any of them.

This lesson writes four iterators by hand, from a two-field counter to a walk with a stack, and ends with the compiler error for a type that implements the trait without the one required method.

State in a struct

The Fibonacci sequence needs two numbers: the current one and the next. next hands out the first, shifts the pair and returns the value, which is the whole state machine.

The program takes eight values from the iterator and collects them into a vector. The first two are the seeds, and every later value is the sum of the two before it.

struct Fibonacci { a: u64, b: u64, } impl Iterator for Fibonacci { type Item = u64; fn next(&mut self) -> Option<u64> { let value = self.a; self.a = self.b; self.b = value + self.b; Some(value) } } fn main() { let values: Vec<u64> = Fibonacci { a: 0, b: 1 }.take(8).collect(); println!("{values:?}"); }

rustc --edition 2024 fib.rs
./fib

[0, 1, 1, 2, 3, 5, 8, 13]

The iterator never ends by itself, and take is what stops it. That is the shape of every infinite generator: next always returns Some, and the consumer decides how many to pull. The lesson on the Iterator trait is the trait itself.

Two optional methods make an iterator a better citizen. size_hint tells a consumer how many values are left, and collect uses it to reserve the right amount of memory. nth skips forward without calling next in a loop, which a generator with cheap state can implement directly. Neither is required, and a default that is correct but slow is what a first version should use.

A function can also return an iterator without a struct of its own: -> impl Iterator<Item = i32> hides the concrete type, and std::iter::from_fn turns a closure with state into one. Both are the same state machine with the type left to the compiler.

A tree walk with a stack

A walk over a tree is a state machine whose state is a list of nodes still to visit. The stack is a Vec of references, and next pops until it finds a leaf, pushing the children of every node it passes.

The program builds a small tree and walks it in order. The values come out sorted because the left child is pushed last and therefore popped first.

enum Tree { Leaf(i32), Node(Box<Tree>, Box<Tree>), } struct Walk<'a> { stack: Vec<&'a Tree>, } impl<'a> Iterator for Walk<'a> { type Item = i32; fn next(&mut self) -> Option<i32> { while let Some(node) = self.stack.pop() { match node { Tree::Leaf(value) => return Some(*value), Tree::Node(left, right) => { self.stack.push(right); self.stack.push(left); } } } None } } fn main() { let tree = Tree::Node( Box::new(Tree::Node(Box::new(Tree::Leaf(1)), Box::new(Tree::Leaf(2)))), Box::new(Tree::Leaf(3)), ); let values: Vec<i32> = Walk { stack: vec![&tree] }.collect(); println!("{values:?}"); }

rustc --edition 2024 tree.rs
./tree

[1, 2, 3]

The lifetime on the struct says the walk borrows the tree, so the stack of references cannot outlive it. An iterator that owned the nodes would push them by value and would be the same code with Tree instead of &Tree. The lesson on lifetimes is the annotation.

A sequence from a loop

A sequence defined by a rule is a state machine with one field and a transition. The Collatz sequence halves an even number and triples plus one an odd one, and stops at one.

The program collects the sequence that starts at six. Nine values come out, and the last is one.

struct Collatz { value: u64, } impl Iterator for Collatz { type Item = u64; fn next(&mut self) -> Option<u64> { if self.value == 0 { return None; } let current = self.value; self.value = if current == 1 { 0 } else if current % 2 == 0 { current / 2 } else { 3 * current + 1 }; Some(current) } } fn main() { let values: Vec<u64> = Collatz { value: 6 }.collect(); println!("{values:?}"); }

rustc --edition 2024 collatz.rs
./collatz

[6, 3, 10, 5, 16, 8, 4, 2, 1]

The zero is the end marker, and the transition from one to zero is what makes collect stop. A sequence that never reaches one would run forever, which is the open problem about this particular rule. The lesson on ranges is the built-in version of a sequence with an end.

A lazy sequence

A chain of adaptors computes nothing until a consumer asks. The range is infinite, the map squares, the filter keeps the odd squares, and take is the limit that makes the whole thing finite.

The program collects four values. Four squares are computed, of which the odd ones are the first, third, fifth and seventh, so the largest number is forty-nine.

fn main() { let squares = (1..).map(|value| value * value); let picked: Vec<i32> = squares.filter(|value| value % 2 == 1).take(4).collect(); println!("{picked:?}"); }

rustc --edition 2024 lazy.rs
./lazy

[1, 9, 25, 49]

The source is 1.., which has no end, and the chain is still finite because take stops pulling. That is the same laziness the lesson on adaptors describes for finite sources, and the reason a chain of ten adaptors still walks the data once.

An iterator whose state is a few numbers is also the cheapest way to test a loop: the test drives the sequence by hand and checks the values without a container in between.

An Iterator without next

next is the only required method of the trait, and a type that implements Iterator without it does not compile. The error is E0046, and the help prints a signature that can be pasted.

The program declares the associated type and nothing else. The compiler lists the missing method.

struct Counter; impl Iterator for Counter { type Item = i32; } fn main() {}

rustc --edition 2024 missing_err.rs

error[E0046]: not all trait items implemented, missing: `next`
--> missing_err.rs:3:1
|
3 | impl Iterator for Counter {
| ^^^^^^^^^^^^^^^^^^^^^^^^^ missing `next` in implementation
|
= help: implement the missing item: `fn next(&mut self) -> Option<<Self as Iterator>::Item> { todo!() }`

error: aborting due to 1 previous error

For more information about this error, try `rustc --explain E0046`.

The signature in the help is the one every iterator writes, with the associated type in place of Self::Item. The next lesson splits a sequence across threads and collects the parts.

Exercises

1. Write an iterator over the multiples of three and take the first five.
2. Make the tree walk return the values in reverse order by pushing the children the other way.
3. Give the Collatz iterator a new constructor that rejects zero.

The code on this page was built with rustc 1.96.1 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev