The Iterator Trait and Adapters

By the end of this lesson you can implement Iterator for your own type, use the whole adapter vocabulary on it for free, and tell from a loop header whether the collection is borrowed or consumed. In Rust Fundamentals you chained iter().filter().map().sum(); underneath is a one-method trait that you can implement yourself.

One method: next

trait Iterator {
    type Item;                                 // what the iterator yields
    fn next(&mut self) -> Option<Self::Item>;  // Some(item), or None when finished
    // ...plus dozens of provided methods: map, filter, zip, count, ...
}

Item is an associated type: each implementor names it once and every method uses it. next takes &mut self because the struct is the progress marker; calling it advances the state. Here is an iterator that halves a number until nothing is left:

struct Halves { cur: u32 }

impl Iterator for Halves {
    type Item = u32;
    fn next(&mut self) -> Option<u32> {
        if self.cur == 0 { return None; }
        let out = self.cur;   // remember what to hand out
        self.cur /= 2;        // then move the state on
        Some(out)
    }
}

let mut h = Halves { cur: 3 };
println!("{:?} {:?} {:?} {:?}", h.next(), h.next(), h.next(), h.next());
// Some(3) Some(1) None None

The order inside next is the whole job: hand out the current value, then advance. Swap the two lines (self.cur /= 2; Some(self.cur)) and Halves { cur: 100 } yields 50 25 12 6 3 1 0: the 100 is lost and a stray 0 appears.

Every adapter now works on it

You wrote only next; the rest comes with the trait. Over the sequence 100 50 25 12 6 3 1:

collect builds whatever you name, partition splits one iterator in two by a test, and unzip splits pairs:

let s: String = "stressed".chars().rev().collect();   // "desserts"
let (small, big): (Vec<u32>, Vec<u32>) = Halves { cur: 100 }.partition(|&x| x < 10);
// small = [6, 3, 1], big = [100, 50, 25, 12]

Also there: chain, flat_map, filter_map (map, and drop the Nones), min_by_key, max_by_key. And peekable() adds peek(), a look at the next item without consuming it, which with while let groups runs:

let mut it = [1, 1, 2, 2, 2, 3].iter().peekable();
while let Some(&x) = it.next() {
    let mut n = 1;
    while it.peek() == Some(&&x) { it.next(); n += 1; }
    println!("{}x{}", x, n);        // 1x2, then 2x3, then 3x1
}

.rev() is the one that does not carry over. Halves { cur: 100 }.rev() fails with error[E0277], saying Halves does not implement DoubleEndedIterator: walking from the back needs a second method, next_back, which ranges and slices have and your struct does not. collect into a Vec first.

Pairs: zip with a shifted copy

zip walks two iterators in step and stops at the shorter. Zipping a sequence with itself skipped by one pairs each item with its successor:

let v = vec![3, 7, 12, 12, 20];
let gaps: Vec<i32> = v.iter().zip(v.iter().skip(1)).map(|(a, b)| b - a).collect();
// [4, 5, 0, 8]   five items, four pairs

A Vec can hand out .iter() twice. An iterator cannot: count, sum, collect and zip take self by value, so they use it up.

let h = Halves { cur: 100 };
let a = h.count();
let b = h.count();   // error[E0382]: use of moved value: `h`

Put #[derive(Clone)] on the struct and give each pass its own copy: h.clone().count(). A clone copies the position too, so a clone taken halfway continues from the halfway point.

Who owns the items

A for loop calls IntoIterator::into_iter on whatever follows in, then calls next until None. The three spellings differ in what they yield:

let mut v = vec![1, 2, 3];
for x in v.iter_mut() { *x *= 10; }       // v is [10, 20, 30]
for x in v { println!("{}", x); }         // consumes v
println!("{}", v.len());                  // error[E0382]: `v` was moved by the loop

Every iterator is its own IntoIterator, so for t in h works when h is a Halves. To return a chain without writing its real type, return impl Iterator<Item = u32>:

fn bounce(n: u32) -> impl Iterator<Item = u32> {
    (1..=n).chain((1..n).rev())      // bounce(3) yields 1 2 3 2 1
}

Common mistakes

• Advancing before handing out. The first item is skipped and the sequence ends one value off; every count and total downstream shifts with it.
• Using a value as the stop signal when that value is also a real item. Halves can stop on 0 because 0 is never yielded. If the last real item is one your state could move past, keep a separate done flag and set it as you hand that item out; otherwise the last item is dropped or the iterator never ends.
• Zipping without skip(1). Each item pairs with itself, so every gap is 0 and every "is it bigger" test is false.
• Using the iterator twice without clone(). The second use is E0382, a compile error, not a wrong answer.

Your exercise

Implement Iterator for Collatz so the adapters in report work on it, then replace the ups placeholder with one zip chain. The most likely mistake is an off-by-one in next, which changes every number on every line.