🎬 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

287: Recursive Sequences with successors()

Difficulty: 2 Level: Intermediate Generate a sequence where each element is computed from the previous one — powers, Collatz, Newton's method.

The Problem This Solves

Many sequences are defined recursively: each term is a function of the previous term. Powers of 2 (`n → 2n`). The Collatz sequence (`n → n/2` if even, `3n+1` if odd). Newton-Raphson iterations converging to a root. A string shrinking by one character at a time. `from_fn` handles stateful generators, but when each new value is purely derived from the previous one, `successors` is more expressive. You provide the first element and a function `f(prev) -> Option<next>`. Returning `None` terminates the sequence. There's no mutable state to manage — the function receives the previous value directly. In Haskell this is `iterate` (infinite) or `unfoldr` (with termination). In OCaml it's `Seq.unfold`. In Rust, `std::iter::successors` is the precise match.

The Intuition

`successors(first, f)` generates: `first, f(first), f(f(first)), ...` — applying `f` repeatedly. Return `None` from `f` to stop. The first element is `Option<T>` — pass `None` to get an empty iterator.

let powers: Vec<u32> = std::iter::successors(Some(1u32), |&n| Some(n * 2))
 .take(8).collect();
// → [1, 2, 4, 8, 16, 32, 64, 128]

How It Works in Rust

// Powers of 2 — terminate when past 512
let powers_of_2: Vec<u32> = std::iter::successors(Some(1u32), |&n| {
 if n < 512 { Some(n * 2) } else { None }  // None stops the sequence
}).collect();
// → [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]

// Collatz sequence from 6
let collatz: Vec<u64> = std::iter::successors(Some(6u64), |&n| {
 if n == 1 { None }                          // terminate at 1
 else if n % 2 == 0 { Some(n / 2) }
 else { Some(3 * n + 1) }
}).collect();
// → [6, 3, 10, 5, 16, 8, 4, 2, 1]

// Newton's method — converge to sqrt(2)
let sqrt2: Vec<f64> = std::iter::successors(Some(1.0f64), |&x| {
 let next = 0.5 * (x + 2.0 / x);            // Newton step
 if (next - x).abs() < 1e-10 { None }        // converged — stop
 else { Some(next) }
}).collect();
// → [1.0, 1.5, 1.4166..., 1.41421356..., ...]

// Shrinking string — each step removes first character
let shrinking: Vec<String> = std::iter::successors(
 Some("hello".to_string()),
 |s| if s.is_empty() { None } else { Some(s[1..].to_string()) }
).collect();
// → ["hello", "ello", "llo", "lo", "o", ""]

// Empty start — passing None gives an empty iterator
let empty: Vec<i32> = std::iter::successors(None, |&_: &i32| Some(1)).collect();
// → []

The closure receives `&T` (a reference to the previous value), not `T` — destructure with `|&n|` for `Copy` types.

What This Unlocks

Mathematical sequences — powers, geometric series, Collatz, Fibonacci (though `from_fn` is simpler for Fibonacci).
Iterative numerical methods — Newton-Raphson, bisection, any algorithm that refines an estimate step by step.
Shrinking / expanding transformations — progressively modify a structure, emitting each stage.

Key Differences

Concept	OCaml	Rust
Unfold from previous	`Seq.unfold f seed`	`std::iter::successors(first, f)`
Terminate	Return `None` from unfold	Return `None` from `f`
Closure receives	Previous value + seed	Reference to previous value only
vs. `from_fn`	`from_fn` for independent state	`successors` when `next = f(prev)`
Infinite variant	`Seq.iterate f x`	`successors(Some(x), \	&v\	Some(f(v)))`

//! 287. Recursive sequences with successors()
//!
//! `successors(first, f)` generates a sequence: first, f(first), f(f(first)), ...

fn main() {
    // Powers of 2
    let powers_of_2: Vec<u32> = std::iter::successors(Some(1u32), |&n| {
        if n < 512 { Some(n * 2) } else { None }
    }).collect();
    println!("Powers of 2: {:?}", powers_of_2);

    // Collatz sequence from 6
    let collatz: Vec<u64> = std::iter::successors(Some(6u64), |&n| {
        if n == 1 { None }
        else if n % 2 == 0 { Some(n / 2) }
        else { Some(3 * n + 1) }
    }).collect();
    println!("Collatz(6): {:?}", collatz);

    // Geometric sequence (multiply by 3 each step)
    let geometric: Vec<i32> = std::iter::successors(Some(1i32), |&n| {
        if n >= 729 { None } else { Some(n * 3) }
    }).collect();
    println!("Geometric (x3): {:?}", geometric);

    // String processing: repeatedly remove first char
    let shrinking: Vec<String> = std::iter::successors(
        Some("hello".to_string()),
        |s| if s.is_empty() { None } else { Some(s[1..].to_string()) }
    ).collect();
    println!("Shrinking: {:?}", shrinking);

    // Newton's method square root approximation (finite steps)
    let sqrt2_approx: Vec<f64> = std::iter::successors(Some(1.0f64), |&x| {
        let next = 0.5 * (x + 2.0 / x);
        if (next - x).abs() < 1e-10 { None } else { Some(next) }
    }).collect();
    println!("sqrt(2) steps: {:?}", &sqrt2_approx[..sqrt2_approx.len().min(5)]);
    println!("sqrt(2) ≈ {:.10}", sqrt2_approx.last().unwrap());
}

#[cfg(test)]
mod tests {
    #[test]
    fn test_powers_of_2() {
        let result: Vec<u32> = std::iter::successors(Some(1u32), |&n| {
            if n < 16 { Some(n * 2) } else { None }
        }).collect();
        assert_eq!(result, vec![1, 2, 4, 8, 16]);
    }

    #[test]
    fn test_collatz_6() {
        let result: Vec<u64> = std::iter::successors(Some(6u64), |&n| {
            if n == 1 { None }
            else if n % 2 == 0 { Some(n / 2) }
            else { Some(3 * n + 1) }
        }).collect();
        assert_eq!(result, vec![6, 3, 10, 5, 16, 8, 4, 2, 1]);
    }

    #[test]
    fn test_successors_empty_if_first_is_none() {
        let result: Vec<i32> = std::iter::successors(None, |&_n: &i32| Some(1))
            .collect();
        assert!(result.is_empty());
    }
}

(* 287. Recursive sequences with successors() - OCaml *)

let successors first f =
  Seq.unfold (fun state ->
    match state with
    | None -> None
    | Some x -> Some (x, f x)
  ) (Some first)

let () =
  (* Powers of 2 *)
  let powers_of_2 = successors 1 (fun x -> if x < 256 then Some (x * 2) else None) in
  Printf.printf "Powers of 2: %s\n"
    (String.concat ", " (List.map string_of_int (List.of_seq powers_of_2)));

  (* Collatz sequence *)
  let collatz n =
    successors n (fun x ->
      if x = 1 then None
      else if x mod 2 = 0 then Some (x / 2)
      else Some (3 * x + 1)
    )
  in
  Printf.printf "Collatz(6): %s\n"
    (String.concat ", " (List.map string_of_int (List.of_seq (collatz 6))));

  (* Geometric sequence *)
  let geo = successors 1.0 (fun x -> if x > 100.0 then None else Some (x *. 3.0)) in
  Printf.printf "Geometric: %s\n"
    (String.concat ", " (List.map (Printf.sprintf "%.0f") (List.of_seq geo)))