883 Intermediate

883-lazy-sequences — Lazy Sequences

Functional Programming

Tutorial

The Problem

Computing with infinite mathematical sequences — natural numbers, primes, Fibonacci numbers, powers — requires that elements be generated on demand rather than all at once. Lazy evaluation defers computation until results are needed, enabling programs to express "the first 100 primes" as concisely as "all primes." Haskell is lazy by default; OCaml uses Seq for explicit laziness. Rust's iterators are lazy by design: adapters like .map() and .filter() do nothing until consumed by .collect(), .take(), or .fold(). This makes Rust iterators ideal for modeling infinite mathematical sequences.

🎯 Learning Outcomes

• Build infinite lazy iterators using ranges, std::iter::successors, and from_fn

• Combine lazy generators with .filter() for sieve-like constructions

• Use .take_while() and .find() to safely consume infinite iterators

• Implement powers_of and triangle_numbers as lazy generators

• Compare Rust's lazy iterators with OCaml's explicit Seq laziness

Code Example

fn naturals() -> impl Iterator<Item = u64> {
    0u64..
}

let naturals () =
  let rec aux n () = Seq.Cons (n, aux (n + 1)) in
  aux 0

Key Differences

Implicit vs explicit laziness: Rust iterators are always lazy (adapters don't evaluate); OCaml Seq makes laziness explicit via unit -> thunks.

State representation: Rust lazy state lives in the struct (e.g., Fibonacci { a, b }); OCaml Seq.unfold threads state functionally.

Overflow safety: successors with checked_mul gracefully terminates on overflow; OCaml requires explicit bounds checking.

Composability: Both compose lazy sequences using map/filter/take; Rust uses method chaining, OCaml uses |> pipe.

OCaml Approach

OCaml Seq uses explicit thunking: let naturals () = Seq.unfold (fun n -> Some(n, n+1)) 0. Each element is a closure that evaluates the next on demand. Seq.filter is_prime (naturals ()) creates a lazy primes sequence. List.of_seq (Seq.take 10 primes_seq) materializes the first 10. OCaml's Seq is more explicit about laziness (each Cons node is a unit -> _ closure), while Rust's iterator laziness is baked into the trait design.

Full Source

#![allow(clippy::all)]
// Example 089: Lazy Sequences
// OCaml Seq → Rust Iterator + take

// === Approach 1: Infinite iterators with closures ===
fn naturals() -> impl Iterator<Item = u64> {
    0u64..
}

fn squares() -> impl Iterator<Item = u64> {
    naturals().map(|n| n * n)
}

fn is_prime(n: u64) -> bool {
    if n < 2 {
        return false;
    }
    let mut d = 2;
    while d * d <= n {
        if n % d == 0 {
            return false;
        }
        d += 1;
    }
    true
}

fn primes() -> impl Iterator<Item = u64> {
    naturals().filter(|&n| is_prime(n))
}

// === Approach 2: Custom lazy generators ===
fn powers_of(base: u64) -> impl Iterator<Item = u64> {
    std::iter::successors(Some(1u64), move |&prev| prev.checked_mul(base))
}

fn triangle_numbers() -> impl Iterator<Item = u64> {
    naturals().skip(1).scan(0u64, |acc, n| {
        *acc += n;
        Some(*acc)
    })
}

// === Approach 3: take_while / skip_while ===
fn primes_below(limit: u64) -> Vec<u64> {
    primes().take_while(|&p| p < limit).collect()
}

fn first_prime_over(threshold: u64) -> Option<u64> {
    primes().find(|&p| p > threshold)
}

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

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

    #[test]
    fn test_squares() {
        let v: Vec<u64> = squares().take(5).collect();
        assert_eq!(v, vec![0, 1, 4, 9, 16]);
    }

    #[test]
    fn test_primes() {
        let v: Vec<u64> = primes().take(5).collect();
        assert_eq!(v, vec![2, 3, 5, 7, 11]);
    }

    #[test]
    fn test_powers_of_2() {
        let v: Vec<u64> = powers_of(2).take(5).collect();
        assert_eq!(v, vec![1, 2, 4, 8, 16]);
    }

    #[test]
    fn test_powers_of_3() {
        let v: Vec<u64> = powers_of(3).take(4).collect();
        assert_eq!(v, vec![1, 3, 9, 27]);
    }

    #[test]
    fn test_triangle_numbers() {
        let v: Vec<u64> = triangle_numbers().take(5).collect();
        assert_eq!(v, vec![1, 3, 6, 10, 15]);
    }

    #[test]
    fn test_primes_below() {
        assert_eq!(primes_below(20), vec![2, 3, 5, 7, 11, 13, 17, 19]);
    }

    #[test]
    fn test_first_prime_over() {
        assert_eq!(first_prime_over(100), Some(101));
    }

    #[test]
    fn test_lazy_composition() {
        let count = naturals().filter(|n| n % 2 == 0).take(100).count();
        assert_eq!(count, 100);
    }
}

(* Example 089: Lazy Sequences *)
(* OCaml Seq → Rust Iterator + take *)

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

let squares () =
  Seq.map (fun n -> n * n) (naturals ())

let primes () =
  let is_prime n =
    if n < 2 then false
    else
      let rec check d = d * d > n || (n mod d <> 0 && check (d + 1)) in
      check 2
  in
  Seq.filter is_prime (naturals ())

(* Approach 2: Recursive lazy generation *)
let powers_of base =
  let rec aux p () = Seq.Cons (p, aux (p * base)) in
  aux 1

let triangle_numbers () =
  let rec aux n sum () =
    let new_sum = sum + n in
    Seq.Cons (new_sum, aux (n + 1) new_sum)
  in
  aux 1 0

(* Approach 3: Seq operations on infinite sequences *)
let seq_take n seq =
  let rec aux n seq acc =
    if n = 0 then List.rev acc
    else match seq () with
    | Seq.Nil -> List.rev acc
    | Seq.Cons (x, rest) -> aux (n - 1) rest (x :: acc)
  in
  aux n seq []

let seq_drop_while pred seq =
  let rec aux seq () =
    match seq () with
    | Seq.Nil -> Seq.Nil
    | Seq.Cons (x, rest) ->
      if pred x then aux rest ()
      else Seq.Cons (x, rest)
  in
  aux seq

let seq_take_while pred seq =
  let rec aux seq () =
    match seq () with
    | Seq.Nil -> Seq.Nil
    | Seq.Cons (x, rest) ->
      if pred x then Seq.Cons (x, aux rest)
      else Seq.Nil
  in
  aux seq

(* Tests *)
let () =
  assert (seq_take 5 (naturals ()) = [0; 1; 2; 3; 4]);
  assert (seq_take 5 (squares ()) = [0; 1; 4; 9; 16]);
  assert (seq_take 5 (primes ()) = [2; 3; 5; 7; 11]);
  assert (seq_take 5 (powers_of 2) = [1; 2; 4; 8; 16]);
  assert (seq_take 5 (triangle_numbers ()) = [1; 3; 6; 10; 15]);

  let first_prime_over_100 = seq_take 1 (seq_drop_while (fun x -> x <= 100) (primes ())) in
  assert (first_prime_over_100 = [101]);

  let small_primes = seq_take 100 (seq_take_while (fun x -> x < 20) (primes ())) in
  assert (small_primes = [2; 3; 5; 7; 11; 13; 17; 19]);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

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

    #[test]
    fn test_squares() {
        let v: Vec<u64> = squares().take(5).collect();
        assert_eq!(v, vec![0, 1, 4, 9, 16]);
    }

    #[test]
    fn test_primes() {
        let v: Vec<u64> = primes().take(5).collect();
        assert_eq!(v, vec![2, 3, 5, 7, 11]);
    }

    #[test]
    fn test_powers_of_2() {
        let v: Vec<u64> = powers_of(2).take(5).collect();
        assert_eq!(v, vec![1, 2, 4, 8, 16]);
    }

    #[test]
    fn test_powers_of_3() {
        let v: Vec<u64> = powers_of(3).take(4).collect();
        assert_eq!(v, vec![1, 3, 9, 27]);
    }

    #[test]
    fn test_triangle_numbers() {
        let v: Vec<u64> = triangle_numbers().take(5).collect();
        assert_eq!(v, vec![1, 3, 6, 10, 15]);
    }

    #[test]
    fn test_primes_below() {
        assert_eq!(primes_below(20), vec![2, 3, 5, 7, 11, 13, 17, 19]);
    }

    #[test]
    fn test_first_prime_over() {
        assert_eq!(first_prime_over(100), Some(101));
    }

    #[test]
    fn test_lazy_composition() {
        let count = naturals().filter(|n| n % 2 == 0).take(100).count();
        assert_eq!(count, 100);
    }
}

Deep Comparison

Comparison: Lazy Sequences

Infinite Naturals

OCaml:

let naturals () =
  let rec aux n () = Seq.Cons (n, aux (n + 1)) in
  aux 0

Rust:

fn naturals() -> impl Iterator<Item = u64> {
    0u64..
}

Derived Sequences

OCaml:

let squares () = Seq.map (fun n -> n * n) (naturals ())
let primes () = Seq.filter is_prime (naturals ())

Rust:

fn squares() -> impl Iterator<Item = u64> { naturals().map(|n| n * n) }
fn primes() -> impl Iterator<Item = u64> { naturals().filter(|&n| is_prime(n)) }

Recursive Generation

OCaml:

let powers_of base =
  let rec aux p () = Seq.Cons (p, aux (p * base)) in
  aux 1

Rust:

fn powers_of(base: u64) -> impl Iterator<Item = u64> {
    std::iter::successors(Some(1u64), move |&prev| prev.checked_mul(base))
}

Consuming Infinite Sequences

OCaml:

let small_primes = seq_take_while (fun x -> x < 20) (primes ())
let first_big = seq_drop_while (fun x -> x <= 100) (primes ())

Rust:

let small_primes: Vec<_> = primes().take_while(|&p| p < 20).collect();
let first_big = primes().find(|&p| p > 100);

Exercises

Implement a lazy happy_numbers() iterator that yields numbers whose digit-square-sum eventually reaches 1.

Write prime_pairs() that lazily yields twin primes (p, p+2) using zip and filter over the primes iterator.

Implement memoized_fibonacci() as a lazy iterator backed by a cache to avoid recomputing previous values.

Open Source Repos

functional-rust

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

Rust