🎬 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

1052: Fibonacci Bottom-Up DP

Difficulty: Beginner Category: Dynamic Programming Concept: Bottom-up tabulation converting recursion to iteration, with O(1) space optimization Key Insight: The fold/iterator approach in both languages elegantly expresses the two-variable optimization as a tuple transformation — `(a, b) → (b, a+b)` — making the state transition explicit and functional.

// 1052: Fibonacci Bottom-Up DP with O(1) Space

// Approach 1: Vec-based bottom-up DP
fn fib_vec(n: usize) -> u64 {
    if n <= 1 {
        return n as u64;
    }
    let mut dp = vec![0u64; n + 1];
    dp[1] = 1;
    for i in 2..=n {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    dp[n]
}

// Approach 2: O(1) space — two variables
fn fib_const(n: usize) -> u64 {
    if n <= 1 {
        return n as u64;
    }
    let (mut a, mut b) = (0u64, 1u64);
    for _ in 2..=n {
        let t = a + b;
        a = b;
        b = t;
    }
    b
}

// Approach 3: Iterator/fold approach
fn fib_fold(n: usize) -> u64 {
    if n <= 1 {
        return n as u64;
    }
    let (_, b) = (2..=n).fold((0u64, 1u64), |(a, b), _| (b, a + b));
    b
}

fn main() {
    for n in [0, 1, 5, 10, 20, 30] {
        println!("fib({}) = {}", n, fib_const(n));
    }
}

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

    const CASES: &[(usize, u64)] = &[
        (0, 0), (1, 1), (2, 1), (5, 5), (10, 55), (20, 6765), (30, 832040),
    ];

    #[test]
    fn test_fib_vec() {
        for &(n, expected) in CASES {
            assert_eq!(fib_vec(n), expected, "fib_vec({n})");
        }
    }

    #[test]
    fn test_fib_const() {
        for &(n, expected) in CASES {
            assert_eq!(fib_const(n), expected, "fib_const({n})");
        }
    }

    #[test]
    fn test_fib_fold() {
        for &(n, expected) in CASES {
            assert_eq!(fib_fold(n), expected, "fib_fold({n})");
        }
    }
}

(* 1052: Fibonacci Bottom-Up DP with O(1) Space *)

(* Approach 1: Array-based bottom-up DP *)
let fib_array n =
  if n <= 1 then n
  else begin
    let dp = Array.make (n + 1) 0 in
    dp.(1) <- 1;
    for i = 2 to n do
      dp.(i) <- dp.(i - 1) + dp.(i - 2)
    done;
    dp.(n)
  end

(* Approach 2: O(1) space — two variables *)
let fib_const n =
  if n <= 1 then n
  else begin
    let a = ref 0 in
    let b = ref 1 in
    for _ = 2 to n do
      let t = !a + !b in
      a := !b;
      b := t
    done;
    !b
  end

(* Approach 3: Functional fold with tuple *)
let fib_fold n =
  if n <= 1 then n
  else
    let (_, b) =
      List.init (n - 1) Fun.id
      |> List.fold_left (fun (a, b) _ -> (b, a + b)) (0, 1)
    in
    b

let () =
  List.iter (fun (n, expected) ->
    assert (fib_array n = expected);
    assert (fib_const n = expected);
    assert (fib_fold n = expected)
  ) [(0, 0); (1, 1); (2, 1); (5, 5); (10, 55); (20, 6765); (30, 832040)];
  Printf.printf "✓ All tests passed\n"

📊 Detailed Comparison

Fibonacci Bottom-Up DP — Comparison

Core Insight

Bottom-up DP eliminates recursion overhead. The O(1) space variant using tuple state `(a, b) → (b, a+b)` is naturally expressed as a fold in both languages, showing how functional patterns align with space-optimal DP.

OCaml Approach

Array-based DP with imperative `for` loop and mutable array
`ref` cells for the two-variable version (imperative in functional clothing)
`List.fold_left` with tuple destructuring for the pure functional version
`List.init` creates the iteration range

Rust Approach

`Vec`-based DP table — explicit allocation, indexed access
Tuple destructuring `let (mut a, mut b)` for O(1) space
`(2..=n).fold((0, 1), |(a, b), _| (b, a+b))` — idiomatic iterator chain
Range iterators are zero-cost abstractions

Comparison Table

Aspect	OCaml	Rust
Array DP	`Array.make n 0`	`vec![0u64; n + 1]`
Mutable vars	`ref` cells + `:=`	`let mut` + `=`
Fold syntax	`List.fold_left (fun (a,b) _ -> ...)`	`(2..=n).fold((0,1), \	(a,b), _\	...)`
Range creation	`List.init (n-1) Fun.id` (allocates list)	`2..=n` (zero-cost iterator)
Space complexity	Same O(1) for both	Same O(1) for both
Overflow handling	Silent overflow (OCaml ints)	Panic on debug, wrap on release