5.5 · Creating Iterators: once, empty, repeat, successors, from_fn

Domain 5 — Iterators and Lazy Computation Duration: ~15 minutes Library components: std::iter::once, std::iter::empty, std::iter::repeat, std::iter::successors, std::iter::from_fn, std::iter::IntoIterator

Introduction

Until now, each pipeline started from a collection. This tutorial explains how to create iterators without a collection: from one value, from a closure, or from a seed and a rule.

• The std::iter factory functions make the small cases in one line each.
• IntoIterator explains why for loops accept all of them.
• Your own Iterator implementation is the last step. You write one next() method and get the full adapter library.

The topics of this tutorial are:

• The factory functions: once, once_with, empty, repeat, repeat_with, repeat_n, successors, and from_fn. The RepeatN type of repeat_n implements Default since 1.97. A note covers the unstable from_coroutine.
• IntoIterator: the desugaring of for, and the three forms (T, &T, &mut T).
• How to implement Iterator and IntoIterator for your own types.

Choosing a Factory

Figure: Which factory function do you need?

Each of these functions returns a real iterator. You can use it with all the adapters and consumers from Tutorials 5.1–5.4.

once, once_with, empty

05_15_once_empty_repeat.rs makes a CSV report from these three smallest sources:

// `iter` is `std::iter`. `rows` is the array ["alpha,3", "beta,7"].
// once: adds one value to a stream. Here it puts a header row before the data rows.
let report: Vec<&str> = iter::once("name,count").chain(rows).collect();
// report is ["name,count", "alpha,3", "beta,7"]

// once_with: the closure runs when a consumer takes the item, not at construction.
// `built` is a Cell<bool> that starts as false. It records the closure call.
let footer = iter::once_with(|| {
    built.set(true);
    "-- end of report --"
});
assert!(!built.get());   // the closure did not run yet
let full: Vec<&str> = report.iter().copied().chain(footer).collect();
assert!(built.get());    // collect consumed the footer and ran the closure

// empty: zero items of a specified type. It is the identity element for chain.
let extra_rows = iter::empty::<&str>();

Use once to put a sentinel value before or after a stream. You do not allocate a Vec of one element. once_with applies the lazy evaluation of Tutorial 5.1 to the creation of values, not only to their transformation. empty is useful in generic code where a branch has no items to add but the types must agree.

repeat, repeat_with, repeat_n

Three functions repeat a value:

• repeat(v) clones v without end. The iterator is infinite, so always use it with take, zip, or a different adapter that sets a limit. A typical use fills a column to a constant width: cells.chain(iter::repeat("·")).take(width).
• repeat_with(f) calls a closure for each item. It has no Clone bound. Thus it can make values that must be distinct (new buffers) or sequences with state (an ID counter that the closure captures).
• repeat_n(v, n) yields exactly n copies, and its type implements more traits. RepeatN implements ExactSizeIterator and DoubleEndedIterator, which an infinite Repeat cannot implement. Thus len(), rev(), and a collect with one allocation are all available. For the last item, it moves the value out and does not clone it again.

New in 1.97: RepeatN implements Default, and the default value is an iterator that is already exhausted. It is the correct placeholder with no items for struct fields and for exchanges in the style of mem::take:

// The default RepeatN has no items to yield.
let drained: iter::RepeatN<&str> = iter::RepeatN::default();
assert_eq!(drained.len(), 0);

05_15_once_empty_repeat.rs prints:

report: ["name,count", "alpha,3", "beta,7"]
padded column: ["a", "bb", "·", "·"]
RepeatN::default() is an exhausted repeater (new in 1.97)

All assertions passed.

successors and from_fn

These two functions make the sequences that the factory functions with a predefined shape cannot make.

successors(seed, f): the closure calculates each value from the previous value, and None ends the sequence. The closure returns Option, so you can use an API that already returns Option with no adapter code. 05_16_successors_from_fn.rs has two examples that are similar to production code:

// Powers of two. checked_mul returns None on overflow, and None ends the sequence.
let powers: Vec<u32> = iter::successors(Some(1_u32), |&p| p.checked_mul(2)).collect();
assert_eq!(powers.len(), 32);   // 1, 2, 4, ..., 2^31

// A walk through the ancestor directories: cargo finds the nearest Cargo.toml this way.
// start: &Path = Path::new("/work/app/src/bin")
// dirs_with_manifest: [&Path; 1] contains "/work/app" (a simulated file lookup)
let project_root = iter::successors(Some(start), |dir| dir.parent())
    .find(|dir| dirs_with_manifest.contains(dir));
assert_eq!(project_root, Some(Path::new("/work/app")));

from_fn(f): the closure is the iterator, and its captured variables are the state. A Fibonacci sequence needs no struct. from_fn together with by_ref from Tutorial 5.3 gives the batching pattern (database inserts in chunks):

// `source` is the mutable iterator (1..=8).peekable().
let batches: Vec<Vec<u32>> = iter::from_fn(|| {
    // by_ref borrows `source`, so take(3) removes only the next three items.
    let batch: Vec<u32> = source.by_ref().take(3).collect();
    // An empty batch means that `source` has no more items: end the sequence.
    if batch.is_empty() { None } else { Some(batch) }
}).collect();
// batches is [[1, 2, 3], [4, 5, 6], [7, 8]]

General rule: if the next value is a function of the previous value, use successors (the state is visible in the stream). If the state is auxiliary (counters, buffers, handles), use from_fn, and the closure owns the state. On nightly, iter::from_coroutine would let a coroutine that uses yield do this task. On stable 1.99, use from_fn.

IntoIterator: Why for Loops Work

for is not a special mechanism. It is a trait call. for job in queue { ... } desugars to approximately this code:

// into_iter converts `queue` into an iterator one time, before the loop.
let mut it = IntoIterator::into_iter(queue);
// The loop calls next() until next() returns None.
while let Some(job) = it.next() { ... }

05_17_into_iterator_for_loops.rs runs the desugared form manually and verifies that the two forms give the same result. Three facts follow from the desugaring:

• The expression after in selects the impl. Vec<T> implements IntoIterator three times:

  • for x in v moves and consumes the Vec (Item = T).
  • for x in &v borrows (Item = &T).
  • for x in &mut v lets you change the elements in place (Item = &mut T).

  The methods into_iter(), iter(), and iter_mut() correspond to these three forms, in this sequence.

• Arrays iterate by value since Rust 1.53: for code in [200_u32, 404, 500] yields u32, not &u32. The method call array.into_iter() yields values since edition 2021.

• Every Iterator is IntoIterator (the blanket impl returns self). Thus for x in data.iter().filter(...) compiles directly. You can also pass a partial pipeline to each API that has an IntoIterator bound.

That bound is the most flexible signature for a function that takes a group of items:

// I can be any type that converts into an iterator of u32.
fn total_cost<I: IntoIterator<Item = u32>>(jobs: I) -> u32 {
    jobs.into_iter().sum()
}
total_cost(vec![3, 4, 5]);            // Vec: returns 12
total_cost([3, 4, 5]);                // array: returns 12
total_cost(1..=4);                    // range: returns 10
total_cost((1..=4).filter(|n| n % 2 == 0)); // pipeline: returns 6

Implementing Iterator for Custom Types

The trait has one required method, and that method is all that you must write. 05_18_custom_iterator.rs makes a Deltas iterator that moves a window along a price series. It yields the change between consecutive samples. Its only cursor state is a slice that becomes shorter:

// Deltas<'a> has one field, `remaining: &'a [i64]`: the prices that it did not consume yet.
impl Iterator for Deltas<'_> {
    type Item = i64;
    fn next(&mut self) -> Option<i64> {
        // The slice pattern needs two prices. With fewer than two, the iteration ends.
        let [a, b, ..] = self.remaining else { return None };
        let delta = b - a;
        self.remaining = &self.remaining[1..];   // b becomes the `a` of the next pair
        Some(delta)
    }
    fn size_hint(&self) -> (usize, Option<usize>) { /* exact, see Tutorial 5.4 */ }
}

Immediately, the provided methods are available. The trait has about 75 of them, and 60 are stable in 1.99. Examples are series.deltas().max(), .filter(...).count(), and .scan(...) for cumulative moves.

Add impl IntoIterator for &PriceSeries (it returns Deltas), and a for loop accepts the type itself: for delta in &series. Each API with an IntoIterator bound from the previous slide also accepts it. Most custom collections start with the impl for &T, which borrows. Vec has the same impl.

05_18_custom_iterator.rs prints:

deltas: [25, -15, 60, -30]
cumulative moves: [25, 10, 70, 40]
down moves: 2
net change: 40 cents

All assertions passed.

Summary

Code Examples