🎬 How Rust Iterators Work Lazy evaluation, chaining, collect(), and zero-cost abstractions.

📝 Text version (for readers / accessibility)

• Iterators are lazy — .map(), .filter(), .take() build a chain but do no work until consumed

• .collect() triggers evaluation, transforming the chain into a Vec, HashMap, or other collection

• Zero-cost abstraction: iterator chains compile to the same machine code as hand-written loops

• .iter() borrows, .into_iter() consumes, .iter_mut() borrows mutably

• Chaining replaces nested loops with a readable, composable pipeline

255: Lazy Fibonacci

Difficulty: 2 Level: Intermediate Generate an infinite Fibonacci sequence without computing all of it — take only what you need, when you need it.

The Problem This Solves

The Fibonacci sequence is infinite. You can't compute it all before you use it. But often you need a prefix: the first 10, the first 100, however many satisfy some condition. The challenge is decoupling "how to generate the next value" from "how many values to consume". Eager languages compute everything upfront. A function returning a list of Fibonacci numbers must know in advance how many to generate — hard-code a limit, or blow the stack with naive recursion. Lazy evaluation solves this by deferring each computation until it's actually needed. This example shows two Rust approaches: the idiomatic `Iterator` (lazy by design, zero overhead, understood by the entire standard library) and a thunk-based `Stream` that mirrors OCaml's coinductive stream type exactly. Both are safe with infinite sequences as long as you only force a finite prefix.

The Intuition

A lazy sequence is like a vending machine: you press the button to get the next item. The machine doesn't pre-fill all the items — it generates each one on demand. Pressing the button 10 times gives you 10 items; the machine could keep going forever. OCaml's stream stores each tail as a thunk — a `fun () -> ...` — which is a suspended computation. The tail doesn't exist until you call it. Rust's `Iterator` trait works the same way: `next()` produces one value on each call, and the struct holds just enough state (two numbers) to compute the next. A `move` closure in Rust captures its variables by ownership. Each thunk owns its two Fibonacci numbers independently — no shared state, no borrowing complications, stack-safe for any depth.

How It Works in Rust

// Style 1: Idiomatic — implement Iterator, use the standard library for free
pub struct FibIter { a: u64, b: u64 }

impl Iterator for FibIter {
 type Item = u64;
 fn next(&mut self) -> Option<u64> {
     let value = self.a;
     let next_b = self.a + self.b;  // compute next before updating
     self.a = self.b;
     self.b = next_b;
     Some(value)  // never returns None — infinite iterator
 }
}

// Use: take first 10 Fibonacci numbers
let fibs: Vec<u64> = FibIter { a: 0, b: 1 }.take(10).collect();
// → [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

// Style 2: Thunk-based — mirrors OCaml's stream type exactly
struct Stream<T> {
 head: T,
 tail: Box<dyn Fn() -> Stream<T>>,  // Box required: Stream contains itself
}

fn fibs_stream(a: u64, b: u64) -> Stream<u64> {
 Stream {
     head: a,
     tail: Box::new(move || fibs_stream(b, a + b)),  // move captures a, b by value
 }
}

fn take_stream<T: Clone>(n: usize, s: Stream<T>) -> Vec<T> {
 if n == 0 { return vec![]; }
 let mut result = vec![s.head.clone()];
 result.extend(take_stream(n - 1, (s.tail)()));
 result
}

What This Unlocks

Infinite sequences — primes, factorials, random numbers, sensor readings: any sequence where you don't know the length upfront.
On-demand computation — combine with `take_while`, `filter`, `zip` to compute only what a downstream consumer needs.
Memory efficiency — `FibIter` holds two `u64` values regardless of how many elements you take; no list grows in memory.

Key Differences

Concept	OCaml	Rust
Lazy abstraction	Custom `'a stream` type with thunks	`Iterator` trait — standard library aware
Heap indirection	GC handles recursive type transparently	`Box<dyn Fn()>` required for recursive type
Closure capture	By reference (GC-managed)	`move` closure — takes ownership
Infinite safety	Safe if only `take n` is forced	Safe — `Iterator::take` is finite
Standard library	Custom `take`, `map` needed	`take`, `map`, `filter`, `zip` all built in

// Example 255: Lazy Fibonacci — Infinite stream using closures/iterators

// ---------------------------------------------------------------------------
// Solution 1: Idiomatic Rust — Iterator
// ---------------------------------------------------------------------------

pub struct FibIter {
    a: u64,
    b: u64,
}

impl FibIter {
    pub fn new(a: u64, b: u64) -> Self {
        Self { a, b }
    }
}

impl Iterator for FibIter {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let value = self.a;
        let next_b = self.a + self.b;
        self.a = self.b;
        self.b = next_b;
        Some(value)
    }
}

pub fn fibs_take(n: usize) -> Vec<u64> {
    FibIter::new(0, 1).take(n).collect()
}

// ---------------------------------------------------------------------------
// Solution 2: Thunk-based stream — mirrors OCaml's stream type
//
//   OCaml: type 'a stream = Cons of 'a * (unit -> 'a stream)
// ---------------------------------------------------------------------------

pub struct Stream<T> {
    pub head: T,
    tail: Box<dyn Fn() -> Stream<T>>,
}

impl<T: Copy> Stream<T> {
    pub fn take(&self, n: usize) -> Vec<T> {
        let mut result = Vec::with_capacity(n);
        if n == 0 {
            return result;
        }
        result.push(self.head);
        let mut next = (self.tail)();
        for _ in 1..n {
            result.push(next.head);
            next = (next.tail)();
        }
        result
    }
}

pub fn fibs_stream(a: u64, b: u64) -> Stream<u64> {
    Stream {
        head: a,
        tail: Box::new(move || fibs_stream(b, a + b)),
    }
}

// ---------------------------------------------------------------------------

fn main() {
    // Iterator approach
    let first_ten: Vec<u64> = FibIter::new(0, 1).take(10).collect();
    println!("Iterator — first 10 fibs: {:?}", first_ten);

    // Convenience helper
    println!("fibs_take(5)             : {:?}", fibs_take(5));

    // Stream (thunk) approach
    let stream = fibs_stream(0, 1);
    println!("Stream   — first 10 fibs: {:?}", stream.take(10));

    // Composing with other Iterator adapters
    let evens: Vec<u64> = FibIter::new(0, 1)
        .filter(|x| x % 2 == 0)
        .take(5)
        .collect();
    println!("Even fibs (first 5)      : {:?}", evens);
}

/* Output:
   Iterator — first 10 fibs: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
   fibs_take(5)             : [0, 1, 1, 2, 3]
   Stream   — first 10 fibs: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
   Even fibs (first 5)      : [0, 2, 8, 34, 144]
*/

(* Example 255: Lazy Fibonacci — Infinite stream using thunks *)

(* Idiomatic OCaml: coinductive stream type *)
type 'a stream = Cons of 'a * (unit -> 'a stream)

(* Build an infinite Fibonacci stream starting from (a, b) *)
let rec fibs a b = Cons (a, fun () -> fibs b (a + b))

(* Take the first n elements from a stream *)
let rec take n (Cons (x, rest)) =
  if n = 0 then []
  else x :: take (n - 1) (rest ())

(* Recursive: peek at the nth element *)
let rec nth n (Cons (x, rest)) =
  if n = 0 then x
  else nth (n - 1) (rest ())

let () =
  let fib_stream = fibs 0 1 in
  let first_ten = take 10 fib_stream in
  assert (first_ten = [0; 1; 1; 2; 3; 5; 8; 13; 21; 34]);
  assert (nth 0 fib_stream = 0);
  assert (nth 9 fib_stream = 34);
  assert (take 5 (fibs 1 1) = [1; 1; 2; 3; 5]);
  List.iter (Printf.printf "%d ") first_ten;
  print_newline ();
  print_endline "ok"

📊 Detailed Comparison

OCaml vs Rust: Lazy Fibonacci Stream

Side-by-Side Code

OCaml

🐪 Show OCaml equivalent

type 'a stream = Cons of 'a * (unit -> 'a stream)

let rec fibs a b = Cons (a, fun () -> fibs b (a + b))

let rec take n (Cons (x, rest)) =
if n = 0 then []
else x :: take (n - 1) (rest ())

let () =
let fib_stream = fibs 0 1 in
List.iter (Printf.printf "%d ") (take 10 fib_stream)

Rust (idiomatic — Iterator)

pub struct FibIter { a: u64, b: u64 }

impl Iterator for FibIter {
 type Item = u64;
 fn next(&mut self) -> Option<u64> {
     let value = self.a;
     let next_b = self.a + self.b;
     self.a = self.b;
     self.b = next_b;
     Some(value)
 }
}

// Usage: FibIter { a: 0, b: 1 }.take(10).collect::<Vec<_>>()

Rust (functional — thunk-based, mirrors OCaml)

pub struct Stream<T> {
 pub head: T,
 tail: Box<dyn Fn() -> Stream<T>>,  // the thunk
}

pub fn fibs_stream(a: u64, b: u64) -> Stream<u64> {
 Stream {
     head: a,
     tail: Box::new(move || fibs_stream(b, a + b)),
 }
}

Type Signatures

Concept	OCaml	Rust (Iterator)	Rust (Stream)
Stream type	`'a stream`	`impl Iterator<Item=u64>`	`Stream<u64>`
Infinite generator	`val fibs : int -> int -> int stream`	`FibIter::new(u64, u64) -> FibIter`	`fn fibs_stream(u64, u64) -> Stream<u64>`
Take prefix	`val take : int -> 'a stream -> 'a list`	`.take(n).collect::<Vec<_>>()`	`stream.take(n) -> Vec<u64>`
Thunk type	`unit -> 'a stream`	N/A (implicit in `next`)	`Box<dyn Fn() -> Stream<T>>`

Key Insights

1. `Iterator` is Rust's stream abstraction. OCaml's `stream` type is a library-level concept; Rust bakes lazy sequences into the language via the `Iterator` trait. The entire `std` ecosystem (`.map`, `.filter`, `.take`, `.zip`, ...) composes freely with any `Iterator`, including infinite ones.

2. Recursive types require `Box`. OCaml's GC tracks object sizes at runtime, so `type 'a stream = Cons of 'a * (unit -> 'a stream)` compiles fine. In Rust every type must have a statically-known size. `Stream<T>` contains a `Box<dyn Fn()...>` (pointer — fixed 16 bytes) rather than `Stream<T>` itself (infinite size), making the type representable.

3. `move` closures replace GC-managed capture. OCaml closures automatically capture variables from the enclosing scope via the GC. Rust's `move` keyword transfers ownership of `a` and `b` into the closure, making it `'static` and independent of any stack frame — a necessary trade-off for memory safety without GC.

4. No-allocation iteration is possible. The `FibIter` approach stores only two `u64` values on the stack. OCaml's `stream` allocates a `Cons` cell on the heap for every element produced. Rust lets you choose the trade-off: use the Iterator for zero allocation, or the `Stream` type to mirror OCaml's structure exactly.

5. Composability. Because `FibIter` implements `Iterator`, you can write `FibIter::new(0,1).filter(|x| x % 2 == 0).take(5).sum::<u64>()` with no extra code. The thunk-based `Stream` would need manual implementations of each combinator.

When to Use Each Style

Use idiomatic Rust (Iterator) when: you want zero-allocation lazy sequences that compose naturally with the rest of `std`, which is almost always.

Use thunk-based Rust (Stream) when: you are teaching the OCaml→Rust translation, need an explicit coinductive structure (e.g. for tree streams), or want to experiment with custom stream combinators that diverge from `Iterator`.