ExamplesBy LevelBy TopicLearning Paths
938 Advanced
← 937939 →

938-unfold — Unfold

Functional Programming

Tutorial

The Problem

Fold (catamorphism) consumes a recursive structure into a value. Unfold (anamorphism) generates a recursive structure from a seed value. They are dual operations. Unfold takes a seed S and a function f: S -> Option<(T, S)>: if f(s) = None, the sequence ends; if f(s) = Some(value, next_state), emit value and continue with next_state. This generates sequences: ranges, Collatz sequences, Fibonacci, countdowns. Haskell has unfoldr; OCaml has Seq.unfold. Rust's std::iter::from_fn and custom iterators serve the same role. Unfold is the generative dual of fold.

🎯 Learning Outcomes

  • • Implement the generic unfold<T, S, F> function
  • • Generate sequences from seed values: range, countdown, Collatz, Fibonacci
  • • Understand Option<(T, S)> as the protocol: None terminates, Some((value, next)) continues
  • • Recognize unfold as the dual of fold (anamorphism vs catamorphism)
  • • Compare with OCaml's Seq.unfold and Haskell's Data.List.unfoldr

    • Code Example

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

    Key Differences

  • Laziness: Rust's custom unfold is eager (returns Vec); OCaml's Seq.unfold is lazy; Rust's from_fn closure enables lazy unfold.
  • State cloning: The eager Rust version needs S: Clone to apply f and keep state; the lazy iterator version can take ownership.
  • Protocol: Both use Option<(value, next_state)> — same semantic protocol, just Option vs None/Some.
  • Standard library: OCaml has Seq.unfold since 4.11; Rust uses std::iter::from_fn or custom iterators — no direct unfold function in std.

    • OCaml Approach

    Seq.unfold: ('a -> ('b * 'a) option) -> 'a -> 'b Seq.t is the direct equivalent (since 4.11). let range a b = Seq.unfold (fun i -> if i > b then None else Some(i, i+1)) a. Fibonacci: Seq.unfold (fun (a,b) -> Some(a, (b, a+b))) (0, 1). OCaml's Seq.unfold is lazy — elements are generated on demand. Converting to list: Seq.take n seq |> List.of_seq. Haskell's unfoldr uses (a -> Maybe (b, a)) — same protocol, different Maybe syntax.

    Full Source

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

    Deep 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

    AspectOCamlRust
    MemoryCons cells (linked list)Vec (contiguous) or iterator (lazy)
    Null safetyOption for terminationOption for termination
    ErrorsStack overflow on deep unfoldVec grows dynamically (no overflow)
    IterationRecursivewhile let loop or iterator chain
    LazinessSeq.unfold (separate module)successors / from_fn (built-in)

    Things Rust Learners Should Notice

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

    • Further Reading

  • • [std::iter::successors](https://doc.rust-lang.org/std/iter/fn.successors.html)
  • • [std::iter::from_fn](https://doc.rust-lang.org/std/iter/fn.from_fn.html)
  • • [Anamorphism (Wikipedia)](https://en.wikipedia.org/wiki/Anamorphism)

    • Exercises

  • Implement a lazy unfold_iter<T, S, F: Fn(S) -> Option<(T, S)>> using std::iter::from_fn that generates values on demand.
  • Use unfold to generate the sequence of perfect squares below 1000.
  • Implement unfold_tree<T, S, F>(seed: S, f: F) -> Tree<T> where f(s) = None creates a leaf and f(s) = Some(value, left_seed, right_seed) creates a node.

    • Open Source Repos

    functional-rust

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

    Rust