The Iterator Trait

The previous lesson measured when a single closure runs: a stored body did not run at all unless it was called. This lesson carries the same question from a single closure to an entire source. An array, a range, a string — traversing each of these looks like a different operation, but Rust reduces all of them to a single contract: a single call asking for the next value in sequence. This lesson writes that contract itself, and measures that traversal is really just this one call repeated, and that a chain built over a source never enters the run ledger until that call actually arrives. What is measured is not the source’s type or content, but when and how many times the contract’s method runs. This is a natural extension of the closures measurement: there, what determined things was how a single body was stored; here, it is the contract itself, the thing many closures bind together. The contract stays fixed while whoever implements it — an array, a range, or the Counter written in this lesson — can change; the measured count is independent of that choice.

Traversal Reduced to a Single Contract

A for loop, a transformation chain, a summing call — very different-looking forms in the source all reduce underneath to the same one method: ask for the next value, or stop. This method’s name and signature are gathered into a single contract; once a type implements that contract, it becomes traversable. The contract itself says nothing about how the source is stored or how many elements it has — only how it answers “give me the next one.”

The standard library’s own sources (a growable array, a range) already implement this contract, but a counter cannot be placed inside their implementation — there is no way to directly ask how many times the method was called. This is why the run below implements the contract on its own small type: Counter, a source that holds a single count and produces values one at a time. The contract itself is identical to the standard library’s; the only difference is that the method writes to the ledger every time it is called.

CI5. — the claim that “traversing a three-element source visits its contract implementation’s single method four times” is confirmed by the run below.

// counter_iteration.rs — measures that traversal reduces to a single next-value call
use std::cell::RefCell;
use std::collections::BTreeMap;
use std::rc::Rc;

type Ledger = Rc<RefCell<BTreeMap<String, u32>>>;

fn record(ledger: &Ledger, name: &str) {
    *ledger.borrow_mut().entry(name.to_string()).or_insert(0) += 1;
}

fn times(ledger: &Ledger, name: &str) -> u32 {
    *ledger.borrow().get(name).unwrap_or(&0)
}

struct Counter {
    current: u32,
    limit: u32,
    ledger: Ledger,
}

impl Iterator for Counter {
    type Item = u32;
    fn next(&mut self) -> Option<u32> {
        record(&self.ledger, "next-value-call");
        if self.current < self.limit {
            self.current += 1;
            Some(self.current)
        } else {
            None
        }
    }
}

fn main() {
    let ledger: Ledger = Rc::new(RefCell::new(BTreeMap::new()));
    let counter = Counter { current: 0, limit: 3, ledger: Rc::clone(&ledger) };

    let mut total = 0;
    for value in counter {
        total += value;
    }

    println!("total: {}", total);
    println!("next-value call count: {}", times(&ledger, "next-value-call"));
}

total: 6
next-value call count: 4

Counter implements the contract’s single method: if there is a next value it returns it and advances its own state by one, otherwise it returns an empty answer. Though the for loop looks like one piece of syntax in the source, in the run this method is called four times on a three-element Counter: three times with a value, once with the “nothing left” answer. The loop does not stop until it sees this fourth call — it does not count elements itself, it just keeps asking until the answer is empty. The total coming out to six (1 + 2 + 3) and the call count coming out to four are two faces of the same run: one shows the elements’ values, the other shows how many times the contract was exercised. This measurement is not to be confused with the question the JVM, Concurrency and Performance course asks — which thread runs a given step: there is only one thread here, and the only question is how many times the contract ran.

The fourth call is nowhere explicit in the source — the for loop itself produces it, by continuing to ask until it sees “no value left.” This means the traversing side (the loop) does not need to know in advance how many elements the source holds: Counter‘s limit was set to three, but the loop never read that limit, it only followed the answers. The contract keeps the source’s size to itself.

The contract’s single method also does not force the whole source to be traversed — it only advances as far as it is asked. The same Counter, built with a limit of five, is queried only twice below.

CI6. — the claim that “when only the first two values of a five-element source are requested, the contract’s method is called two times, not five” is confirmed by the run below.

// partial_consumption.rs — an iterator can be dropped before it is fully consumed
use std::cell::RefCell;
use std::collections::BTreeMap;
use std::rc::Rc;

type Ledger = Rc<RefCell<BTreeMap<String, u32>>>;

fn record(ledger: &Ledger, name: &str) {
    *ledger.borrow_mut().entry(name.to_string()).or_insert(0) += 1;
}

fn times(ledger: &Ledger, name: &str) -> u32 {
    *ledger.borrow().get(name).unwrap_or(&0)
}

struct Counter {
    current: u32,
    limit: u32,
    ledger: Ledger,
}

impl Iterator for Counter {
    type Item = u32;
    fn next(&mut self) -> Option<u32> {
        record(&self.ledger, "partial-next-value-call");
        if self.current < self.limit {
            self.current += 1;
            Some(self.current)
        } else {
            None
        }
    }
}

fn main() {
    let ledger: Ledger = Rc::new(RefCell::new(BTreeMap::new()));
    let mut counter = Counter { current: 0, limit: 5, ledger: Rc::clone(&ledger) };

    let first = counter.next();
    let second = counter.next();

    println!("first two values: {:?}, {:?}", first, second);
    println!("call count while limit is five: {}", times(&ledger, "partial-next-value-call"));
}

first two values: Some(1), Some(2)
call count while limit is five: 2

counter was built able to advance to five values, but it was only queried explicitly twice, and the remaining three values were never touched — counter is here left to go out of scope without further use. The contract’s method waits for the source to be “asked,” not to be “finished”: the source may hold five elements, but that count only sets an upper bound, it does not determine the call count. This observation sets up the next lesson’s axis in advance: a source’s length and how many times the body running over it runs are not the same number.

In this run the method was called explicitly, on two separate lines; in the previous run the same method was called by a loop. The only difference between the two is who does the calling: in one it is our own main, in the other it is the for loop itself. The contract’s method carries the same signature and answers the same way in both cases — who calls it does not change the contract’s behavior, only where the call appears in the source. This is the full meaning of the contract being “single”: no matter which syntax expresses the traversal, underneath it always comes down to the same method.

This single contract also simplifies converting one form of traversal into another: once a transformation chain or a search call is written, all of it is built on the same contract, with no separate traversal rule to learn. Most of these higher-level methods are default bodies of the kind measured in the Trait Definition and Implementation lesson, the course’s opening lesson — they do not contain a next call themselves, they inherit a ready-made body that calls next over and over; what was measured there was that a default body never runs for a type that overrides it, and what is measured here is the same mechanism’s concrete instance inside the traversal contract. Still, the contract existing does not mean that writing the traversal in the source and it actually happening in the run are the same moment — that distinction is the next measurement’s subject.

A Chain That Is Built But Never Consumed

Defining a transformation over a source is not the same thing as running that transformation. The previous measurement called the contract’s method by hand; this measurement takes on a form seen far more often in source code — a transformation chain — built on the same contract. Writing a transformation chain (.map(...), for instance) is a call that combines a source and a closure and produces a new source; what it produces is itself a value that implements the contract. A line in the course’s measurement core builds a chain that transforms a four-element source but never consumes it anywhere — its result is never handed to a loop, collected into a list, or sent to a summing call. Whether a chain in this state runs at all is an application of lazy evaluation; that concept was established in the Programming Fundamentals course and is not retold here, only how many times it ran is counted.

CI7. — the claim that “when the same four-element source is built once without ever being consumed, and once consumed by a summing call, the unconsumed body runs zero times and the consumed one runs four” is confirmed by the run below.

// unconsumed_and_consumed.rs — the same source is built once unconsumed, once consumed
use std::cell::RefCell;
use std::collections::BTreeMap;
use std::rc::Rc;

type Ledger = Rc<RefCell<BTreeMap<String, u32>>>;

fn record(ledger: &Ledger, name: &str) {
    *ledger.borrow_mut().entry(name.to_string()).or_insert(0) += 1;
}

fn times(ledger: &Ledger, name: &str) -> u32 {
    *ledger.borrow().get(name).unwrap_or(&0)
}

fn main() {
    let ledger: Ledger = Rc::new(RefCell::new(BTreeMap::new()));

    // unconsumed: the exact slice from the course's measurement core, never consumed
    let _lazy = vec![1, 2, 3, 4].into_iter().map(|x| {
        record(&ledger, "unconsumed-chain");
        x * 2
    });

    // the same source, this time consumed by a summing call
    let total: i32 = vec![1, 2, 3, 4]
        .into_iter()
        .map(|x| {
            record(&ledger, "consumed-equivalent-chain");
            x * 2
        })
        .sum();

    println!("how many times the unconsumed body ran: {}", times(&ledger, "unconsumed-chain"));
    println!(
        "how many times the consumed body ran: {} (total {})",
        times(&ledger, "consumed-equivalent-chain"),
        total
    );
}

how many times the unconsumed body ran: 0
how many times the consumed body ran: 4 (total 20)

The two chains’ source text starts out identical: the same four-element source, the same transformation body. The difference is only at the end: the first is stored under a name and left as is, the second is handed to a summing call. The unconsumed-chain counter stays at zero for the whole run — this line falls into the never class in the course’s binding table. Once the equivalent chain is consumed, the transformation body runs once for each of the four elements, four times in total. A built chain sitting in the source means that the contract’s “give me the next value” call never arrived; without that call, the body does not run.

The only difference between these two runs is not in the chain’s source text but in what sits at its end. The .sum() call is a consumer that keeps calling the contract’s method until the source runs out; the chain left under the name _lazy has no such consumer at all. Writing a chain’s transformation body is only the precondition for that body entering the run ledger — the sufficient condition is a consumer being attached at the chain’s end.

This difference can be noticed just by reading the source: the underscore leading the name _lazy is there to silence Rust’s “this name is unused” warning — the same mark seen on _closure in the previous lesson. A chain being built and never used leaves a small trace in the source too: a binding whose name is never read. In the consumed chain, by contrast, the result is bound to the name total and read in the print call; the name does not go unused.

A Bounding Measurement

A body counter of zero for an unconsumed chain does not mean that chain is free. The map call builds a structure wrapping the source and the transformation closure; this structure sits in memory under the name _lazy, just like a closure that is never called in the previous lesson. The structure itself is a value and takes up a place — but that placement falls outside the scope of the “how many times did the body run” question the run ledger measures. The ledger only counts calls inside the transformation closure; it does not count the structure the chain occupies at the moment it is built. This lesson does not attempt to measure that cost, it only records that it exists — the same observation as the previous lesson’s bounding measurement, carried from a single closure to a chain of closures.

The same boundary applies to the partial-consumption measurement on Counter. A five-element source having only two values requested and the remaining three never requested means those three were never produced — but the cost of building the source itself was already paid, independent of where this cutoff falls. The measured count reflects the cost of a later request, not the cost of construction.

Together, these two observations draw the boundaries of the “how many times did it run” question: the counter says precisely when the contract’s method was called, but it says nothing about when the structure holding that method was built, or how much space it took. A chain gets built, part of it gets requested, the rest is left unrequested — three separate moments, three separate questions, and the number this lesson measures answers only one of them, the moment of the call. A question that wants to measure construction and space occupied needs a different tool; this course does not write that tool, it only states plainly which question falls outside this number’s scope.

Summary

• Traversing a source reduces to repeatedly revisiting a single method of its own contract; on a three-element source this method is called four times.
• The contract itself is independent of how the source is stored; it only defines how it answers “give me the next one.”
• The unconsumed-chain body from the course’s measurement core did not run in this run — the equivalent consumed source ran four times.
• Building a chain and the chain advancing are separate events; at the moment of building, the contract’s method is never visited at all; if only two values of a five-element source are requested, the contract’s method is also called only twice.
• Lazy evaluation itself was not rebuilt in this lesson; only how many times it ran was counted.
• A built but unconsumed chain is not free — that cost is not what the body’s run counter measures; the counter only measures the moment of the call, not the moment of construction.

Next Step

In this lesson, the difference between a chain never being consumed and being fully consumed was measured over a single transformation step: zero against four. But “consuming” does not carry a single meaning — as the partial-consumption measurement showed, how much of a source is requested also determines how many times the contract’s method is visited. This lesson saw two extremes: never requested (zero) and fully requested (four). The next lesson takes the same source and the same transformation body and attaches different consumers to the end of the chain, and shows that this time it is not the chain’s length but the consumer that determines how many times the body will run — one consumer may want the whole source, another may stop as soon as it finds the first matching value; both will start from the same four-element source, but one will land at one of the extremes, the other somewhere in the middle. Together, these two lessons show that “consuming” actually spans a range from one end to the other: never, partially, fully.