Iterators, the Lazy Pull

You know how to walk a collection. In Go you write for i, v := range xs; in Python for v in xs; in JavaScript xs.forEach(v => ...). In every one of those, the collection is in charge: it pushes each element at your loop body, one after another, until it runs out. The work happens because the container decides to hand it to you.

Rust turns that around. The collection does not push; you pull. You ask for one value, you get it, you ask again, and at some point the answer is “there are no more.” A pull is a single method call, and the whole of iteration in Rust is built on it. Here is the most literal version of that idea, with no loop and no sugar. Read it, then press Run:

// A pull is one call to next(). The loop just keeps pulling until the well dries.
fn main() {
    let scores = [70, 85, 90];

    // iter() hands back something that knows how to produce one item at a time.
    let mut pulls = scores.iter();

    // Each next() is one pull. Some(&value) while items remain, then None forever.
    println!("{:?}", pulls.next()); // Some(70)
    println!("{:?}", pulls.next()); // Some(85)
    println!("{:?}", pulls.next()); // Some(90)
    println!("{:?}", pulls.next()); // None: the well is dry
    println!("{:?}", pulls.next()); // None again, and forever after
}

scores.iter() gives back an iterator: a small value that remembers where it is in the array. Each next() is one pull. The first three return Some(70), Some(85), Some(90): the value is there, wrapped in the Some you met when you learned Option. After the last element, next() returns None, and it keeps returning None every time you call it again. None is the signal that means stop.

Notice pulls is declared mut. Pulling changes the iterator: it has to remember that it already handed you 70 so the next pull gives 85. The iterator is the cursor, and advancing the cursor mutates it. That is the entire mechanism. Everything else in this chapter, every adapter and every loop, is layered on top of this one move.

What makes a value an iterator is not magic and not a keyword. It is a trait, the same kind of trait you implemented in III.10. The trait is called Iterator, and it is almost comically small. It has exactly one method you are required to write:

fn next(&mut self) -> Option<Self::Item>

Read that signature slowly, because every word in it earns its place. &mut self says a pull mutates the iterator, which you already saw: it advances the cursor. Self::Item is an associated type, the feature from III.10 where a trait names a type that each implementor fills in. It is the type of one pulled value: i32 for an iterator of numbers, &str for one of string slices, whatever you choose. And the return is Option<Self::Item>: Some(item) while items remain, None when they are gone. That Optionis doing real work here. It is how a single method can express both “here is a value” and “there are no more” without a second function and without a sentinel value.

That is the whole required surface. One method, next(), returning an Option. Everything else the trait offers, the map, filter, sum, collect, and dozens more you will meet, comes with default implementations built on top of next(). Implement the one method and you inherit all of them, for free, which is the payoff you will collect in section 07. The full catalog of those methods, and the deeper reason they all share one chainable shape, is the subject of Part IV and its chapter on monads. This chapter is the language mechanism underneath them.

Here is the property that surprises people coming from other languages, and it is worth meeting head on. When you call map on an iterator, nothing happens. The closure you passed does not run. No values are transformed. The call returns instantly, handing back a new iterator that merely remembers what you asked for. This is called laziness: an adapter builds a description of work and defers all of it until something forces the issue. Run this and watch the ordering of the printed lines:

// An adapter builds a plan. Nothing runs until a consumer pulls.
fn main() {
    let nums = [1, 2, 3, 4];

    // map() returns immediately. The closure has NOT run yet: this is just a
    // description of work, not the work. No "(squaring N)" line prints here.
    let plan = nums.iter().map(|n| {
        println!("(squaring {n})");
        n * n
    });

    println!("plan built, nothing has run");

    // sum() is a consumer: it pulls every item, which finally runs the closure.
    let total: i32 = plan.sum();
    println!("total = {total}");
}

The line plan built, nothing has run prints before any (squaring N) line. That is the proof. The map closure prints as a side effect, so if it had run during the map call you would see the squaring lines first. Instead they appear only when sum() starts pulling, because sum is the thing that actually walks the iterator to the end. Up to that point, plan is an inert recipe.

If you are coming from a language where [1,2,3].map(f)eagerly builds a whole new array, this is a real difference, not a cosmetic one. Rust’s map allocates nothing and runs nothing on its own. The benefit shows up the moment you chain: a filter then a map then a take(3) never builds the intermediate collections an eager language would, and it can stop early after three items because the work is pulled on demand, not done up front.

Once you see that adapters are lazy, the whole iterator vocabulary sorts into two piles, and knowing which pile a method is in tells you what it does to the chain. Adapters take an iterator and return a new iterator: they are lazy, they describe a step, and you can keep chaining after them. map, filter, take, enumerate, and zip are all adapters. Consumers take an iterator and pull it to produce a final value: they are where the work actually runs, and the chain ends with them. collect, sum, fold, for_each, and count are consumers. Run this and trace each call into its pile:

// Adapters chain (each returns a new iterator); a consumer ends the chain.
fn main() {
    let prices = [12, 7, 30, 4, 19, 25];

    // Three adapters, lazy, each wrapping the one before:
    //   filter keeps items, map transforms them, take cuts the chain short.
    // Then collect is the consumer that finally pulls and gathers the results.
    let cheap: Vec<i32> = prices
        .iter()
        .filter(|&&p| p < 20) // keep prices under 20
        .map(|&p| p + 1)      // add a one-unit fee
        .take(2)              // we only want the first two
        .collect();           // consumer: run the plan, build a Vec

    println!("{cheap:?}"); // [13, 8]

    // A different consumer over the same kind of chain: sum totals the pulls.
    let total: i32 = prices.iter().filter(|&&p| p >= 20).sum();
    println!("big spenders total {total}"); // 30 + 25 = 55
}

The first chain stacks three adapters and ends in one consumer. filter keeps the prices under twenty, map adds a fee, take(2) says stop after two, and then collect is the consumer that finally pulls and gathers the survivors into a Vec. Because the whole thing is lazy, take(2) genuinely stops the work early: the third qualifying price is never even fee-adjusted, because map is only asked for two items. The second chain shows a different consumer, sum, ending a one-adapter chain by adding up every pulled value.

The annotation on collect is worth a word, because it trips up newcomers. You usually have to tell collect what to build, here with the type on the binding, let cheap: Vec<i32>. collect is generic over the result type, so the same pull-everything machinery can build a Vec, a String, a HashMap, and more; you choose by naming the target, and the compiler wires up the right gathering. The complete menu of what collect can target is a Part IV story; here it is enough that the type annotation is how you steer it.

A collection does not give you just one iterator; it gives you three, and the difference between them is the ownership lesson from earlier in Part III wearing iterator clothes. iter() yields &T, a shared borrow of each item, so you can read and the collection survives. iter_mut() yields &mut T, a unique borrow, so you can edit each item in place and the collection survives. into_iter() yields T itself, taking ownership: it consumes the collection and hands you each value to keep. Run this and watch which collections live on afterward:

// Three doors into a collection: borrow, borrow-to-edit, or take ownership.
fn main() {
    // iter() yields &T: a shared borrow. You can read, the Vec lives on.
    let names = vec![String::from("ada"), String::from("alan")];
    for n in names.iter() {
        println!("read {n}"); // n is &String
    }
    println!("names still usable: {}", names.len());

    // iter_mut() yields &mut T: you may edit each item in place.
    let mut counts = vec![1, 2, 3];
    for c in counts.iter_mut() {
        *c *= 10; // c is &mut i32, so deref to write
    }
    println!("after edit: {counts:?}"); // [10, 20, 30]

    // into_iter() yields T: it consumes the collection and hands you each value.
    let owned = vec![String::from("x"), String::from("y")];
    for s in owned.into_iter() {
        println!("own {s}"); // s is String, moved out of the Vec
    }
    // owned is gone now; using it here would not compile.
}

The iter() loop reads each name and then prints names.len() afterward, which only compiles because iter() merely borrowed: names is still alive. The iter_mut() loop binds each c as &mut i32, so *c *= 10 writes back through the borrow and the original counts ends up [10, 20, 30]. The into_iter() loop moves each String out of owned, so after the loop owned is gone; the comment marks the line that would not compile.

You have written for x in something since chapter one of this book, and it has been an iterator the entire time. The for loop is syntactic sugar, a convenient spelling the compiler rewrites into something simpler. The rewrite has exactly two moves: call into_iter() on the thing you are looping over to get an iterator, then call next() in a loop until it returns None. That is the entire definition of for. Run this to see the sugar and its expansion produce the same line:

// `for x in thing` is sugar: the compiler calls thing.into_iter(), then loops
// on next() until it returns None. Here are both, side by side, same result.
fn main() {
    let v = vec![10, 20, 30];

    // The sugar you normally write.
    print!("for loop:  ");
    for x in &v {
        print!("{x} ");
    }
    println!();

    // What the compiler turns it into. (&v).into_iter() yields &i32, exactly
    // like the loop above, and we pull by hand with next() until None.
    print!("desugared: ");
    let mut it = (&v).into_iter();
    while let Some(x) = it.next() {
        print!("{x} ");
    }
    println!();
}

The first loop is what you write. The second is what the compiler writes for you: (&v).into_iter() turns the collection into an iterator, and the while let Some(x) pulls until the iterator is empty. They print identically because they are identical; the for form is just easier on the eye. This also explains a detail you may have wondered about: for x in &v borrows (because into_iter on a &Vec yields &T), while for x in v consumes (because into_iter on a Vec by value yields T). The & you reach for is choosing which of the three forms from section 05 the loop uses.

One small but useful fact falls out of this. The trait that makes for work is IntoIterator, not Iterator directly. They are related: every Iterator is also IntoIterator (its into_iter just returns itself), which is why you can write for n in fib().take(8) in the next section over a value that is already an iterator. So you only ever need to implement Iterator; the IntoIterator that for wants comes along for free.

Here is where the small trait pays off enormously. Implement the one required method, next(), on a type of your own, and that type becomes a full iterator: usable in for, and usable with every adapter and consumer in the standard library, none of which you had to write. This is the same promise III.10 made about traits, now cashed in. The example below is an endless stream of Fibonacci numbers. Run it:

// Implement Iterator once, and `for` plus every adapter works on your type.
struct Fib {
    current: u64,
    next: u64,
}

fn fib() -> Fib {
    Fib { current: 0, next: 1 }
}

impl Iterator for Fib {
    // The associated type from III.10: each pull yields one u64.
    type Item = u64;

    // The single required method. Compute one number, advance the state,
    // and hand the number back wrapped in Some. This stream never ends,
    // so it never returns None: take() is what keeps it finite.
    fn next(&mut self) -> Option<u64> {
        let value = self.current;
        self.current = self.next;
        self.next = value + self.next;
        Some(value)
    }
}

fn main() {
    // for works, because Fib is already an Iterator (so into_iter is trivial).
    print!("first eight: ");
    for n in fib().take(8) {
        print!("{n} ");
    }
    println!();

    // And so does every adapter and consumer, for free:
    let sum_even: u64 = fib().take(10).filter(|n| n % 2 == 0).sum();
    println!("sum of even among first ten: {sum_even}");
}

Fib is an ordinary struct holding two numbers of state. The whole iterator-ness lives in the impl block. type Item = u64 fills in the associated type from section 02: each pull yields a u64. Then next() does the one job it must: compute the current Fibonacci number, advance the state, and return the number in Some. That is all you wrote, and yet for n in fib().take(8) works, filter works, and sum works, because each of them is a default method built on the next() you just supplied.

Look at what this iterator never does: it never returns None. Fib is an infinite stream, a perfectly legal thing to be, precisely because nothing computes it until something pulls. The finiteness comes from the outside: take(8) pulls eight times and then stops, so the endless source is tamed by a lazy adapter rather than by the source knowing when to quit. An eager language could not hand you an infinite list; laziness is what makes Fib both infinite and useful.

A fair worry, looking at a chain like iter().filter(...).map(...).sum(), is that you are paying for it. Four iterators wrapping each other, a closure call per item per layer, surely that is slower than a plain hand-written loop. In Rust it is not. The chain compiles to the same machine code as the loop you would write by hand. Run this, which computes the same total two ways and asserts they match:

// The chain and the hand-written loop compile to the same tight machine code.
// Adapters are generic and monomorphized (III.09), so each closure inlines and
// the layers of "iterator wrapping iterator" vanish. No per-item overhead.
fn main() {
    let data = [4, 9, 1, 16, 25, 2];

    // The expressive version: a lazy chain ended by one consumer.
    let chained: u32 = data
        .iter()
        .filter(|&&n| n > 3)
        .map(|&n| n * 2)
        .sum();

    // The version you might write in C: one loop, one accumulator.
    let mut by_hand: u32 = 0;
    for &n in data.iter() {
        if n > 3 {
            by_hand += n * 2;
        }
    }

    // Same answer, and after optimization, the same instructions.
    println!("chained {chained}");
    println!("by hand {by_hand}");
    assert_eq!(chained, by_hand);
    println!("identical, and zero-cost");
}

Both halves print 108 and the assert_eq! passes, but the real claim is stronger than “same answer.” After optimization the two compile to essentially identical instructions. The reason is the one from III.09: monomorphization. Every adapter is generic over its closure, and the compiler stamps out a concrete, specialized version for the exact closures you passed, with no dynamic dispatch. Each closure body then inlines into the loop, the layers of “iterator wrapping iterator” collapse, and what is left is one tight loop over the data. The abstraction is real at the source level and gone at the machine level.

This is why idiomatic Rust reaches for iterators without a second thought. In a language where map and filter allocate intermediate arrays and box closures, a hot loop is a good reason to drop down to indices by hand. In Rust there is no such tradeoff: the readable chain and the fast loop are the same artifact, so you almost never give up one to get the other.

Two more useful adapters and two consumers round out the working set, and they all rest on exactly the mechanism you now understand. Run this last program, then we will name the pieces:

// enumerate pairs each item with its index; zip walks two iterators in step.
fn main() {
    let stages = ["fetch", "build", "test"];

    // enumerate yields (index, item). No manual counter, no off-by-one.
    for (i, stage) in stages.iter().enumerate() {
        println!("step {i}: {stage}");
    }

    // zip walks two iterators together, stopping when the shorter one ends.
    let names = ["ada", "alan", "grace"];
    let years = [1815, 1912]; // one shorter on purpose
    let paired: Vec<(&str, i32)> = names.iter().copied().zip(years).collect();
    println!("{paired:?}"); // grace dropped: zip stops at the shorter

    // fold threads an accumulator through every item: start at 0, add each.
    let total = [3, 7, 2].iter().fold(0, |acc, &n| acc + n);
    println!("fold total {total}"); // 12

    // for_each is a consumer for side effects: no value collected, just run.
    [1, 2, 3].iter().for_each(|n| print!("{n}."));
    println!();
}

enumerate is the adapter that pairs each item with its running index, yielding (index, item), so you never hand- roll a counter and never miscount. zip is the adapter that walks two iterators in lockstep, yielding pairs and stopping the moment the shorter one runs dry, which is why grace drops out with only two years to pair against. fold is the consumer that threads an accumulator through every item, starting from a seed, and it is the general shape that sum and count are special cases of. for_each is the consumer for pure side effects, the chain-ending twin of a for loop.

All of it is the pull from section 01. An iterator is a value you call next() on; the trait that defines it asks for that one method and gives you everything else; adapters stay lazy and chain; consumers pull and finish; the three forms choose your borrow; and for was this all along. The full catalog of adapters, and the shared shape that makes them compose so cleanly, you will meet again in Part IV, where the standard library and the monads chapter give the pattern its name and its laws. This chapter was the machine underneath.