089 Intermediate GitHub

089 — Lazy Sequences

Functional Programming

Tutorial

The Problem

Create infinite lazy sequences in Rust using std::iter::from_fn and std::iter::successors — without custom structs. Generate natural numbers, Fibonacci numbers, and powers of two using closures that capture mutable state. Compare with OCaml's Seq thunk-based lazy sequences.

🎯 Learning Outcomes

• Use std::iter::from_fn(move || …) to create a stateful iterator from a closure

• Use std::iter::successors(seed, step) for sequences defined by recurrence

• Apply .take(n) to safely bound infinite iterators

• Understand why move is required — the closure must own its mutable state

• Map from_fn to OCaml's Seq.Cons(v, thunk) construction

• Choose between from_fn (general), successors (recurrence), and a struct iterator

Code Example

//! # Lazy Sequences
//!
//! Demonstrates Rust's lazily-evaluated iterators, mirroring OCaml's `Seq` module.
//! Rust iterators are lazy by default — computation only occurs when values are polled.

/// Returns an infinite iterator of natural numbers starting from 0.
///
/// # Examples
/// ```
/// use example_089_lazy_sequences::naturals;
/// let v: Vec<u64> = naturals().take(5).collect();
/// assert_eq!(v, [0, 1, 2, 3, 4]);
/// ```
pub fn naturals() -> impl Iterator<Item = u64> {
    0..
}

/// Returns an infinite iterator of Fibonacci numbers.
///
/// Produces the sequence 0, 1, 1, 2, 3, 5, 8, 13, …
///
/// # Examples
/// ```
/// use example_089_lazy_sequences::fibs;
/// let v: Vec<u64> = fibs().take(8).collect();
/// assert_eq!(v, [0, 1, 1, 2, 3, 5, 8, 13]);
/// ```
pub fn fibs() -> impl Iterator<Item = u64> {
    std::iter::successors(Some((0u64, 1u64)), |&(a, b)| Some((b, a + b))).map(|(a, _)| a)
}

/// Builds an iterator from a stateful function, mirroring OCaml's `from_fn`.
///
/// The closure receives the current index (starting at 0). Returning `None`
/// terminates the sequence; returning `Some(v)` yields `v` and advances the index.
///
/// # Examples
/// ```
/// use example_089_lazy_sequences::from_fn_indexed;
/// let powers: Vec<u64> = from_fn_indexed(|n| if n < 10 { Some(1u64 << n) } else { None }).collect();
/// assert_eq!(powers[..4], [1, 2, 4, 8]);
/// ```
pub fn from_fn_indexed<T, F>(f: F) -> impl Iterator<Item = T>
where
    F: FnMut(usize) -> Option<T>,
{
    let mut index = 0usize;
    let mut f = f;
    std::iter::from_fn(move || {
        let result = f(index)?;
        index += 1;
        Some(result)
    })
}

/// Returns the first `n` elements of an iterator as a `Vec`.
///
/// Convenience wrapper around `.take(n).collect()`.
///
/// # Examples
/// ```
/// use example_089_lazy_sequences::{naturals, take};
/// assert_eq!(take(3, naturals()), vec![0, 1, 2]);
/// ```
pub fn take<T>(n: usize, iter: impl Iterator<Item = T>) -> Vec<T> {
    iter.take(n).collect()
}

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

    #[test]
    fn test_naturals_first_five() {
        assert_eq!(take(5, naturals()), [0, 1, 2, 3, 4]);
    }

    #[test]
    fn test_naturals_zero_elements() {
        assert_eq!(take(0, naturals()), [] as [u64; 0]);
    }

    #[test]
    fn test_naturals_one_element() {
        assert_eq!(take(1, naturals()), [0]);
    }

    #[test]
    fn test_fibs_first_eight() {
        assert_eq!(take(8, fibs()), [0, 1, 1, 2, 3, 5, 8, 13]);
    }

    #[test]
    fn test_fibs_first_one() {
        assert_eq!(take(1, fibs()), [0]);
    }

    #[test]
    fn test_fibs_first_two() {
        assert_eq!(take(2, fibs()), [0, 1]);
    }

    #[test]
    fn test_from_fn_indexed_powers_of_2() {
        let v: Vec<u64> =
            from_fn_indexed(|n| if n >= 10 { None } else { Some(1u64 << n) }).collect();
        assert_eq!(v.len(), 10);
        assert_eq!(&v[..4], [1, 2, 4, 8]);
        assert_eq!(v[9], 512);
    }

    #[test]
    fn test_from_fn_indexed_terminates() {
        let v: Vec<u32> =
            from_fn_indexed(|n| if n < 4 { Some(n as u32 * 3) } else { None }).collect();
        assert_eq!(v, [0, 3, 6, 9]);
    }

    #[test]
    fn test_from_fn_indexed_empty() {
        let v: Vec<u32> = from_fn_indexed(|_| None).collect();
        assert!(v.is_empty());
    }

    #[test]
    fn test_take_helper() {
        assert_eq!(take(4, naturals()), [0, 1, 2, 3]);
    }

    #[test]
    fn test_naturals_laziness() {
        // Confirms that only the requested elements are produced.
        let mut count = 0usize;
        let _: Vec<u64> = std::iter::from_fn(|| {
            count += 1;
            Some(count as u64)
        })
        .take(3)
        .collect();
        assert_eq!(count, 3);
    }
}

(* 089: Lazy Sequences *)

(* Approach 1: Lazy list via thunks *)
let naturals =
  let rec aux n () = Seq.Cons (n, aux (n + 1)) in
  aux 0

let take n s = List.of_seq (Seq.take n s)

(* Approach 2: Lazy fibonacci *)
let fibs =
  let rec aux a b () = Seq.Cons (a, aux b (a + b)) in
  aux 0 1

(* Approach 3: from_fn equivalent *)
let from_fn f =
  let state = ref 0 in
  let rec aux () =
    match f !state with
    | None -> Seq.Nil
    | Some v -> state := !state + 1; Seq.Cons (v, aux)
  in
  aux

let powers_of_2 = from_fn (fun n -> if n >= 10 then None else Some (1 lsl n))

(* Tests *)
let () =
  assert (take 5 naturals = [0; 1; 2; 3; 4]);
  assert (take 8 fibs = [0; 1; 1; 2; 3; 5; 8; 13]);
  assert (take 4 powers_of_2 = [1; 2; 4; 8]);
  Printf.printf "✓ All tests passed\n"

Key Differences

Aspect	Rust	OCaml
Generator	`from_fn(move \\|\\| …)`	`let rec aux () = Seq.Cons(…)`
Recurrence	`successors(seed, step)`	`let rec aux a b () = Seq.Cons(a, aux b (a+b))`
State	`move` captured mutable variable	Recursive argument or `ref`
Termination	Return `None`	Return `Seq.Nil`
Bounding	`.take(n)`	`Seq.take n`
Sharing	No sharing (new state per call)	Structural sharing via thunks

from_fn and successors are the quickest way to create custom lazy sequences in Rust without defining a struct. Use successors for single-state recurrences (Fibonacci, powers), from_fn for more general stateful generation, and a struct iterator for complex multi-field state.

OCaml Approach

OCaml's Seq type requires explicit thunk construction: let rec aux n () = Seq.Cons(n, aux (n+1)). The from_fn equivalent uses a mutable ref cell and a Seq.Cons(v, aux) where aux is the recursive thunk. Seq.take n s materialises the first n elements. The key difference is that OCaml's sequences share structure via closures (not mutable state), while Rust's from_fn uses mutated captured variables.

Full Source

//! # Lazy Sequences
//!
//! Demonstrates Rust's lazily-evaluated iterators, mirroring OCaml's `Seq` module.
//! Rust iterators are lazy by default — computation only occurs when values are polled.

/// Returns an infinite iterator of natural numbers starting from 0.
///
/// # Examples
/// ```
/// use example_089_lazy_sequences::naturals;
/// let v: Vec<u64> = naturals().take(5).collect();
/// assert_eq!(v, [0, 1, 2, 3, 4]);
/// ```
pub fn naturals() -> impl Iterator<Item = u64> {
    0..
}

/// Returns an infinite iterator of Fibonacci numbers.
///
/// Produces the sequence 0, 1, 1, 2, 3, 5, 8, 13, …
///
/// # Examples
/// ```
/// use example_089_lazy_sequences::fibs;
/// let v: Vec<u64> = fibs().take(8).collect();
/// assert_eq!(v, [0, 1, 1, 2, 3, 5, 8, 13]);
/// ```
pub fn fibs() -> impl Iterator<Item = u64> {
    std::iter::successors(Some((0u64, 1u64)), |&(a, b)| Some((b, a + b))).map(|(a, _)| a)
}

/// Builds an iterator from a stateful function, mirroring OCaml's `from_fn`.
///
/// The closure receives the current index (starting at 0). Returning `None`
/// terminates the sequence; returning `Some(v)` yields `v` and advances the index.
///
/// # Examples
/// ```
/// use example_089_lazy_sequences::from_fn_indexed;
/// let powers: Vec<u64> = from_fn_indexed(|n| if n < 10 { Some(1u64 << n) } else { None }).collect();
/// assert_eq!(powers[..4], [1, 2, 4, 8]);
/// ```
pub fn from_fn_indexed<T, F>(f: F) -> impl Iterator<Item = T>
where
    F: FnMut(usize) -> Option<T>,
{
    let mut index = 0usize;
    let mut f = f;
    std::iter::from_fn(move || {
        let result = f(index)?;
        index += 1;
        Some(result)
    })
}

/// Returns the first `n` elements of an iterator as a `Vec`.
///
/// Convenience wrapper around `.take(n).collect()`.
///
/// # Examples
/// ```
/// use example_089_lazy_sequences::{naturals, take};
/// assert_eq!(take(3, naturals()), vec![0, 1, 2]);
/// ```
pub fn take<T>(n: usize, iter: impl Iterator<Item = T>) -> Vec<T> {
    iter.take(n).collect()
}

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

    #[test]
    fn test_naturals_first_five() {
        assert_eq!(take(5, naturals()), [0, 1, 2, 3, 4]);
    }

    #[test]
    fn test_naturals_zero_elements() {
        assert_eq!(take(0, naturals()), [] as [u64; 0]);
    }

    #[test]
    fn test_naturals_one_element() {
        assert_eq!(take(1, naturals()), [0]);
    }

    #[test]
    fn test_fibs_first_eight() {
        assert_eq!(take(8, fibs()), [0, 1, 1, 2, 3, 5, 8, 13]);
    }

    #[test]
    fn test_fibs_first_one() {
        assert_eq!(take(1, fibs()), [0]);
    }

    #[test]
    fn test_fibs_first_two() {
        assert_eq!(take(2, fibs()), [0, 1]);
    }

    #[test]
    fn test_from_fn_indexed_powers_of_2() {
        let v: Vec<u64> =
            from_fn_indexed(|n| if n >= 10 { None } else { Some(1u64 << n) }).collect();
        assert_eq!(v.len(), 10);
        assert_eq!(&v[..4], [1, 2, 4, 8]);
        assert_eq!(v[9], 512);
    }

    #[test]
    fn test_from_fn_indexed_terminates() {
        let v: Vec<u32> =
            from_fn_indexed(|n| if n < 4 { Some(n as u32 * 3) } else { None }).collect();
        assert_eq!(v, [0, 3, 6, 9]);
    }

    #[test]
    fn test_from_fn_indexed_empty() {
        let v: Vec<u32> = from_fn_indexed(|_| None).collect();
        assert!(v.is_empty());
    }

    #[test]
    fn test_take_helper() {
        assert_eq!(take(4, naturals()), [0, 1, 2, 3]);
    }

    #[test]
    fn test_naturals_laziness() {
        // Confirms that only the requested elements are produced.
        let mut count = 0usize;
        let _: Vec<u64> = std::iter::from_fn(|| {
            count += 1;
            Some(count as u64)
        })
        .take(3)
        .collect();
        assert_eq!(count, 3);
    }
}

(* 089: Lazy Sequences *)

(* Approach 1: Lazy list via thunks *)
let naturals =
  let rec aux n () = Seq.Cons (n, aux (n + 1)) in
  aux 0

let take n s = List.of_seq (Seq.take n s)

(* Approach 2: Lazy fibonacci *)
let fibs =
  let rec aux a b () = Seq.Cons (a, aux b (a + b)) in
  aux 0 1

(* Approach 3: from_fn equivalent *)
let from_fn f =
  let state = ref 0 in
  let rec aux () =
    match f !state with
    | None -> Seq.Nil
    | Some v -> state := !state + 1; Seq.Cons (v, aux)
  in
  aux

let powers_of_2 = from_fn (fun n -> if n >= 10 then None else Some (1 lsl n))

(* Tests *)
let () =
  assert (take 5 naturals = [0; 1; 2; 3; 4]);
  assert (take 8 fibs = [0; 1; 1; 2; 3; 5; 8; 13]);
  assert (take 4 powers_of_2 = [1; 2; 4; 8]);
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_naturals_first_five() {
        assert_eq!(take(5, naturals()), [0, 1, 2, 3, 4]);
    }

    #[test]
    fn test_naturals_zero_elements() {
        assert_eq!(take(0, naturals()), [] as [u64; 0]);
    }

    #[test]
    fn test_naturals_one_element() {
        assert_eq!(take(1, naturals()), [0]);
    }

    #[test]
    fn test_fibs_first_eight() {
        assert_eq!(take(8, fibs()), [0, 1, 1, 2, 3, 5, 8, 13]);
    }

    #[test]
    fn test_fibs_first_one() {
        assert_eq!(take(1, fibs()), [0]);
    }

    #[test]
    fn test_fibs_first_two() {
        assert_eq!(take(2, fibs()), [0, 1]);
    }

    #[test]
    fn test_from_fn_indexed_powers_of_2() {
        let v: Vec<u64> =
            from_fn_indexed(|n| if n >= 10 { None } else { Some(1u64 << n) }).collect();
        assert_eq!(v.len(), 10);
        assert_eq!(&v[..4], [1, 2, 4, 8]);
        assert_eq!(v[9], 512);
    }

    #[test]
    fn test_from_fn_indexed_terminates() {
        let v: Vec<u32> =
            from_fn_indexed(|n| if n < 4 { Some(n as u32 * 3) } else { None }).collect();
        assert_eq!(v, [0, 3, 6, 9]);
    }

    #[test]
    fn test_from_fn_indexed_empty() {
        let v: Vec<u32> = from_fn_indexed(|_| None).collect();
        assert!(v.is_empty());
    }

    #[test]
    fn test_take_helper() {
        assert_eq!(take(4, naturals()), [0, 1, 2, 3]);
    }

    #[test]
    fn test_naturals_laziness() {
        // Confirms that only the requested elements are produced.
        let mut count = 0usize;
        let _: Vec<u64> = std::iter::from_fn(|| {
            count += 1;
            Some(count as u64)
        })
        .take(3)
        .collect();
        assert_eq!(count, 3);
    }
}

Deep Comparison

Core Insight

Rust iterators are lazy by default — computation only happens when values are pulled

OCaml Approach

• See example.ml for implementation

Rust Approach

• See example.rs for implementation

Comparison Table

Feature	OCaml	Rust
See	example.ml	example.rs

Exercises

Generate the Collatz sequence for a given start value using successors(Some(n), |&n| if n == 1 { None } else { Some(next) }).

Create a lazy sieve of Eratosthenes by combining from_fn with a HashSet of composites.

Implement a zip_lazy function that takes two from_fn-style sequences and yields pairs.

Use std::iter::repeat_with to generate random numbers and compare it to from_fn with the same effect.

In OCaml, implement a lazy merge of two sorted infinite sequences into a single sorted sequence using Seq.

Open Source Repos

functional-rust

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

Rust