🎬 Rust Ownership in 30 seconds Visual walkthrough of ownership, moves, and automatic memory management.

📝 Text version (for readers / accessibility)

• Each value in Rust has exactly one owner — when the owner goes out of scope, the value is dropped

• Assignment moves ownership by default; the original binding becomes invalid

• Borrowing (&T / &mut T) lets you reference data without taking ownership

• The compiler enforces: many shared references OR one mutable reference, never both

• No garbage collector needed — memory is freed deterministically at scope exit

103: Unfold — Generating Sequences from Seeds

Difficulty: 2 Level: Intermediate Build sequences from a starting value and a step function — the categorical dual of `fold`.

The Problem This Solves

`fold` consumes a collection to produce one value. `unfold` does the opposite: it produces a collection from one value. Given a seed and a function that says "what's the next value and what's the next seed?", you get a sequence. This pattern shows up constantly: the Collatz sequence, pagination (each page is a "seed" for the next), game replays (each state produces the next), tree traversal order. Anywhere you have a "current state → (output, next state)" shape, unfold is the right abstraction.

The Intuition

Think of unfold as running a state machine: you start with a seed, the function produces one output item and a new seed, then it runs again with the new seed, until the function returns `None` to stop.

seed → f(seed) = Some((item1, seed2))
seed2 → f(seed2) = Some((item2, seed3))
seed3 → f(seed3) = None  → stop
Result: [item1, item2]

The lazy version (returning an `Iterator`) only computes values when consumed — useful for potentially infinite sequences.

How It Works in Rust

Eager version — collects into a `Vec`:

pub fn unfold<S, T>(seed: S, f: impl Fn(S) -> Option<(T, S)>) -> Vec<T> {
 let mut result = Vec::new();
 let mut state = seed;
 loop {
     match f(state) {
         None => break,
         Some((value, next)) => {
             result.push(value);
             state = next;
         }
     }
 }
 result
}

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

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

Lazy version using `from_fn` — returns an iterator, computes on demand:

pub fn unfold_iter<S, T>(
 seed: S,
 f: impl Fn(&S) -> Option<(T, S)>,
) -> impl Iterator<Item = T> {
 let mut state = Some(seed);
 std::iter::from_fn(move || {
     let s = state.take()?;
     let (value, next) = f(&s)?;
     state = Some(next);
     Some(value)
 })
}

`std::iter::successors` is the standard library's built-in unfold for sequences where the value is the state:

let collatz = std::iter::successors(Some(6u64), |&x| {
 if x <= 1 { None }
 else if x % 2 == 0 { Some(x / 2) }
 else { Some(3 * x + 1) }
});

What This Unlocks

Pagination — `unfold(page_1_url, |url| fetch_page(url).map(|p| (p.items, p.next_url)))`
State machine replay — generate a sequence of states from an initial state and transition function
Mathematical sequences — any recurrence relation (Fibonacci, Collatz, continued fractions)

Key Differences

Concept	OCaml	Rust
Eager unfold	Recursive `let rec` building a list	Loop with `Vec::push`
Lazy unfold	`Seq.unfold` (since 4.07)	`std::iter::from_fn`
Built-in variant	`Seq.unfold`	`std::iter::successors`
Stop condition	`None` return	`None` return
Memory	GC manages intermediate state	`Option<S>` moves state — no GC needed

//! # Unfold — Generating Sequences from Seeds
//!
//! `unfold` is the dual of `fold`: instead of reducing a list to a value,
//! it builds a list from a seed value.

// ---------------------------------------------------------------------------
// Approach A: Collect into Vec (mirrors OCaml's list building)
// ---------------------------------------------------------------------------

pub fn unfold<S, T>(seed: S, f: impl Fn(S) -> Option<(T, S)>) -> Vec<T> {
    let mut result = Vec::new();
    let mut state = seed;
    loop {
        match f(state) {
            None => break,
            Some((value, next)) => {
                result.push(value);
                state = next;
            }
        }
    }
    result
}

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

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

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

// ---------------------------------------------------------------------------
// Approach B: Lazy unfold — returns an iterator
// ---------------------------------------------------------------------------

pub fn unfold_iter<S, T>(
    seed: S,
    f: impl Fn(&S) -> Option<(T, S)>,
) -> impl Iterator<Item = T> {
    let mut state = Some(seed);
    std::iter::from_fn(move || {
        let s = state.take()?;
        let (value, next) = f(&s)?;
        state = Some(next);
        Some(value)
    })
}

// ---------------------------------------------------------------------------
// Approach C: Using std::iter::successors
// ---------------------------------------------------------------------------

pub fn collatz_iter(n: u64) -> impl Iterator<Item = u64> {
    std::iter::successors(Some(n), |&x| {
        if x <= 1 { None }
        else if x % 2 == 0 { Some(x / 2) }
        else { Some(3 * x + 1) }
    })
}

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

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

    #[test]
    fn test_countdown() {
        assert_eq!(countdown(3), vec![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_empty_range() {
        assert_eq!(range(5, 3), vec![]);
    }

    #[test]
    fn test_lazy_unfold() {
        let first5: Vec<i32> = unfold_iter(0, |&i| Some((i, i + 1))).take(5).collect();
        assert_eq!(first5, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn test_collatz_iter() {
        let seq: Vec<u64> = collatz_iter(6).collect();
        assert_eq!(seq, vec![6, 3, 10, 5, 16, 8, 4, 2, 1]);
    }
}

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

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 ()

📊 Detailed Comparison

Comparison: Unfold — OCaml vs Rust

Core Insight

`unfold` is the dual of `fold`: fold reduces a collection to a value; unfold builds a collection from a seed. OCaml's version is naturally recursive and builds a list eagerly. Rust offers both eager (`Vec`) and lazy (`Iterator`) variants, with the lazy version being more idiomatic for potentially large sequences.

OCaml

🐪 Show OCaml equivalent

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

Rust — Eager

pub fn unfold<S, T>(seed: S, f: impl Fn(S) -> Option<(T, S)>) -> Vec<T> {
 let mut result = Vec::new();
 let mut state = seed;
 loop {
     match f(state) { None => break, Some((v, next)) => { result.push(v); state = next; } }
 }
 result
}

Rust — Lazy

pub fn unfold_iter<S, T>(seed: S, f: impl Fn(&S) -> Option<(T, S)>) -> impl Iterator<Item = T> {
 let mut state = Some(seed);
 std::iter::from_fn(move || { let s = state.take()?; let (v, next) = f(&s)?; state = Some(next); Some(v) })
}

Comparison Table

Aspect	OCaml	Rust
Result type	`'a list` (eager)	`Vec<T>` or `impl Iterator` (lazy)
Recursion	Natural recursive cons	Loop or `from_fn`
Termination	`None` stops recursion	`None` breaks loop / ends iterator
Infinite seqs	Stack overflow risk	Lazy iterator handles infinite
Ownership	GC manages seed	`Fn(S) -> ...` takes ownership

Learner Notes

Dual of fold: If fold is `[a,b,c] -> x`, unfold is `x -> [a,b,c]` — same function, opposite direction
`std::iter::from_fn`: Rust's most flexible iterator builder — a closure that returns `Option<T>`
`successors`: Simpler than `from_fn` when each value depends only on the previous one
Eager vs lazy: OCaml's unfold builds the whole list; Rust's lazy version computes on demand
Ownership of seed: Rust's `Fn(S) -> Option<(T, S)>` consumes the seed each step — ensures single owner