089 Intermediate

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

#![allow(clippy::all)]
// 089: Lazy Sequences

#[cfg(test)]
mod tests {
    #[test]
    fn test_naturals() {
        let mut n = 0i32;
        let v: Vec<i32> = std::iter::from_fn(move || {
            let v = n;
            n += 1;
            Some(v)
        })
        .take(5)
        .collect();
        assert_eq!(v, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn test_fibs() {
        let v: Vec<u64> = std::iter::successors(Some((0u64, 1u64)), |&(a, b)| Some((b, a + b)))
            .map(|(a, _)| a)
            .take(8)
            .collect();
        assert_eq!(v, vec![0, 1, 1, 2, 3, 5, 8, 13]);
    }

    #[test]
    fn test_powers() {
        let mut exp = 0u32;
        let v: Vec<u64> = std::iter::from_fn(move || {
            if exp >= 4 {
                None
            } else {
                let v = 1u64 << exp;
                exp += 1;
                Some(v)
            }
        })
        .collect();
        assert_eq!(v, vec![1, 2, 4, 8]);
    }
}

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

#![allow(clippy::all)]
// 089: Lazy Sequences

#[cfg(test)]
mod tests {
    #[test]
    fn test_naturals() {
        let mut n = 0i32;
        let v: Vec<i32> = std::iter::from_fn(move || {
            let v = n;
            n += 1;
            Some(v)
        })
        .take(5)
        .collect();
        assert_eq!(v, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn test_fibs() {
        let v: Vec<u64> = std::iter::successors(Some((0u64, 1u64)), |&(a, b)| Some((b, a + b)))
            .map(|(a, _)| a)
            .take(8)
            .collect();
        assert_eq!(v, vec![0, 1, 1, 2, 3, 5, 8, 13]);
    }

    #[test]
    fn test_powers() {
        let mut exp = 0u32;
        let v: Vec<u64> = std::iter::from_fn(move || {
            if exp >= 4 {
                None
            } else {
                let v = 1u64 << exp;
                exp += 1;
                Some(v)
            }
        })
        .collect();
        assert_eq!(v, vec![1, 2, 4, 8]);
    }
}

(* 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 {
    #[test]
    fn test_naturals() {
        let mut n = 0i32;
        let v: Vec<i32> = std::iter::from_fn(move || {
            let v = n;
            n += 1;
            Some(v)
        })
        .take(5)
        .collect();
        assert_eq!(v, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn test_fibs() {
        let v: Vec<u64> = std::iter::successors(Some((0u64, 1u64)), |&(a, b)| Some((b, a + b)))
            .map(|(a, _)| a)
            .take(8)
            .collect();
        assert_eq!(v, vec![0, 1, 1, 2, 3, 5, 8, 13]);
    }

    #[test]
    fn test_powers() {
        let mut exp = 0u32;
        let v: Vec<u64> = std::iter::from_fn(move || {
            if exp >= 4 {
                None
            } else {
                let v = 1u64 << exp;
                exp += 1;
                Some(v)
            }
        })
        .collect();
        assert_eq!(v, vec![1, 2, 4, 8]);
    }
}

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