281 Intermediate

281: Implementing the Iterator Trait from Scratch

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "281: Implementing the Iterator Trait from Scratch" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Every iterator in Rust's standard library is built from the same foundation: a struct with state and a single `next()` method. Key difference from OCaml: 1. **Interface size**: Rust's `Iterator` requires one method; OCaml's `Seq` is just a function type — both are minimal.

Tutorial

The Problem

Every iterator in Rust's standard library is built from the same foundation: a struct with state and a single next() method. Understanding this foundation is essential for building domain-specific sequences — streaming database rows, generating mathematical sequences, traversing custom data structures, or implementing infinite value generators. The entire iterator adapter ecosystem (map, filter, zip, etc.) becomes available for free once next() is implemented.

🎯 Learning Outcomes

• Understand that implementing Iterator requires only defining type Item and fn next(&mut self) -> Option<Self::Item>

• Recognize that all other iterator adapters (map, filter, sum, etc.) are provided for free by the trait

• Build stateful iterators using struct fields to track iteration progress

• Implement custom termination logic by returning None from next()

Code Example

struct Squares { current: u32, max: u32 }

impl Iterator for Squares {
    type Item = u32;
    
    fn next(&mut self) -> Option<Self::Item> {
        if self.current >= self.max { return None; }
        let val = self.current * self.current;
        self.current += 1;
        Some(val)
    }
}

type 'a counter = {
  mutable current: int;
  max: int;
  step: int;
  f: int -> 'a;
}

let counter_next c =
  if c.current >= c.max then None
  else begin
    let v = c.f c.current in
    c.current <- c.current + c.step;
    Some v
  end

let counter_to_seq c =
  Seq.unfold (fun () ->
    counter_next c |> Option.map (fun v -> (v, ()))
  ) ()

Key Differences

Interface size: Rust's Iterator requires one method; OCaml's Seq is just a function type — both are minimal.

Free methods: Rust's Iterator provides ~70 free methods once next() is implemented; OCaml's Seq module provides a smaller set.

State representation: Rust stores state in a struct with named fields; OCaml uses closure-captured variables.

Type safety: Rust's type Item makes the element type explicit in the trait; OCaml's 'a Seq.t is polymorphic.

OCaml Approach

OCaml does not have a single iterator trait. The closest equivalent is the Seq module's lazy sequence type, which is a function unit -> 'a node where node is Nil | Cons of 'a * 'a Seq.t. A custom generator is a closure returning the next Cons or Nil:

let squares max =
  let rec go n () =
    if n >= max then Seq.Nil
    else Seq.Cons (n * n, go (n + 1))
  in go 0
(* All Seq combinators (map, filter, fold_left) work on this *)

Full Source

#![allow(clippy::all)]
//! # Custom Iterator Implementation
//!
//! Demonstrates implementing the `Iterator` trait from scratch.
//! Only `next()` is required — the rest of the iterator API comes for free.

/// A counter that yields squares up to a maximum
pub struct Squares {
    current: u32,
    max: u32,
}

impl Squares {
    pub fn new(max: u32) -> Self {
        Squares { current: 0, max }
    }
}

impl Iterator for Squares {
    type Item = u32;

    fn next(&mut self) -> Option<Self::Item> {
        if self.current >= self.max {
            return None;
        }
        let val = self.current * self.current;
        self.current += 1;
        Some(val)
    }
}

/// Fibonacci sequence iterator - infinite, always returns Some
pub struct Fibonacci {
    a: u64,
    b: u64,
}

impl Fibonacci {
    pub fn new() -> Self {
        Fibonacci { a: 0, b: 1 }
    }
}

impl Default for Fibonacci {
    fn default() -> Self {
        Self::new()
    }
}

impl Iterator for Fibonacci {
    type Item = u64;

    fn next(&mut self) -> Option<Self::Item> {
        let val = self.a;
        let next = self.a + self.b;
        self.a = self.b;
        self.b = next;
        Some(val) // infinite — always Some
    }
}

/// Alternative: A range iterator using step
pub struct SteppedRange {
    current: i32,
    end: i32,
    step: i32,
}

impl SteppedRange {
    pub fn new(start: i32, end: i32, step: i32) -> Self {
        SteppedRange {
            current: start,
            end,
            step,
        }
    }
}

impl Iterator for SteppedRange {
    type Item = i32;

    fn next(&mut self) -> Option<Self::Item> {
        if (self.step > 0 && self.current >= self.end)
            || (self.step < 0 && self.current <= self.end)
        {
            return None;
        }
        let val = self.current;
        self.current += self.step;
        Some(val)
    }
}

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

    #[test]
    fn test_squares_collect() {
        let result: Vec<u32> = Squares::new(5).collect();
        assert_eq!(result, vec![0, 1, 4, 9, 16]);
    }

    #[test]
    fn test_squares_sum() {
        let sum: u32 = Squares::new(4).sum();
        assert_eq!(sum, 0 + 1 + 4 + 9);
    }

    #[test]
    fn test_squares_filter() {
        let big: Vec<u32> = Squares::new(10).filter(|&x| x > 10).collect();
        assert_eq!(big, vec![16, 25, 36, 49, 64, 81]);
    }

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

    #[test]
    fn test_fibonacci_filter() {
        let even_fibs: Vec<u64> = Fibonacci::new().take(10).filter(|x| x % 2 == 0).collect();
        assert_eq!(even_fibs, vec![0, 2, 8, 34]);
    }

    #[test]
    fn test_stepped_range() {
        let result: Vec<i32> = SteppedRange::new(0, 10, 2).collect();
        assert_eq!(result, vec![0, 2, 4, 6, 8]);
    }

    #[test]
    fn test_stepped_range_negative() {
        let result: Vec<i32> = SteppedRange::new(10, 0, -3).collect();
        assert_eq!(result, vec![10, 7, 4, 1]);
    }

    #[test]
    fn test_zip_custom_iterators() {
        let zipped: Vec<(u32, u64)> = Squares::new(5).zip(Fibonacci::new()).collect();
        assert_eq!(zipped, vec![(0, 0), (1, 1), (4, 1), (9, 2), (16, 3)]);
    }
}

(* 281. Implementing Iterator trait from scratch - OCaml *)
(* OCaml uses Seq.t for lazy sequences *)

type 'a counter = {
  mutable current: int;
  max: int;
  step: int;
  f: int -> 'a;
}

let make_counter ?(step=1) max f =
  { current = 0; max; step; f }

let counter_next c =
  if c.current >= c.max then None
  else begin
    let v = c.f c.current in
    c.current <- c.current + c.step;
    Some v
  end

let counter_to_seq c =
  Seq.unfold (fun () ->
    counter_next c |> Option.map (fun v -> (v, ()))
  ) ()

let () =
  let c = make_counter 5 (fun i -> i * i) in
  let squares = counter_to_seq c |> List.of_seq in
  Printf.printf "Squares: %s\n"
    (String.concat ", " (List.map string_of_int squares));

  (* Fibonacci sequence as lazy iterator *)
  let fib_seq =
    Seq.unfold (fun (a, b) -> Some (a, (b, a + b))) (0, 1)
  in
  let first10 = Seq.take 10 fib_seq |> List.of_seq in
  Printf.printf "First 10 Fibonacci: %s\n"
    (String.concat ", " (List.map string_of_int first10))

✓ Tests Rust test suite

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

    #[test]
    fn test_squares_collect() {
        let result: Vec<u32> = Squares::new(5).collect();
        assert_eq!(result, vec![0, 1, 4, 9, 16]);
    }

    #[test]
    fn test_squares_sum() {
        let sum: u32 = Squares::new(4).sum();
        assert_eq!(sum, 0 + 1 + 4 + 9);
    }

    #[test]
    fn test_squares_filter() {
        let big: Vec<u32> = Squares::new(10).filter(|&x| x > 10).collect();
        assert_eq!(big, vec![16, 25, 36, 49, 64, 81]);
    }

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

    #[test]
    fn test_fibonacci_filter() {
        let even_fibs: Vec<u64> = Fibonacci::new().take(10).filter(|x| x % 2 == 0).collect();
        assert_eq!(even_fibs, vec![0, 2, 8, 34]);
    }

    #[test]
    fn test_stepped_range() {
        let result: Vec<i32> = SteppedRange::new(0, 10, 2).collect();
        assert_eq!(result, vec![0, 2, 4, 6, 8]);
    }

    #[test]
    fn test_stepped_range_negative() {
        let result: Vec<i32> = SteppedRange::new(10, 0, -3).collect();
        assert_eq!(result, vec![10, 7, 4, 1]);
    }

    #[test]
    fn test_zip_custom_iterators() {
        let zipped: Vec<(u32, u64)> = Squares::new(5).zip(Fibonacci::new()).collect();
        assert_eq!(zipped, vec![(0, 0), (1, 1), (4, 1), (9, 2), (16, 3)]);
    }
}

Deep Comparison

OCaml vs Rust: Custom Iterator

Pattern 1: Custom Sequence Type

OCaml

type 'a counter = {
  mutable current: int;
  max: int;
  step: int;
  f: int -> 'a;
}

let counter_next c =
  if c.current >= c.max then None
  else begin
    let v = c.f c.current in
    c.current <- c.current + c.step;
    Some v
  end

let counter_to_seq c =
  Seq.unfold (fun () ->
    counter_next c |> Option.map (fun v -> (v, ()))
  ) ()

Rust

struct Squares { current: u32, max: u32 }

impl Iterator for Squares {
    type Item = u32;
    
    fn next(&mut self) -> Option<Self::Item> {
        if self.current >= self.max { return None; }
        let val = self.current * self.current;
        self.current += 1;
        Some(val)
    }
}

Pattern 2: Infinite Sequence (Fibonacci)

OCaml

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

let first10 = Seq.take 10 fib_seq |> List.of_seq

Rust

struct Fibonacci { a: u64, b: u64 }

impl Iterator for Fibonacci {
    type Item = u64;
    fn next(&mut self) -> Option<u64> {
        let val = self.a;
        self.a = self.b;
        self.b = val + self.b;
        Some(val)  // always Some — infinite
    }
}

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

Pattern 3: Using Iterator Adapters

OCaml

let result = 
  counter_to_seq (make_counter 10 (fun i -> i * i))
  |> Seq.filter (fun x -> x > 10)
  |> List.of_seq

Rust

let result: Vec<u32> = Squares::new(10)
    .filter(|&x| x > 10)
    .collect();

Key Differences

Aspect	OCaml	Rust
Trait required	None (use `Seq.unfold`)	Implement `Iterator` trait
Minimum method	`unit -> 'a Seq.node`	`fn next(&mut self) -> Option<Item>`
State storage	Closure captures	Struct fields
Adapters	Separate `Seq.*` functions	Methods on `Iterator` trait
Method chaining	`\|>` pipeline operator	`.method().method()`
Infinite sequences	Natural with `Seq.unfold`	Return `Some` forever, use `take()`

Exercises

Implement a Fibonacci iterator struct that yields Fibonacci numbers indefinitely using two accumulator fields.

Implement a Range iterator struct that yields integers from start to end with a configurable step size.

Implement a TakeWhile adapter struct that wraps another iterator and stops when a predicate returns false — implement Iterator on it manually.

Open Source Repos

functional-rust

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

Rust