101 Intermediate

Lazy Sequences

Lazy/Infinite Sequences

Tutorial Video

Text description (accessibility)

This video demonstrates the "Lazy Sequences" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Lazy/Infinite Sequences. Create infinite lazy sequences: natural numbers, Fibonacci numbers, and primes. Key difference from OCaml: 1. **Default laziness:** Rust iterators are lazy by default — `(0..)` is already an infinite sequence. OCaml lists are strict; `Seq` is a separate lazy abstraction added explicitly

Tutorial

The Problem

Create infinite lazy sequences: natural numbers, Fibonacci numbers, and primes. Take only what you need without computing the rest.

🎯 Learning Outcomes

• Map OCaml's Seq module to Rust's Iterator trait

• Use std::iter::successors and std::iter::from_fn for custom infinite iterators

• Understand that Rust iterators are lazy by default (no Seq module needed)

• Implement unfold — the dual of fold

Code Example

pub fn fibs() -> impl Iterator<Item = u64> {
    std::iter::successors(Some((0, 1)), |&(a, b)| Some((b, a + b)))
        .map(|(a, _)| a)
}

let first10: Vec<u64> = fibs().take(10).collect();

let fibs = Seq.unfold (fun (a, b) -> Some (a, (b, a + b))) (0, 1)
let primes = Seq.ints 2 |> Seq.filter is_prime
let first10 = Seq.take 10 fibs |> Seq.iter (Printf.printf "%d ")

Key Differences

Default laziness: Rust iterators are lazy by default — (0..) is already an infinite sequence. OCaml lists are strict; Seq is a separate lazy abstraction added explicitly

Representation: OCaml Seq uses closures (unit -> node); Rust uses Iterator trait objects or impl Iterator return types — both avoid computing values until demanded

**successors vs unfold:** Rust's std::iter::successors is the direct equivalent of OCaml's Seq.unfold; both thread state through a step function returning Option

Memory: OCaml Seq nodes are heap-allocated closures; Rust iterators can be stack-allocated state machines with zero heap overhead

OCaml Approach

OCaml's Seq module (added in 4.07) represents a lazy sequence as a thunk: type 'a t = unit -> 'a node where node = Nil | Cons of 'a * 'a t. Each Cons cell is a closure that produces the next element only when forced. Seq.unfold f seed repeatedly applies f returning Some (value, next_seed) or None. Unlike Rust, OCaml lists are strict by default, so Seq is the explicit opt-in for laziness.

Full Source

#![allow(clippy::all)]
//! # Lazy Sequences
//!
//! OCaml's `Seq` module provides lazy sequences. Rust's iterators are
//! lazy by default — they only compute values when consumed.

// ---------------------------------------------------------------------------
// Approach A: Iterator adaptors (idiomatic Rust)
// ---------------------------------------------------------------------------

/// Infinite natural numbers starting from n
pub fn naturals(start: u64) -> impl Iterator<Item = u64> {
    start..
}

/// Fibonacci sequence as an iterator
pub fn fibs() -> impl Iterator<Item = u64> {
    std::iter::successors(Some((0u64, 1u64)), |&(a, b)| {
        a.checked_add(b).map(|s| (b, s))
    })
    .map(|(a, _)| a)
}

/// Infinite prime number iterator
pub fn primes() -> impl Iterator<Item = u64> {
    (2..).filter(|&n| is_prime(n))
}

fn is_prime(n: u64) -> bool {
    if n < 2 {
        return false;
    }
    (2..).take_while(|&i| i * i <= n).all(|i| n % i != 0)
}

// ---------------------------------------------------------------------------
// Approach B: Custom unfold (mirrors OCaml's Seq.unfold)
// ---------------------------------------------------------------------------

pub fn unfold<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)
    })
}

pub fn fibs_unfold() -> impl Iterator<Item = u64> {
    unfold((0u64, 1u64), |&(a, b)| Some((a, (b, a + b))))
}

// ---------------------------------------------------------------------------
// Approach C: Successors (std::iter::successors)
// ---------------------------------------------------------------------------

pub fn naturals_succ(start: u64) -> impl Iterator<Item = u64> {
    std::iter::successors(Some(start), |&n| Some(n + 1))
}

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

    #[test]
    fn test_naturals() {
        let first5: Vec<u64> = naturals(0).take(5).collect();
        assert_eq!(first5, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn test_fibs() {
        let first10: Vec<u64> = fibs().take(10).collect();
        assert_eq!(first10, vec![0, 1, 1, 2, 3, 5, 8, 13, 21, 34]);
    }

    #[test]
    fn test_primes() {
        let first10: Vec<u64> = primes().take(10).collect();
        assert_eq!(first10, vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 29]);
    }

    #[test]
    fn test_unfold_fibs() {
        let first10: Vec<u64> = fibs_unfold().take(10).collect();
        assert_eq!(first10, vec![0, 1, 1, 2, 3, 5, 8, 13, 21, 34]);
    }

    #[test]
    fn test_laziness() {
        // This doesn't hang because iterators are lazy
        let _infinite = naturals(0);
        let first = naturals(0).take(1).collect::<Vec<_>>();
        assert_eq!(first, vec![0]);
    }
}

let naturals = Seq.ints 0

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

let primes =
  let is_prime n =
    n >= 2 && Seq.ints 2
    |> Seq.take_while (fun i -> i * i <= n)
    |> Seq.for_all (fun i -> n mod i <> 0)
  in
  Seq.ints 2 |> Seq.filter is_prime

let () =
  Printf.printf "Naturals: ";
  Seq.take 5 naturals |> Seq.iter (Printf.printf "%d ");
  Printf.printf "\nFibs: ";
  Seq.take 10 fibs |> Seq.iter (Printf.printf "%d ");
  Printf.printf "\nPrimes: ";
  Seq.take 10 primes |> Seq.iter (Printf.printf "%d ");
  print_newline ()

✓ Tests Rust test suite

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

    #[test]
    fn test_naturals() {
        let first5: Vec<u64> = naturals(0).take(5).collect();
        assert_eq!(first5, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn test_fibs() {
        let first10: Vec<u64> = fibs().take(10).collect();
        assert_eq!(first10, vec![0, 1, 1, 2, 3, 5, 8, 13, 21, 34]);
    }

    #[test]
    fn test_primes() {
        let first10: Vec<u64> = primes().take(10).collect();
        assert_eq!(first10, vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 29]);
    }

    #[test]
    fn test_unfold_fibs() {
        let first10: Vec<u64> = fibs_unfold().take(10).collect();
        assert_eq!(first10, vec![0, 1, 1, 2, 3, 5, 8, 13, 21, 34]);
    }

    #[test]
    fn test_laziness() {
        // This doesn't hang because iterators are lazy
        let _infinite = naturals(0);
        let first = naturals(0).take(1).collect::<Vec<_>>();
        assert_eq!(first, vec![0]);
    }
}

Deep Comparison

Comparison: Lazy Sequences — OCaml vs Rust

Core Insight

OCaml's Seq provides lazy sequences as an explicit abstraction layered on top of eager lists. Rust's iterators are lazy from the ground up — map, filter, take all return lazy adaptors that only evaluate when consumed by collect, for_each, etc. This design means Rust doesn't need a separate Seq module; every iterator is already a lazy sequence.

OCaml

let fibs = Seq.unfold (fun (a, b) -> Some (a, (b, a + b))) (0, 1)
let primes = Seq.ints 2 |> Seq.filter is_prime
let first10 = Seq.take 10 fibs |> Seq.iter (Printf.printf "%d ")

Rust

pub fn fibs() -> impl Iterator<Item = u64> {
    std::iter::successors(Some((0, 1)), |&(a, b)| Some((b, a + b)))
        .map(|(a, _)| a)
}

let first10: Vec<u64> = fibs().take(10).collect();

Comparison Table

Aspect	OCaml	Rust
Lazy by default	No (lists are eager)	Yes (iterators are lazy)
Infinite range	`Seq.ints 0`	`0..` (built-in)
Unfold	`Seq.unfold f seed`	`std::iter::successors` or `from_fn`
Take N	`Seq.take n seq`	`.take(n)`
Filter	`Seq.filter pred seq`	`.filter(pred)`
Consume	`Seq.iter f seq`	`.collect()` or `.for_each()`
Custom iterator	Implement `unit -> 'a Seq.node`	`impl Iterator for T`

Learner Notes

• **impl Iterator<Item = T>**: Return type hides the concrete iterator type — like OCaml's abstract 'a Seq.t

• **successors**: Generates Some(next) from previous — perfect for Fibonacci-style sequences

• **from_fn**: Most flexible — closure with mutable state, returns Option<T> per call

• No allocation: Rust's lazy chains allocate nothing until collect() — OCaml's Seq also avoids allocation via thunks

• **0..**: Rust's range syntax creates an infinite iterator — no Seq.ints needed

Exercises

Implement a cycle iterator that repeats a finite Vec<T> infinitely using std::iter::from_fn

Implement zip_with that combines two infinite iterators element-by-element with a function, producing a third infinite iterator

Implement a lazy sieve_of_eratosthenes that generates primes without the is_prime predicate — instead, filter out multiples of each new prime as it is discovered

Open Source Repos

functional-rust

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

Rust