🎬 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

069: Unfold (Anamorphism)

Difficulty: Intermediate Category: Functional Patterns Concept: Generate a sequence from a seed value (dual of fold) Key Insight: Fold consumes a structure; unfold produces one. Rust's `std::iter::from_fn` and `successors` are unfold equivalents.

// 069: Unfold — generate a sequence from a seed

// Approach 1: Manual unfold function
fn unfold<S, T>(seed: S, f: impl Fn(S) -> Option<(T, S)>) -> Vec<T> {
    let mut result = Vec::new();
    let mut state = seed;
    while let Some((value, next)) = f(state) {
        result.push(value);
        state = next;
    }
    result
}

fn range(a: i32, b: i32) -> Vec<i32> {
    unfold(a, |i| if i >= b { None } else { Some((i, i + 1)) })
}

fn fibs_up_to(limit: u64) -> Vec<u64> {
    unfold((0u64, 1u64), |(a, b)| {
        if a > limit { None } else { Some((a, (b, a + b))) }
    })
}

// Approach 2: Using std::iter::successors
fn collatz(n: u64) -> Vec<u64> {
    std::iter::successors(Some(n), |&x| {
        if x <= 1 { None }
        else if x % 2 == 0 { Some(x / 2) }
        else { Some(3 * x + 1) }
    }).collect()
}

// Approach 3: Using from_fn with state
fn range_from_fn(a: i32, b: i32) -> Vec<i32> {
    let mut i = a;
    std::iter::from_fn(move || {
        if i >= b { None } else { let v = i; i += 1; Some(v) }
    }).collect()
}

fn main() {
    println!("range(1,6) = {:?}", range(1, 6));
    println!("fibs_up_to(20) = {:?}", fibs_up_to(20));
    println!("collatz(6) = {:?}", collatz(6));
}

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

    #[test]
    fn test_range() {
        assert_eq!(range(1, 6), vec![1, 2, 3, 4, 5]);
        assert_eq!(range(5, 5), Vec::<i32>::new());
    }

    #[test]
    fn test_fibs() {
        assert_eq!(fibs_up_to(20), vec![0, 1, 1, 2, 3, 5, 8, 13]);
    }

    #[test]
    fn test_collatz() {
        assert_eq!(collatz(6), vec![6, 3, 10, 5, 16, 8, 4, 2, 1]);
    }

    #[test]
    fn test_range_from_fn() {
        assert_eq!(range_from_fn(1, 4), vec![1, 2, 3]);
    }
}

(* 069: Unfold — generate a sequence from a seed *)

(* Approach 1: Manual list unfold *)
let rec unfold f seed =
  match f seed with
  | None -> []
  | Some (value, next_seed) -> value :: unfold f next_seed

(* Generate range [a, b) *)
let range a b =
  unfold (fun i -> if i >= b then None else Some (i, i + 1)) a

(* Fibonacci sequence up to limit *)
let fibs_up_to limit =
  unfold (fun (a, b) ->
    if a > limit then None
    else Some (a, (b, a + b))
  ) (0, 1)

(* Approach 2: Collatz sequence *)
let collatz n =
  unfold (fun n ->
    if n = 1 then Some (1, 0)
    else if n = 0 then None
    else Some (n, if n mod 2 = 0 then n / 2 else 3 * n + 1)
  ) n

(* Approach 3: Using Seq.unfold *)
let range_seq a b =
  Seq.unfold (fun i -> if i >= b then None else Some (i, i + 1)) a

let seq_to_list s = List.of_seq s

(* Tests *)
let () =
  assert (range 1 6 = [1; 2; 3; 4; 5]);
  assert (range 5 5 = []);
  assert (fibs_up_to 20 = [0; 1; 1; 2; 3; 5; 8; 13]);
  assert (collatz 6 = [6; 3; 10; 5; 16; 8; 4; 2; 1]);
  assert (seq_to_list (range_seq 1 4) = [1; 2; 3]);
  Printf.printf "✓ All tests passed\n"

📊 Detailed Comparison

Core Insight

Unfold is the dual of fold: while fold reduces a collection to a value, unfold generates a collection from a seed. Given a seed and a function `seed -> (element, new_seed) option`, unfold produces a list.

OCaml Approach

`Seq.unfold` (OCaml 4.14+) generates a `Seq`
Manual recursive unfold for lists
Seed function returns `Some (value, next_seed)` or `None`

Rust Approach

`std::iter::from_fn(|| ...)` — stateful closure
`std::iter::successors(seed, |prev| ...)` — explicit unfold
Custom iterator with state struct

Comparison Table

Feature	OCaml	Rust
Unfold	`Seq.unfold f seed`	`successors(seed, f)`
Stateful gen	Manual closure	`from_fn(\	\	...)`
Laziness	`Seq` is lazy	Iterators are lazy
Termination	Return `None`	Return `None`