🎬 How Rust Iterators Work Lazy evaluation, chaining, collect(), and zero-cost abstractions.

📝 Text version (for readers / accessibility)

• Iterators are lazy — .map(), .filter(), .take() build a chain but do no work until consumed

• .collect() triggers evaluation, transforming the chain into a Vec, HashMap, or other collection

• Zero-cost abstraction: iterator chains compile to the same machine code as hand-written loops

• .iter() borrows, .into_iter() consumes, .iter_mut() borrows mutably

• Chaining replaces nested loops with a readable, composable pipeline

405: Iterator Adapters and Combinators

Difficulty: 2 Level: Intermediate The full depth of Rust's iterator protocol — implementing custom iterators and composing complex lazy pipelines.

The Problem This Solves

Processing collections is the bulk of most programs. Without a composable abstraction, you write explicit loops, temporary allocations, and imperative index-tracking code that obscures intent. Even with basic `map`/`filter` you hit a ceiling: you need custom step sizes, stateful transformations, early termination, or generating data on the fly. Rust's `Iterator` trait is minimal by design — implement just `next()` and you get the entire adapter ecosystem for free. `map`, `filter`, `flat_map`, `take_while`, `scan`, `zip`, `chain`, and 70+ other adapters compose lazily. Nothing allocates until you call a consuming adapter like `collect()`, `sum()`, or `for_each()`. The entire pipeline is a single zero-allocation state machine. Building your own iterator is how you express domain-specific iteration: Fibonacci sequences, file-line readers, tree traversals, tokenizers. Once it implements `Iterator`, every consumer in the language can use it.

The Intuition

Implement `next()` on your type and you get the whole iterator machinery for free — every adapter, every consumer, all lazy.

How It Works in Rust

// The entire Iterator trait — just one required method
trait Iterator {
 type Item;
 fn next(&mut self) -> Option<Self::Item>;
 // ...100+ provided methods built on next()
}

// Custom iterator: Fibonacci
struct Fib { a: u64, b: u64 }
impl Fib { fn new() -> Self { Fib { a: 0, b: 1 } } }

impl Iterator for Fib {
 type Item = u64;
 fn next(&mut self) -> Option<u64> {
     let next = self.a + self.b;
     self.a = self.b;
     self.b = next;
     Some(self.a)  // infinite — never returns None
 }
}

// Now it works with the whole ecosystem
let sum: u64 = Fib::new().take(10).sum();  // 143
let evens: Vec<u64> = Fib::new().take(20).filter(|x| x % 2 == 0).collect();

// Lazy pipeline — nothing runs until consumed
let pipeline = (1..=1000)
 .filter(|x| x % 3 == 0)
 .map(|x| x * x)
 .take_while(|&x| x < 10_000);
// No work done yet ↑

let result: Vec<i32> = pipeline.collect(); // work happens here

1. Define a struct with iteration state. 2. `impl Iterator for YourStruct` — implement only `next()`. 3. Return `Some(value)` to continue, `None` to end. 4. Compose with any adapter: `.map()`, `.filter()`, `.flat_map()`, `.scan()`.

What This Unlocks

Domain iterators: Express any sequence — ranges, tree nodes, parsed tokens — as a first-class iterator.
Zero-allocation pipelines: Chain 10 adapters; only the final `collect()` allocates.
Infinite iterators: `Fib::new().take(n)` — generate lazily, consume exactly what you need.

Key Differences

Concept	OCaml	Rust
Sequence abstraction	`Seq.t` (lazy), `List.t` (strict)	`Iterator` trait — always lazy
Custom sequence	`let rec gen () = fun () -> Seq.Cons(...)`	`impl Iterator for MyStruct`
Adapter composition	`Seq.map`, `Seq.filter` (limited)	70+ adapters, all composable
Allocation	`List` allocates; `Seq` defers	Adapters zero-alloc; `collect()` allocates
Infinite sequences	`Seq` supports infinite	`Iterator` supports infinite naturally

// Iterator adapters and combinators in Rust

fn main() {
    // Basic pipeline
    let sum_of_squares_of_evens: i32 = (1..=10)
        .filter(|x| x % 2 == 0)
        .map(|x| x * x)
        .sum();
    println!("Sum of squares of evens 1..10: {}", sum_of_squares_of_evens);

    // flat_map
    let pairs: Vec<(i32, i32)> = (1..=4)
        .flat_map(|x| (1..=4).map(move |y| (x, y)))
        .filter(|(x, y)| x < y)
        .collect();
    println!("Pairs (x<y) from 1..4: {} pairs", pairs.len());

    // zip and enumerate
    let names = ["Alice", "Bob", "Carol"];
    let scores = [95, 87, 91];
    names.iter().zip(scores.iter()).enumerate().for_each(|(i, (name, score))| {
        println!("  {}. {}: {}", i + 1, name, score);
    });

    // scan (stateful)
    let running_total: Vec<i32> = (1..=5)
        .scan(0, |state, x| { *state += x; Some(*state) })
        .collect();
    println!("Running total: {:?}", running_total);

    // take_while / skip_while
    let data = vec![1, 3, 5, 2, 4, 6, 1, 2];
    let odds_prefix: Vec<_> = data.iter().take_while(|&&x| x % 2 != 0).collect();
    println!("Odd prefix: {:?}", odds_prefix);

    // chain
    let a = 1..=3;
    let b = 7..=9;
    let chained: Vec<i32> = a.chain(b).collect();
    println!("Chained: {:?}", chained);

    // partition
    let (evens, odds): (Vec<i32>, Vec<i32>) = (1..=10).partition(|x| x % 2 == 0);
    println!("Evens: {:?}", evens);
    println!("Odds: {:?}", odds);

    // unzip
    let (names2, scores2): (Vec<_>, Vec<_>) = vec![("Alice", 95), ("Bob", 87)].into_iter().unzip();
    println!("Names: {:?}, Scores: {:?}", names2, scores2);

    // Custom iterator — Fibonacci
    struct Fib { a: u64, b: u64 }
    impl Iterator for Fib {
        type Item = u64;
        fn next(&mut self) -> Option<u64> {
            let next = self.a + self.b;
            self.a = self.b;
            self.b = next;
            Some(self.a)
        }
    }
    let fibs: Vec<u64> = Fib { a: 0, b: 1 }.take(10).collect();
    println!("Fibonacci: {:?}", fibs);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_filter_map() {
        let v: Vec<i32> = (1..=10).filter(|x| x % 2 == 0).map(|x| x * x).collect();
        assert_eq!(v, vec![4, 16, 36, 64, 100]);
    }

    #[test]
    fn test_flat_map() {
        let v: Vec<i32> = vec![1, 2, 3].into_iter().flat_map(|x| vec![x, x * 10]).collect();
        assert_eq!(v, vec![1, 10, 2, 20, 3, 30]);
    }

    #[test]
    fn test_scan() {
        let r: Vec<i32> = (1..=4).scan(0, |s, x| { *s += x; Some(*s) }).collect();
        assert_eq!(r, vec![1, 3, 6, 10]);
    }
}

(* Iterator combinators in OCaml using Seq *)

let range a b = Seq.init (b - a) (fun i -> a + i)

let () =
  (* Pipeline: range -> filter -> map -> fold *)
  let sum_of_squares_of_evens =
    range 1 11
    |> Seq.filter (fun x -> x mod 2 = 0)
    |> Seq.map (fun x -> x * x)
    |> Seq.fold_left (+) 0
  in
  Printf.printf "Sum of squares of evens 1..10: %d\n" sum_of_squares_of_evens;

  (* flat_map / concat_map *)
  let pairs =
    range 1 4
    |> Seq.flat_map (fun x -> Seq.map (fun y -> (x, y)) (range 1 4))
    |> Seq.filter (fun (x, y) -> x < y)
    |> List.of_seq
  in
  Printf.printf "Pairs (x<y) from 1..3: %d pairs\n" (List.length pairs);

  (* zip *)
  let names = List.to_seq ["Alice"; "Bob"; "Carol"] in
  let scores = List.to_seq [95; 87; 91] in
  Seq.zip names scores
  |> Seq.iter (fun (n, s) -> Printf.printf "  %s: %d\n" n s)