067 Intermediate

067 — Lazy Sequences (Seq Module)

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "067 — Lazy Sequences (Seq Module)" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Lazy sequences represent potentially infinite collections where elements are computed on demand. Key difference from OCaml: 1. **Iterator vs Seq**: Rust's `Iterator` is inherently lazy — any iterator pipeline is a lazy sequence. OCaml's lists are eager; `Seq` is the explicit lazy alternative.

Tutorial

The Problem

Lazy sequences represent potentially infinite collections where elements are computed on demand. OCaml 4.07 added the Seq module for this purpose; Haskell uses lazy lists by default. The key insight: you can define let naturals = 0, 1, 2, ... as an infinite sequence and then take 10 to get the first 10 elements — without ever computing element 11.

Lazy sequences appear in: streaming data processing (reading lines from a file without loading it all), infinite mathematical sequences (primes, Fibonacci), event streams, and any scenario where the full sequence may not be needed or may not fit in memory. Rust's Iterator trait is inherently lazy.

🎯 Learning Outcomes

• Use std::iter::successors to generate sequences from a seed and step function

• Use std::iter::from_fn for sequences with mutable state

• Implement infinite sequences that only compute values when consumed

• Chain lazy operations (filter, map, take) without intermediate allocation

• Implement a finite unfold that stops when the state function returns None

• Create infinite sequences using std::iter::successors or Iterator::from_fn and consume finite prefixes with .take(n)

• Chain lazy operations (.map(), .filter()) that defer computation until a terminal consumer drives the iterator

Code Example

#![allow(clippy::all)]
/// # Seq Module — Lazy Sequences
///
/// Rust's iterator trait is inherently lazy — no need for a separate Seq module.
/// This demonstrates Rust's `std::iter` as the equivalent of OCaml's `Seq`.

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

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

/// Infinite primes using trial division (lazy — only computes as needed)
pub fn primes() -> impl Iterator<Item = u64> {
    (2u64..).filter(|&n| {
        let limit = (n as f64).sqrt() as u64;
        (2..=limit).all(|i| n % i != 0)
    })
}

/// `unfold` — Rust's equivalent is `std::iter::successors` or `std::iter::from_fn`
pub fn unfold<T, S>(seed: S, f: impl Fn(S) -> Option<(T, S)>) -> Vec<T>
where
    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
}

/// 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))
        }
    })
}

#[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_collatz() {
        assert_eq!(collatz(6), vec![6, 3, 10, 5, 16, 8, 4, 2, 1]);
    }

    #[test]
    fn test_lazy_computation() {
        // This doesn't compute all naturals — only the ones we take
        let sum: u64 = naturals(1).take(100).sum();
        assert_eq!(sum, 5050);
    }
}

(* Seq Module — Lazy Sequences in OCaml 4.14+ *)

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

Key Differences

Iterator vs Seq: Rust's Iterator is inherently lazy — any iterator pipeline is a lazy sequence. OCaml's lists are eager; Seq is the explicit lazy alternative.

Infinite iterators: Rust's 0.. is an infinite range. OCaml's lists are always finite; Seq is needed for infinite sequences.

**successors vs recursive Seq**: Rust's successors(seed, f) generates a sequence by repeatedly applying f. OCaml's recursive Seq nodes use closures/thunks to delay computation.

**take and collect**: Rust: .take(n).collect::<Vec<_>>(). OCaml: Seq.take n seq |> List.of_seq. Both materialize n elements from a potentially infinite sequence.

**Iterator as lazy sequence:** Rust's iterators are lazy by default — no computation happens until a consumer (.collect(), .sum(), .for_each()) drives the chain. OCaml's lazy values use lazy keyword and Lazy.force.

Infinite sequences: std::iter::successors(Some(0), |&n| Some(n + 1)) generates an infinite sequence. Combine with .take(n) to consume a finite prefix. OCaml uses let rec seq = lazy (...) for co-recursive lazy streams.

**Iterator::take_while:** Consume from an infinite sequence until a predicate fails: (0..).take_while(|&n| n < 100). OCaml's LazyList.take_while pred stream is the equivalent.

No memoization: Rust's lazy iterators are not memoized — re-consuming a filter().map() chain recomputes. OCaml's Lazy.t IS memoized — Lazy.force computes once and caches the result.

OCaml Approach

OCaml 4.07+ Seq module: let rec naturals n () = Seq.Cons (n, naturals (n + 1)). Taking n elements: Seq.take 10 (naturals 0) |> List.of_seq. Fibonacci: let rec fibs a b () = Seq.Cons (a, fibs b (a + b)). OCaml's Seq is a thunk-based lazy sequence: each element is a unit -> Seq.node function, computed on demand.

Full Source

#![allow(clippy::all)]
/// # Seq Module — Lazy Sequences
///
/// Rust's iterator trait is inherently lazy — no need for a separate Seq module.
/// This demonstrates Rust's `std::iter` as the equivalent of OCaml's `Seq`.

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

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

/// Infinite primes using trial division (lazy — only computes as needed)
pub fn primes() -> impl Iterator<Item = u64> {
    (2u64..).filter(|&n| {
        let limit = (n as f64).sqrt() as u64;
        (2..=limit).all(|i| n % i != 0)
    })
}

/// `unfold` — Rust's equivalent is `std::iter::successors` or `std::iter::from_fn`
pub fn unfold<T, S>(seed: S, f: impl Fn(S) -> Option<(T, S)>) -> Vec<T>
where
    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
}

/// 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))
        }
    })
}

#[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_collatz() {
        assert_eq!(collatz(6), vec![6, 3, 10, 5, 16, 8, 4, 2, 1]);
    }

    #[test]
    fn test_lazy_computation() {
        // This doesn't compute all naturals — only the ones we take
        let sum: u64 = naturals(1).take(100).sum();
        assert_eq!(sum, 5050);
    }
}

(* Seq Module — Lazy Sequences in OCaml 4.14+ *)

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_collatz() {
        assert_eq!(collatz(6), vec![6, 3, 10, 5, 16, 8, 4, 2, 1]);
    }

    #[test]
    fn test_lazy_computation() {
        // This doesn't compute all naturals — only the ones we take
        let sum: u64 = naturals(1).take(100).sum();
        assert_eq!(sum, 5050);
    }
}

Deep Comparison

Lazy Sequences — OCaml vs Rust Comparison

Core Insight

OCaml is strict (eager) by default and needs the Seq module for laziness. Rust iterators are lazy by default — chaining .filter().map().take() builds a pipeline that computes nothing until consumed by collect(), sum(), or for_each(). This makes Rust's approach to lazy sequences more natural.

OCaml Approach

The Seq module (OCaml 4.14+) provides Seq.ints, Seq.unfold, Seq.filter, Seq.take_while, etc. Under the hood, Seq uses thunks (unit -> 'a node) for lazy evaluation. Before Seq, OCaml programmers used custom stream types with explicit thunks.

Rust Approach

Infinite ranges (0u64..) are valid iterators. std::iter::successors generates sequences from a seed (like Seq.unfold). All iterator adaptors (.filter(), .map(), .take()) are lazy — they return new iterator types that wrap the original. The compiler monomorphizes the entire chain into efficient code.

Comparison Table

Aspect	OCaml	Rust
Memory	Thunk closures (GC'd)	Zero-alloc iterator state (stack)
Null safety	N/A	N/A
Errors	N/A	N/A
Iteration	`Seq.take` + `Seq.iter`	`.take(n).collect()` or `.for_each()`
Laziness	Explicit (Seq module)	Default (all iterators are lazy)

Things Rust Learners Should Notice

Ranges are iterators — 0.. is an infinite iterator, 0..10 is a finite one

**std::iter::successors** — Rust's equivalent of Seq.unfold for stateful generation

Zero-cost abstraction — the iterator chain compiles to a simple loop, no heap allocation

**impl Iterator<Item = T>** — return type hides the complex composed iterator type

Consuming adaptors — .collect(), .sum(), .count() trigger actual computation

Exercises

Sieve stream: Write prime_stream() returning an infinite iterator of primes using the sieve of Eratosthenes implemented as a lazy stream (not trial division). Each new prime filters multiples from the remaining stream.

Collatz stream: Write collatz_seq(n: u64) -> impl Iterator<Item=u64> that yields the Collatz sequence starting from n until 1. Use successors.

Memoized Fibonacci: Write a Fibonacci iterator that caches previously computed values using a Vec internally. Compare performance with the successors-based version for large n.

Fibonacci iterator: Implement a Fibonacci struct that implements Iterator<Item = u64> — each next() call returns the next Fibonacci number. Use successors(Some((0u64, 1u64)), |(a, b)| Some((*b, a + b))).map(|(a, _)| a).

Lazy sieve: Implement a lazy Sieve of Eratosthenes using an infinite iterator of integers, filtering out multiples of each discovered prime. Note: this is educational — a segmented sieve is faster in practice.

Open Source Repos

functional-rust

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

Rust

Tutorial Video

Tutorial

The Problem

🎯 Learning Outcomes

Code Example

Key Differences

OCaml Approach

Full Source

Deep Comparison

Lazy Sequences — OCaml vs Rust Comparison

Core Insight

OCaml Approach

Rust Approach

Comparison Table

Things Rust Learners Should Notice

Further Reading

Exercises

Open Source Repos