🦀 Functional Rust

089: Lazy Sequences

Difficulty: 2 Level: Intermediate Build infinite sequences — natural numbers, primes, triangle numbers, powers — and consume exactly as many elements as you need with `take`, `take_while`, and `find`.

The Problem This Solves

Some sequences are naturally infinite: the natural numbers, prime numbers, Fibonacci, powers of two. To work with them you need laziness — a way to describe "all primes" without computing them all upfront (which would take forever). The imperative approach is a stateful loop with a break condition. You need to track state manually, mix generation with consumption, and repeat the same boilerplate for every sequence. The result is code where the algorithm for generating the sequence is tangled with the logic for using it. Lazy iterators separate these concerns cleanly. Define how to produce the next element; let the consumer decide how many to take. The generator runs only as far as needed.

The Intuition

In Python, `itertools.count()` is an infinite iterator; generator functions with `yield` create lazy sequences. In OCaml, `Seq.t` is a lazy type — a `unit -> node` function that produces elements on demand. In Haskell, all lists are lazy by default. Rust's iterators are lazy by design — nothing runs until consumed. This means `(0u64..).filter(is_prime)` really is "all primes" as an iterator. It doesn't compute anything until you call `.take(10)` or `.find(|p| *p > 100)`. The difference from Haskell: Rust iterators are pull-based (the consumer drives) and stateful (mutable `next()` method). The laziness is explicit — you know exactly when computation happens.

How It Works in Rust

// Infinite ranges — the simplest lazy sequence
fn naturals() -> impl Iterator<Item = u64> {
 0u64..   // range with no upper bound — lazy, computes nothing yet
}

// Compose lazy sequences
fn squares() -> impl Iterator<Item = u64> {
 naturals().map(|n| n * n)   // still lazy — just describes the transformation
}
// Filter over an infinite sequence — still lazy
fn primes() -> impl Iterator<Item = u64> {
 naturals().filter(|&n| is_prime(n))
}

// Nothing computed until we consume with take()
let first_ten: Vec<u64> = primes().take(10).collect();
let primes_below_100: Vec<u64> = primes().take_while(|&p| p < 100).collect();
let first_big_prime = primes().find(|&p| p > 1_000_000);
// successors: generate sequences where each element depends on the previous
fn powers_of(base: u64) -> impl Iterator<Item = u64> {
 std::iter::successors(Some(1u64), move |&prev| {
     prev.checked_mul(base)  // returns None on overflow — sequence ends naturally
 })
}

// scan: like fold but yields each intermediate accumulator
fn triangle_numbers() -> impl Iterator<Item = u64> {
 (1u64..).scan(0u64, |acc, n| {
     *acc += n;
     Some(*acc)   // yields running sum: 1, 3, 6, 10, 15, ...
 })
}
// Compose multiple lazy operations — still nothing computed
let result: Vec<u64> = naturals()
 .filter(|n| n % 3 == 0)    // multiples of 3
 .map(|n| n * n)              // their squares
 .take_while(|&n| n < 1000)  // only those below 1000
 .collect();                  // NOW it computes — just enough elements

What This Unlocks

Key Differences

ConceptOCamlRust
Lazy sequence type`Seq.t = unit -> node``impl Iterator<Item = T>`
Infinite sequence`Seq.unfold``(0..)` range or `iter::successors`
Take N elements`Seq.take``.take(n)`
Take while condition`Seq.take_while``.take_while(pred)`
Running accumulator`Seq.scan` or manual`.scan(init, f)`
When computation happensOn each `Seq.next` callOn each `Iterator::next()` call
// 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)
}

fn main() {
    println!("First 10 naturals: {:?}", naturals().take(10).collect::<Vec<_>>());
    println!("First 5 squares: {:?}", squares().take(5).collect::<Vec<_>>());
    println!("First 10 primes: {:?}", primes().take(10).collect::<Vec<_>>());
    println!("Powers of 2: {:?}", powers_of(2).take(10).collect::<Vec<_>>());
    println!("Triangle numbers: {:?}", triangle_numbers().take(5).collect::<Vec<_>>());
    println!("Primes below 20: {:?}", primes_below(20));
    println!("First prime over 100: {:?}", first_prime_over(100));

    // Lazy composition — nothing computed until .collect()
    let result: Vec<u64> = naturals()
        .filter(|n| n % 3 == 0)
        .map(|n| n * n)
        .take_while(|&n| n < 1000)
        .collect();
    println!("Squares of multiples of 3 below 1000: {:?}", result);
}

#[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"

📊 Detailed Comparison

Comparison: Lazy Sequences

Infinite Naturals

OCaml:

🐪 Show OCaml equivalent
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:

🐪 Show OCaml equivalent
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:

🐪 Show OCaml equivalent
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:

🐪 Show OCaml equivalent
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);

Related Examples

#882 088: Iterator Consumers 🌱 #884 090: Infinite Iterators 🌱 #885 091: Zip and Unzip 🌱 #886 092: Scan / Accumulate 🌱
All Examples