🎬 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

Difficulty: ⭐⭐ Level: Foundations Generate sequences from a seed value — the functional dual of `fold`.

The Problem This Solves

You want to produce a sequence by repeatedly applying a rule to some state. Fibonacci numbers start from `(0, 1)` and each step produces the next pair. A Collatz sequence starts from `n` and each step halves (if even) or triples-plus-one (if odd) until reaching 1. A countdown starts from `n` and decrements to 0. The imperative approach: a `while` loop with mutation. That works, but it ties together "how to generate" and "what to do with the results." You can't lazily generate, can't reuse the generation logic, can't compose it with other iterators. `unfold` separates those concerns. You provide: (1) an initial seed, and (2) a function that takes the current state and either produces `(value, next_state)` or `None` to stop. `unfold` does the rest.

The Intuition

If `fold` is "consume a list, produce a value" (many → one), then `unfold` is "consume a seed, produce a list" (one → many). They're conceptual mirrors. The function you pass to `unfold` answers: "given the current state, what's the next value to emit, and what's the next state?" Return `None` to stop. This is exactly `Seq.unfold` in OCaml, and `std::iter::successors` + `std::iter::from_fn` in Rust.

How It Works in Rust

Custom `unfold` function:

pub fn unfold<T, S, F>(seed: S, f: F) -> Vec<T>
where
 F: Fn(S) -> Option<(T, S)>,
 S: Clone,
{
 let mut result = Vec::new();
 let mut state = seed;
 while let Some((value, next)) = f(state.clone()) {
     result.push(value);
     state = next;
 }
 result
}

Using it:

// Range: count from a to b
let range_1_5 = unfold(1, |i| if i > 5 { None } else { Some((i, i + 1)) });
// → [1, 2, 3, 4, 5]

// Collatz sequence from 6
let collatz_6 = unfold(6u64, |x| match x {
 0 => None,
 1 => Some((1, 0)),  // emit 1, stop next
 x if x % 2 == 0 => Some((x, x / 2)),
 x => Some((x, 3 * x + 1)),
});
// → [6, 3, 10, 5, 16, 8, 4, 2, 1]

Rust's built-in lazy version using `std::iter::successors`:

// Infinite Fibonacci iterator — lazy, no allocation until consumed
pub fn fibs() -> impl Iterator<Item = u64> {
 std::iter::successors(Some((0u64, 1u64)), |&(a, b)| Some((b, a + b)))
     .map(|(a, _)| a)
}

What This Unlocks

Sequence generation — any series defined by a recurrence (Fibonacci, primes, Collatz, geometric series)
State machine unrolling — generate all states of a system from an initial state and a transition function
Lazy infinite sequences — use `successors` to define a sequence, then `take(n)` to consume only what you need

Key Differences

Concept	OCaml	Rust
Built-in unfold	`Seq.unfold f seed` (lazy)	`std::iter::successors` (lazy)
Custom unfold	Recursive with `::` cons	Loop with `Vec::push`
Termination	Return `None`	Return `None`
Eager vs lazy	`List.of_seq (Seq.unfold ...)`	`unfold(...)` for Vec, `successors` for lazy

/// # Unfold — Generating Sequences from Seeds
///
/// Unfold is the dual of fold: fold consumes a list into a value,
/// unfold produces a list from a seed value.

/// Generic unfold: applies f to seed repeatedly until f returns None.
/// Returns a Vec of produced values.
pub fn unfold<T, S, F>(seed: S, f: F) -> Vec<T>
where
    F: Fn(S) -> Option<(T, S)>,
    S: Clone,
{
    let mut result = Vec::new();
    let mut state = seed;
    while let Some((value, next)) = f(state.clone()) {
        result.push(value);
        state = next;
    }
    result
}

/// Range using unfold
pub fn range(a: i64, b: i64) -> Vec<i64> {
    unfold(a, |i| if i > b { None } else { Some((i, i + 1)) })
}

/// Countdown using unfold
pub fn countdown(n: i64) -> Vec<i64> {
    unfold(n, |i| if i < 0 { None } else { Some((i, i - 1)) })
}

/// Collatz sequence using unfold
pub fn collatz(n: u64) -> Vec<u64> {
    unfold(n, |x| {
        if x == 0 {
            None
        } else if x == 1 {
            Some((1, 0))
        } else if x % 2 == 0 {
            Some((x, x / 2))
        } else {
            Some((x, 3 * x + 1))
        }
    })
}

/// Iterator-based unfold using `std::iter::successors`
pub fn fibs_iter() -> impl Iterator<Item = u64> {
    std::iter::successors(Some((0u64, 1u64)), |&(a, b)| Some((b, a + b)))
        .map(|(a, _)| a)
}

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

    #[test]
    fn test_range() {
        assert_eq!(range(1, 5), vec![1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_range_empty() {
        assert_eq!(range(5, 3), vec![]);
    }

    #[test]
    fn test_countdown() {
        assert_eq!(countdown(5), vec![5, 4, 3, 2, 1, 0]);
    }

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

    #[test]
    fn test_collatz_one() {
        assert_eq!(collatz(1), vec![1]);
    }

    #[test]
    fn test_fibs_iter() {
        let first8: Vec<u64> = fibs_iter().take(8).collect();
        assert_eq!(first8, vec![0, 1, 1, 2, 3, 5, 8, 13]);
    }
}

fn main() {
    println!("{:?}", range(1, 5), vec![1, 2, 3, 4, 5]);
    println!("{:?}", range(5, 3), vec![]);
    println!("{:?}", countdown(5), vec![5, 4, 3, 2, 1, 0]);
}

(* Unfold — Generating Sequences from Seeds *)
(* The dual of fold: produces a list from a seed value *)

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

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

let countdown n =
  unfold (fun i -> if i < 0 then None else Some (i, i - 1)) n

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

let () =
  List.iter (Printf.printf "%d ") (range 1 5);
  print_newline ();
  List.iter (Printf.printf "%d ") (collatz 6);
  print_newline ();
  assert (range 1 5 = [1;2;3;4;5]);
  assert (countdown 3 = [3;2;1;0]);
  Printf.printf "All unfold tests passed!\n"

📊 Detailed Comparison

Unfold — OCaml vs Rust Comparison

Core Insight

Unfold is the categorical dual of fold: where fold consumes a structure into a summary, unfold generates a structure from a seed. OCaml expresses it naturally as a recursive function returning a list. Rust can do the same but also has built-in lazy unfold via `std::iter::successors`.

OCaml Approach

A simple recursive function: call `f seed`, if `Some(value, next)` then cons `value` onto the recursive result. Clean and elegant, but not tail-recursive — deep sequences can overflow the stack. OCaml's `Seq.unfold` provides a lazy version.

Rust Approach

Two options: (1) A custom `unfold` function that collects into `Vec` — eagerly evaluates the entire sequence. (2) `std::iter::successors` or `std::iter::from_fn` for lazy evaluation — generates values on demand. The lazy version is more idiomatic for potentially large or infinite sequences.

Comparison Table

Aspect	OCaml	Rust
Memory	Cons cells (linked list)	Vec (contiguous) or iterator (lazy)
Null safety	`Option` for termination	`Option` for termination
Errors	Stack overflow on deep unfold	Vec grows dynamically (no overflow)
Iteration	Recursive	`while let` loop or iterator chain
Laziness	`Seq.unfold` (separate module)	`successors` / `from_fn` (built-in)

Things Rust Learners Should Notice

1. `while let Some(...)` pattern — idiomatic for consuming option-producing functions 2. `S: Clone` bound — needed because the state must be passed to `f` while we check the result 3. `std::iter::successors` — built-in lazy unfold, returns an iterator 4. Eager vs lazy — our `unfold` builds a Vec immediately; `successors` is lazy 5. Termination — `None` from the function signals end of sequence in both languages