🎬 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

284: FusedIterator

Difficulty: 3 Level: Advanced A zero-cost marker trait that guarantees your iterator returns `None` forever once it first returns `None` — enabling optimizer skips and safe adapter composition.

The Problem This Solves

The `Iterator` contract says: once `next()` returns `None`, all future calls should return `None`. But this is a convention, not enforced by the type system. A buggy or deliberately weird iterator can return `Some` after returning `None` — and some iterator adapters have to guard against this with extra checks. `FusedIterator` is the compiler-enforced version of that guarantee. Once you implement it on your type, the optimizer knows it can eliminate redundant "is this iterator done?" checks in adapter pipelines. More practically, it's a signal to callers: "this iterator terminates cleanly, you don't need to worry about use-after-done weirdness." All standard library iterators already implement `FusedIterator`. When writing custom iterators that naturally terminate (counters, finite sequences, data readers), implementing it costs nothing and gives your users the same guarantee. If you have a non-fused iterator and need a fused wrapper, `.fuse()` wraps it in an adapter that tracks the first `None` and returns `None` forever after.

The Intuition

A marker trait that promises "once I return `None`, I'll return `None` on every subsequent call" — letting adapters skip redundant termination checks.

How It Works in Rust

use std::iter::FusedIterator;

struct Countdown { n: i32 }

impl Iterator for Countdown {
 type Item = i32;
 fn next(&mut self) -> Option<i32> {
     if self.n <= 0 { return None; }  // once None...
     let val = self.n;
     self.n -= 1;
     Some(val)
 }
}

// Declare that Countdown never returns Some after returning None
impl FusedIterator for Countdown {}  // empty impl — just the marker

// Now callers have the guarantee:
let mut cd = Countdown::new(3);
cd.next();  // Some(3)
cd.next();  // Some(2)
cd.next();  // Some(1)
cd.next();  // None
cd.next();  // None — guaranteed by FusedIterator
cd.next();  // None — always

// Non-fused iterator: can return Some after None (surprising!)
// Use .fuse() to wrap any iterator with the guarantee:
let safe = weird_iterator.fuse();
while let Some(x) = safe.next() { /* ... */ }
safe.next();  // None, guaranteed — even if weird_iterator would have returned Some

// All std iterators are already fused:
let mut v = vec![1, 2, 3].into_iter();
v.next(); v.next(); v.next();
v.next();  // None
v.next();  // None — fused

What This Unlocks

Custom iterator correctness: Mark your counters, readers, and generators as `FusedIterator` to give callers the standard guarantee — costs nothing to implement.
Optimizer hints: Iterator adapters can skip the "check if done" step for fused iterators, reducing branching in hot loops.
Safe composition: `.fuse()` wraps any iterator as a safety net when you're unsure whether a third-party iterator is well-behaved after termination.

Key Differences

Concept	OCaml	Rust
Termination guarantee	Convention only	`FusedIterator` marker trait
Enforcement	Not enforced by type system	Compiler-checked via trait
Standard iterators	All well-behaved (convention)	All implement `FusedIterator`
Custom iterators	Programmer's responsibility	`impl FusedIterator for MyIter {}` — empty impl
Safety wrapper	N/A	`.fuse()` adapter

//! 284. FusedIterator for terminated sequences
//!
//! `FusedIterator` guarantees: once `next()` returns `None`, all future calls also return `None`.

use std::iter::FusedIterator;

/// A non-fused iterator (bad: returns Some after None)
struct FlickyIter {
    count: i32,
}

impl Iterator for FlickyIter {
    type Item = i32;
    fn next(&mut self) -> Option<i32> {
        self.count += 1;
        if self.count == 3 {
            None // returns None once...
        } else if self.count < 6 {
            Some(self.count) // then Some again! (not fused)
        } else {
            None
        }
    }
}

/// A properly fused iterator
struct Countdown {
    n: i32,
}

impl Countdown {
    fn new(n: i32) -> Self { Countdown { n } }
}

impl Iterator for Countdown {
    type Item = i32;
    fn next(&mut self) -> Option<i32> {
        if self.n <= 0 {
            return None;
        }
        let val = self.n;
        self.n -= 1;
        Some(val)
    }
}

// Declare that Countdown is fused — once None, always None
impl FusedIterator for Countdown {}

fn main() {
    // Non-fused behavior (surprising!)
    let mut flicky = FlickyIter { count: 0 };
    let results: Vec<_> = std::iter::from_fn(|| flicky.next()).take(8).collect();
    println!("Flicky results: {:?}", results);

    // Fused behavior: None then always None
    let mut cd = Countdown::new(3);
    println!("{:?} {:?} {:?} {:?} {:?}",
        cd.next(), cd.next(), cd.next(), cd.next(), cd.next());

    // All std iterators are fused
    let v = vec![1i32, 2, 3];
    let mut it = v.into_iter();
    assert_eq!(it.next(), Some(1));
    assert_eq!(it.next(), Some(2));
    assert_eq!(it.next(), Some(3));
    assert_eq!(it.next(), None);
    assert_eq!(it.next(), None); // fused: stays None

    // fuse() adapter wraps any iterator to guarantee fusing
    let mut fused_flicky = FlickyIter { count: 0 }.fuse();
    let results: Vec<_> = std::iter::from_fn(|| fused_flicky.next()).take(8).collect();
    println!("Fused flicky: {:?}", results);
}

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

    #[test]
    fn test_countdown_fused() {
        let mut cd = Countdown::new(3);
        assert_eq!(cd.next(), Some(3));
        assert_eq!(cd.next(), Some(2));
        assert_eq!(cd.next(), Some(1));
        assert_eq!(cd.next(), None);
        assert_eq!(cd.next(), None); // stays None
    }

    #[test]
    fn test_fuse_adapter() {
        let mut it = FlickyIter { count: 0 }.fuse();
        while it.next().is_some() {}
        assert_eq!(it.next(), None); // .fuse() guarantees this
    }

    #[test]
    fn test_collect_countdown() {
        let result: Vec<i32> = Countdown::new(5).collect();
        assert_eq!(result, vec![5, 4, 3, 2, 1]);
    }
}

(* 284. FusedIterator for terminated sequences - OCaml *)
(* OCaml Seq.t is naturally fused — once None, stays None *)

(* An unfused iterator that might return Some after None (bad practice) *)
let unfused_bad =
  let count = ref 0 in
  let limit = ref 3 in
  Seq.unfold (fun () ->
    incr count;
    if !count > !limit then begin
      (* Bad: could reset and return Some again *)
      None
    end else
      Some (!count, ())
  ) ()

let () =
  (* OCaml Seq is lazy and effectively fused by convention *)
  let fused = Seq.take 5 (Seq.of_list [1; 2; 3]) in
  List.iter (fun x -> Printf.printf "%d " x) (List.of_seq fused);
  print_newline ();

  (* Creating a guaranteed-terminating sequence *)
  let countdown n =
    Seq.unfold (fun i -> if i <= 0 then None else Some (i, i-1)) n
  in
  List.iter (fun x -> Printf.printf "%d " x) (List.of_seq (countdown 5));
  print_newline ()