ExamplesBy LevelBy TopicLearning Paths
069 Advanced
← 069070 →

069 — Unfold — Generate a Sequence from a Seed

Functional Programming

Tutorial

The Problem

unfold is the categorical dual of fold: where fold (catamorphism) reduces a sequence to a single value by repeatedly applying a combining function, unfold (anamorphism) generates a sequence from a seed value by repeatedly applying a step function. Given an initial state s and a function f: S -> Option<(T, S)>, unfold produces values of type T and evolves the state S until f returns None.

This pattern appears throughout computing: database cursor iteration yields one row at a time from a state machine; pagination APIs return one page at a time, advancing a token; compilers lex one token at a time from a character stream; and stream decoders decode one frame at a time from a byte buffer. Any situation where you generate a sequence incrementally from evolving state is an unfold.

unfold appears as Seq.unfold in OCaml 4.11+, unfoldr in Haskell's Data.List, and std::iter::successors in Rust (a slightly restricted version where the state equals the output). Understanding unfold gives you a principled vocabulary for all sequence generation.

🎯 Learning Outcomes

  • • Implement unfold<S, T>(seed: S, f: impl Fn(S) -> Option<(T, S)>) -> Vec<T> as a loop
  • • Use std::iter::successors as Rust's built-in unfold-like combinator when state equals output
  • • Recognize the difference between successors (state = value) and full unfold (state can differ)
  • • Generate finite sequences by returning None from the step function when done
  • • Recognize unfold as the dual of fold: catamorphism vs anamorphism in category theory
  • • Implement classic sequences (range, Fibonacci, Collatz) using the unfold pattern

    • Code Example

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

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

    Key Differences

  • **successors vs full unfold**: Rust's successors(Some(seed), f) where f: &T -> Option<T> means the state is the same type as the output. OCaml's Seq.unfold f seed where f: S -> Option<(T, S)> separates state from output — more general but syntactically heavier.
  • **from_fn as general unfold**: std::iter::from_fn(|| ...) with closed-over mutable state is Rust's most general unfold. It handles cases where successors is too restrictive.
  • Eagerness vs laziness: The manual unfold in this example is eager — it collects everything into a Vec. Rust's successors and from_fn are lazy iterators. OCaml's Seq.unfold is lazy (thunk-based). Laziness matters for infinite sequences.
  • Termination: Both versions terminate when the step function returns None. Infinite sequences are handled by never returning None and using .take(n) to limit consumption.
  • Stack safety: OCaml's naive recursive unfold is not tail-recursive and will overflow on long sequences. Rust's loop-based implementation and lazy iterators are stack-safe.

    • OCaml Approach

    OCaml 4.11+ has Seq.unfold f seed in the standard library returning a lazy sequence:

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

(* Fibonacci using unfold *)
let fibs = Seq.unfold (fun (a, b) -> Some (a, (b, a+b))) (0, 1)

    Earlier versions require a manual definition: let rec unfold f s = match f s with | None -> [] | Some (x, s') -> x :: unfold f s'. This is eager and not tail-recursive, so it can stack-overflow on very long sequences. The Seq.unfold version is lazy (thunk-based), so it handles infinite sequences safely.

    Full Source

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

#[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]);
    }
}
    ✓ Tests Rust test suite 
    #[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]);
    }
}

    Deep 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

    FeatureOCamlRust
    UnfoldSeq.unfold f seedsuccessors(seed, f)
    Stateful genManual closurefrom_fn(\|\| ...)
    LazinessSeq is lazyIterators are lazy
    TerminationReturn NoneReturn None

    Exercises

  • Binary representation: Write binary_digits(n: u64) -> Vec<u8> using unfold that generates binary digits of n from least significant to most significant: seed=n, step |x| if x == 0 { None } else { Some((x & 1, x >> 1)) }.
  • Newton's method: Write newton_sqrt(n: f64) -> impl Iterator<Item=f64> that generates successive approximations of √n using successors: x_next = (x + n/x) / 2. Stop (in a consumer) when two successive values differ by less than 1e-10.
  • Iterate combinator: Write iterate<T: Clone, F: Fn(&T) -> T>(f: F, seed: T) -> impl Iterator<Item=T> producing the infinite sequence seed, f(seed), f(f(seed)), .... This is Haskell's iterate and OCaml's Seq.iterate. Implement it using successors.

    • Open Source Repos

    functional-rust

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

    Rust