🎬 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

281: Implementing Iterator Trait from Scratch

Difficulty: 3 Level: Advanced Implement `Iterator` on your own struct — one method required, the entire adapter ecosystem unlocked for free.

The Problem This Solves

Your data structure has a natural traversal order, but it's not a slice or a vec. A graph node's BFS frontier. A custom number sequence — squares, Fibonacci, primes. A lazy generator that computes each value on demand. You need these to work with `map`, `filter`, `zip`, `take`, `collect`, and every other iterator tool without reimplementing them. The power of Rust's iterator design is the minimal requirement: implement one method — `next()` — and you immediately get the full iterator toolkit for free. No inheritance hierarchy, no magic traits to satisfy, no runtime dispatch required. The alternative is implementing every transformation yourself, or collecting everything into a `Vec` and using slice iteration — which forces eager evaluation and allocates even when you'd only consume the first few elements.

The Intuition

Implement `Iterator` by defining `type Item` and `fn next(&mut self) -> Option<Self::Item>`. Return `Some(value)` to yield a value, `None` to signal exhaustion.

impl Iterator for MyType {
 type Item = u32;
 fn next(&mut self) -> Option<u32> {
     // compute next value, return Some or None
 }
}
// Now: MyType.map(), .filter(), .zip(), .collect() — all free

How It Works in Rust

struct Squares { current: u32, max: u32 }

impl Squares {
 fn new(max: u32) -> Self { Squares { current: 0, max } }
}

impl Iterator for Squares {
 type Item = u32;

 fn next(&mut self) -> Option<Self::Item> {
     if self.current >= self.max { return None; }
     let val = self.current * self.current;
     self.current += 1;
     Some(val)  // yield square of current position
 }
}

// All iterator adapters work immediately
let squares: Vec<u32> = Squares::new(6).collect();
// → [0, 1, 4, 9, 16, 25]

let sum_of_squares: u32 = Squares::new(6).sum();
// → 55

let big_squares: Vec<u32> = Squares::new(10)
 .filter(|&x| x > 10)
 .collect();
// → [16, 25, 36, 49, 64, 81]

// Infinite iterator — signals infinity by always returning Some
struct Fibonacci { a: u64, b: u64 }
impl Iterator for Fibonacci {
 type Item = u64;
 fn next(&mut self) -> Option<u64> {
     let val = self.a;
     let next = self.a + self.b;
     self.a = self.b;
     self.b = next;
     Some(val)  // never returns None — must use take() to bound
 }
}

let fibs: Vec<u64> = Fibonacci { a: 0, b: 1 }.take(10).collect();
// → [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

// Zip two custom iterators — works because both implement Iterator
let zipped: Vec<(u32, u64)> = Squares::new(5)
 .zip(Fibonacci { a: 0, b: 1 })
 .collect();

What This Unlocks

Lazy sequences — compute values only when consumed; infinite sequences become trivial.
Custom data structure traversal — implement `Iterator` on trees, graphs, or domain objects to integrate with the full Rust ecosystem.
Zero-cost abstractions — custom iterators compile to the same machine code as hand-written loops with no allocation overhead.

Key Differences

Concept	OCaml	Rust
Custom sequence	`Seq.t` (thunk-based) or module	Implement `Iterator` trait
Minimum required	`unit -> 'a Seq.node`	`fn next(&mut self) -> Option<Item>`
Adapters for free	No — separate `Seq.*` functions	Yes — all `Iterator` methods available
Infinite sequences	Natural with `Seq`	Natural — return `Some` forever, bound with `take()`
State storage	Closure captures	Struct fields

//! 281. Implementing Iterator trait from scratch
//!
//! Only `next()` is required — the rest of the iterator API comes for free.

/// A counter that yields squares up to a maximum
struct Squares {
    current: u32,
    max: u32,
}

impl Squares {
    fn new(max: u32) -> Self {
        Squares { current: 0, max }
    }
}

impl Iterator for Squares {
    type Item = u32;

    fn next(&mut self) -> Option<Self::Item> {
        if self.current >= self.max {
            return None;
        }
        let val = self.current * self.current;
        self.current += 1;
        Some(val)
    }
}

/// Fibonacci sequence iterator
struct Fibonacci {
    a: u64,
    b: u64,
}

impl Fibonacci {
    fn new() -> Self {
        Fibonacci { a: 0, b: 1 }
    }
}

impl Iterator for Fibonacci {
    type Item = u64;

    fn next(&mut self) -> Option<Self::Item> {
        let val = self.a;
        let next = self.a + self.b;
        self.a = self.b;
        self.b = next;
        Some(val) // infinite — always Some
    }
}

fn main() {
    // Squares iterator — uses all iterator adapters for free
    let squares: Vec<u32> = Squares::new(6).collect();
    println!("Squares: {:?}", squares);

    let sum_of_squares: u32 = Squares::new(6).sum();
    println!("Sum of squares: {}", sum_of_squares);

    let big_squares: Vec<u32> = Squares::new(10)
        .filter(|&x| x > 10)
        .collect();
    println!("Squares > 10: {:?}", big_squares);

    // Fibonacci — infinite iterator, use take()
    let fibs: Vec<u64> = Fibonacci::new().take(10).collect();
    println!("First 10 Fibonacci: {:?}", fibs);

    let fib_sum: u64 = Fibonacci::new().take(10).sum();
    println!("Sum of first 10 Fibonacci: {}", fib_sum);

    // Zip two custom iterators
    let zipped: Vec<(u32, u64)> = Squares::new(5)
        .zip(Fibonacci::new())
        .collect();
    println!("Squares zip Fibonacci: {:?}", zipped);
}

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

    #[test]
    fn test_squares_collect() {
        let result: Vec<u32> = Squares::new(5).collect();
        assert_eq!(result, vec![0, 1, 4, 9, 16]);
    }

    #[test]
    fn test_squares_sum() {
        let sum: u32 = Squares::new(4).sum();
        assert_eq!(sum, 0 + 1 + 4 + 9);
    }

    #[test]
    fn test_fibonacci_first_10() {
        let result: Vec<u64> = Fibonacci::new().take(10).collect();
        assert_eq!(result, vec![0, 1, 1, 2, 3, 5, 8, 13, 21, 34]);
    }

    #[test]
    fn test_fibonacci_filter() {
        let even_fibs: Vec<u64> = Fibonacci::new()
            .take(10)
            .filter(|x| x % 2 == 0)
            .collect();
        assert_eq!(even_fibs, vec![0, 2, 8, 34]);
    }
}

(* 281. Implementing Iterator trait from scratch - OCaml *)
(* OCaml uses Seq.t for lazy sequences *)

type 'a counter = {
  mutable current: int;
  max: int;
  step: int;
  f: int -> 'a;
}

let make_counter ?(step=1) max f =
  { current = 0; max; step; f }

let counter_next c =
  if c.current >= c.max then None
  else begin
    let v = c.f c.current in
    c.current <- c.current + c.step;
    Some v
  end

let counter_to_seq c =
  Seq.unfold (fun () ->
    counter_next c |> Option.map (fun v -> (v, ()))
  ) ()

let () =
  let c = make_counter 5 (fun i -> i * i) in
  let squares = counter_to_seq c |> List.of_seq in
  Printf.printf "Squares: %s\n"
    (String.concat ", " (List.map string_of_int squares));

  (* Fibonacci sequence as lazy iterator *)
  let fib_seq =
    Seq.unfold (fun (a, b) -> Some (a, (b, a + b))) (0, 1)
  in
  let first10 = Seq.take 10 fib_seq |> List.of_seq in
  Printf.printf "First 10 Fibonacci: %s\n"
    (String.concat ", " (List.map string_of_int first10))