🎬 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

285: Building Custom Iterator Adapters

Difficulty: 3 Level: Advanced Wrap an existing iterator in a struct to transform its output — the same pattern used by `map`, `filter`, and `zip` in the standard library.

The Problem This Solves

You've written the same `.filter(...).map(...).step_by(...)` chain in five places in your codebase. Or you need a transformation that doesn't exist in the standard library — emitting adjacent pairs, sampling every Nth element, annotating elements with their distance from a reference point. You could write a function that returns a `Vec`, but that forces eager evaluation and allocates even when your caller might only need the first element. The iterator adapter pattern solves this: wrap your transformation in a struct that holds the inner iterator, then implement `Iterator` on it. Your adapter is now lazy, composable, and chains seamlessly with every other iterator adapter. This is exactly how `std::iter::Map`, `std::iter::Filter`, and `std::iter::Zip` are implemented in the standard library. The extension trait pattern (adding your adapter as a method on all iterators via a trait) makes the API ergonomic — callers write `.every_nth(3)` instead of `EveryNth::new(iter, 3)`.

The Intuition

An iterator adapter is a struct `MyAdapter<I>` that wraps an inner iterator `I: Iterator` and transforms what `next()` returns. Implement `Iterator for MyAdapter<I>` — call `self.inner.next()` internally, apply your transformation, and return the result.

struct MyAdapter<I> { inner: I }
impl<I: Iterator> Iterator for MyAdapter<I> {
 type Item = I::Item;  // (or a different type)
 fn next(&mut self) -> Option<I::Item> {
     self.inner.next().map(|x| transform(x))
 }
}

How It Works in Rust

// Adapter 1: yield every Nth element
struct EveryNth<I> { inner: I, n: usize, count: usize }

impl<I: Iterator> Iterator for EveryNth<I> {
 type Item = I::Item;
 fn next(&mut self) -> Option<I::Item> {
     loop {
         let item = self.inner.next()?;  // ? propagates None (exhausted)
         let emit = self.count % self.n == 0;
         self.count += 1;
         if emit { return Some(item); }
         // otherwise loop: skip this element, try the next
     }
 }
}

// Adapter 2: yield adjacent pairs (sliding window of 2)
struct Pairs<I: Iterator> { inner: I, prev: Option<I::Item> }

impl<I: Iterator> Iterator for Pairs<I> where I::Item: Clone {
 type Item = (I::Item, I::Item);
 fn next(&mut self) -> Option<Self::Item> {
     let next = self.inner.next()?;
     let prev = self.prev.replace(next.clone())?;  // swap prev with next
     Some((prev, next))
 }
}

// Extension trait: add adapters as methods on all iterators
trait IteratorExt: Iterator + Sized {
 fn every_nth(self, n: usize) -> EveryNth<Self> {
     EveryNth { inner: self, n, count: 0 }
 }
 fn pairs(self) -> Pairs<Self> where Self::Item: Clone {
     let mut inner = self;
     let prev = inner.next();  // prime with first element
     Pairs { inner, prev }
 }
}
impl<I: Iterator> IteratorExt for I {}  // blanket impl for all iterators

// Usage: chain custom adapters with standard ones
let thirds: Vec<i32> = (0..12).every_nth(3).collect();
// → [0, 3, 6, 9]

let pairs: Vec<(i32, i32)> = [10, 20, 30, 40, 50].iter().copied().pairs().collect();
// → [(10,20), (20,30), (30,40), (40,50)]

// Adapters compose with each other and with standard adapters
let result: Vec<(i32, i32)> = (0i32..20).every_nth(2).pairs().collect();

What This Unlocks

Reusable lazy transformations — package any multi-step adapter chain into a named, composable unit.
Library-quality API — expose your domain's natural iteration patterns as chainable methods on all iterators.
Zero-allocation pipelines — adapters are structs on the stack; no `Vec` is created until `.collect()`.

Key Differences

Concept	OCaml	Rust
Custom adapter	Higher-order function over `Seq`	Struct + `impl Iterator`
Extension method	Module or `	>` pipeline	Extension trait with blanket impl
Lazy by default	`Seq` is lazy, `List` is not	All iterators are lazy
Composability	`Seq` functions compose via `	>`	All adapters chain via method calls
Type	`'a Seq.t -> 'b Seq.t`	`AdapterStruct<I>` where `I: Iterator`

//! 285. Building custom iterator adapters
//!
//! Custom adapters wrap an iterator in a struct and implement `Iterator` on it.

/// Yields every nth element starting from the first
struct EveryNth<I> {
    inner: I,
    n: usize,
    count: usize,
}

impl<I: Iterator> EveryNth<I> {
    fn new(inner: I, n: usize) -> Self {
        EveryNth { inner, n, count: 0 }
    }
}

impl<I: Iterator> Iterator for EveryNth<I> {
    type Item = I::Item;

    fn next(&mut self) -> Option<I::Item> {
        loop {
            let item = self.inner.next()?;
            let emit = self.count % self.n == 0;
            self.count += 1;
            if emit {
                return Some(item);
            }
        }
    }
}

/// Yields adjacent pairs (a, b) as a sliding window of 2
struct Pairs<I: Iterator> {
    inner: I,
    prev: Option<I::Item>,
}

impl<I: Iterator> Pairs<I>
where I::Item: Clone
{
    fn new(mut inner: I) -> Self {
        let prev = inner.next();
        Pairs { inner, prev }
    }
}

impl<I: Iterator> Iterator for Pairs<I>
where I::Item: Clone
{
    type Item = (I::Item, I::Item);

    fn next(&mut self) -> Option<Self::Item> {
        let next = self.inner.next()?;
        let prev = self.prev.replace(next.clone())?;
        Some((prev, next))
    }
}

// Extension trait to add our adapters to all iterators
trait IteratorExt: Iterator + Sized {
    fn every_nth(self, n: usize) -> EveryNth<Self> {
        EveryNth::new(self, n)
    }
    fn pairs(self) -> Pairs<Self> where Self::Item: Clone {
        Pairs::new(self)
    }
}
impl<I: Iterator> IteratorExt for I {}

fn main() {
    // every_nth adapter
    let thirds: Vec<i32> = (0..12).every_nth(3).collect();
    println!("Every 3rd: {:?}", thirds);

    // pairs adapter
    let data = [10i32, 20, 30, 40, 50];
    let adjacent: Vec<(i32, i32)> = data.iter().copied().pairs().collect();
    println!("Adjacent pairs: {:?}", adjacent);

    // Chain custom adapters
    let result: Vec<(i32, i32)> = (0i32..20)
        .every_nth(2)
        .pairs()
        .collect();
    println!("Every 2nd, then pairs: {:?}", result);
}

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

    #[test]
    fn test_every_nth_3() {
        let result: Vec<i32> = (0..9).every_nth(3).collect();
        assert_eq!(result, vec![0, 3, 6]);
    }

    #[test]
    fn test_pairs() {
        let result: Vec<(i32, i32)> = [1i32,2,3,4].iter().copied().pairs().collect();
        assert_eq!(result, vec![(1,2),(2,3),(3,4)]);
    }

    #[test]
    fn test_every_nth_1_identity() {
        let result: Vec<i32> = [1i32,2,3].iter().copied().every_nth(1).collect();
        assert_eq!(result, vec![1,2,3]);
    }
}

(* 285. Building custom iterator adapters - OCaml *)

(* Custom adapter: every_nth -- yield every nth element *)
let every_nth n seq =
  Seq.unfold (fun (i, rest) ->
    let rec skip_to k s =
      if k = 0 then
        match Seq.uncons s with
        | Some (v, rest') -> Some (v, (n-1, rest'))
        | None -> None
      else
        match Seq.uncons s with
        | Some (_, rest') -> skip_to (k-1) rest'
        | None -> None
    in
    skip_to i rest
  ) (0, seq)

(* Custom adapter: running_window -- sliding running tuple *)
let pairs seq =
  Seq.unfold (fun s ->
    match Seq.uncons s with
    | None -> None
    | Some (a, rest) ->
      match Seq.uncons rest with
      | None -> None
      | Some (b, _) -> Some ((a, b), Seq.drop 1 s)
  ) seq

let () =
  let nums = List.to_seq [1; 2; 3; 4; 5; 6; 7; 8; 9; 10] in
  let thirds = every_nth 3 nums in
  Printf.printf "Every 3rd: %s\n"
    (String.concat ", " (List.map string_of_int (List.of_seq thirds)));

  let data = List.to_seq [10; 20; 30; 40; 50] in
  let adjacent = pairs data in
  List.iter (fun (a, b) -> Printf.printf "(%d,%d) " a b) (List.of_seq adjacent);
  print_newline ()