103 Advanced

103-unfold — Unfold: Generating Sequences from Seeds

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "103-unfold — Unfold: Generating Sequences from Seeds" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. `fold` reduces a sequence to a single value. Key difference from OCaml: 1. **Laziness**: OCaml's `Seq.unfold` is lazy; Rust's `unfold` in this example is strict (collects into `Vec`). Rust's `from_fn` / `successors` are lazy iterators.

Tutorial

The Problem

fold reduces a sequence to a single value. unfold is its dual: it generates a sequence from a seed value by repeatedly applying a step function until the function returns None. This is the mathematical concept of anamorphism — the category-theoretic dual of catamorphism (fold).

unfold appears in Haskell's Data.List.unfoldr, OCaml's Seq.unfold, and Rust's std::iter::from_fn and Iterator::scan. It elegantly expresses infinite sequences, state machines, and recursive data generation.

🎯 Learning Outcomes

• Understand unfold as the dual of fold

• Implement unfold using a seed value and step function

• Generate finite and infinite sequences with unfold

• Recognize unfold in Rust's std::iter::from_fn and Iterator::scan

• Apply unfold to classic sequences: ranges, Collatz, Fibonacci

Code Example

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
}

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

Key Differences

Laziness: OCaml's Seq.unfold is lazy; Rust's unfold in this example is strict (collects into Vec). Rust's from_fn / successors are lazy iterators.

Infinite sequences: OCaml's lazy Seq handles infinite sequences naturally; Rust requires lazy iterators (from_fn) and explicit take(n) to truncate.

State type: Both take a seed/state and a step function; the type signature is identical in spirit.

Standard library: OCaml's Seq.unfold is in stdlib since 4.11; Rust's std::iter::successors is the closest built-in equivalent.

OCaml Approach

OCaml's Seq.unfold does this lazily:

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

let collatz n =
  Seq.unfold (function
    | 0 -> None
    | 1 -> Some (1, 0)
    | n -> Some (n, if n mod 2 = 0 then n / 2 else 3 * n + 1)
  ) n |> List.of_seq

OCaml's version is lazy by default — the sequence is only computed as far as it is consumed, enabling infinite sequences without running out of memory.

Full Source

#![allow(clippy::all)]
//! # 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]);
    }
}

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

✓ Tests Rust test suite

#[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]);
    }
}

Deep 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

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

Exercises

Use std::iter::successors to implement fibonacci_iter() -> impl Iterator<Item=u64> as an infinite sequence.

Implement unfold_lazy<S: Clone, T>(seed: S, f: impl Fn(&S) -> Option<(T, S)>) -> impl Iterator<Item=T> using from_fn.

Use unfold to generate the binary representation of a number (most significant digit first) by repeatedly dividing by 2.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust