085 Intermediate

085 — Iterator Trait

Functional Programming

Tutorial

The Problem

Implement the Iterator trait from scratch for two custom types: a bounded MyRange iterator and an infinite Fibonacci iterator. By implementing only next, gain access to the entire iterator adapter ecosystem (filter, map, take, collect). Compare with OCaml's Seq type and lazy sequence operations.

🎯 Learning Outcomes

• Implement Iterator by defining only fn next(&mut self) -> Option<Self::Item>

• Understand that all other iterator methods (map, filter, collect) come for free

• Create an infinite iterator and use .take(n) to bound it safely

• Use type Item = i32 as the associated type required by Iterator

• Map Rust's iterator protocol to OCaml's 'a Seq.t = unit -> 'a Seq.node lazy type

• Recognise when to implement Iterator vs using iter() on existing collections

Code Example

#![allow(clippy::all)]
// 085: Iterator Trait — implement from scratch

// Approach 1: Range iterator
struct MyRange {
    current: i32,
    end_: i32,
}

impl MyRange {
    fn new(start: i32, end_: i32) -> Self {
        MyRange {
            current: start,
            end_,
        }
    }
}

impl Iterator for MyRange {
    type Item = i32;
    fn next(&mut self) -> Option<Self::Item> {
        if self.current >= self.end_ {
            None
        } else {
            let val = self.current;
            self.current += 1;
            Some(val)
        }
    }
}

// Approach 2: Fibonacci iterator
struct Fibonacci {
    a: u64,
    b: u64,
}

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

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 iterator
    }
}

// Approach 3: Use free methods from implementing next()
fn demo_free_methods() -> Vec<i32> {
    MyRange::new(0, 10)
        .filter(|x| x % 2 == 0)
        .map(|x| x * x)
        .collect()
}

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

    #[test]
    fn test_range() {
        let v: Vec<i32> = MyRange::new(0, 5).collect();
        assert_eq!(v, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn test_empty_range() {
        let v: Vec<i32> = MyRange::new(5, 5).collect();
        assert!(v.is_empty());
    }

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

    #[test]
    fn test_free_methods() {
        assert_eq!(demo_free_methods(), vec![0, 4, 16, 36, 64]);
    }

    #[test]
    fn test_sum() {
        assert_eq!(MyRange::new(1, 6).sum::<i32>(), 15);
    }

    #[test]
    fn test_filter_map() {
        let v: Vec<i32> = MyRange::new(1, 4).map(|x| x * 2).collect();
        assert_eq!(v, vec![2, 4, 6]);
    }
}

(* 085: Iterator — implementing Seq from scratch *)

(* Approach 1: Simple sequence type *)
type 'a my_seq = unit -> 'a my_node
and 'a my_node = Nil | Cons of 'a * 'a my_seq

let empty () = Nil

let rec range_seq a b () =
  if a >= b then Nil
  else Cons (a, range_seq (a + 1) b)

(* Approach 2: Sequence operations *)
let rec seq_map f s () =
  match s () with
  | Nil -> Nil
  | Cons (x, rest) -> Cons (f x, seq_map f rest)

let rec seq_filter p s () =
  match s () with
  | Nil -> Nil
  | Cons (x, rest) ->
    if p x then Cons (x, seq_filter p rest)
    else seq_filter p rest ()

let seq_fold f init s =
  let rec aux acc s =
    match s () with
    | Nil -> acc
    | Cons (x, rest) -> aux (f acc x) rest
  in
  aux init s

let seq_to_list s =
  let rec aux acc s =
    match s () with
    | Nil -> List.rev acc
    | Cons (x, rest) -> aux (x :: acc) rest
  in
  aux [] s

(* Approach 3: Take and collect *)
let rec seq_take n s () =
  if n <= 0 then Nil
  else match s () with
    | Nil -> Nil
    | Cons (x, rest) -> Cons (x, seq_take (n - 1) rest)

(* Tests *)
let () =
  let r = range_seq 0 5 in
  assert (seq_to_list r = [0; 1; 2; 3; 4]);
  let doubled = seq_map (fun x -> x * 2) (range_seq 1 4) in
  assert (seq_to_list doubled = [2; 4; 6]);
  let evens = seq_filter (fun x -> x mod 2 = 0) (range_seq 0 10) in
  assert (seq_to_list evens = [0; 2; 4; 6; 8]);
  let sum = seq_fold ( + ) 0 (range_seq 1 6) in
  assert (sum = 15);
  let first3 = seq_take 3 (range_seq 0 100) in
  assert (seq_to_list first3 = [0; 1; 2]);
  Printf.printf "✓ All tests passed\n"

Key Differences

Aspect	Rust	OCaml
Interface	`trait Iterator { fn next(&mut self) -> Option<Item> }`	`type 'a t = unit -> 'a node`
Infinite sequences	`Fibonacci` with no termination	`Seq` with thunks
Bounding	`.take(n)`	`seq_take n`
Adapters	Free from trait (`map`, `filter`, etc.)	Explicit `seq_map`, `seq_filter`
Mutability	`&mut self` (mutable state)	Thunks (immutable, creates new seq)
Collection	`.collect::<Vec<_>>()`	`seq_fold` or `List.of_seq`

Implementing Iterator is one of Rust's most powerful patterns: a single method unlocks dozens of combinators. Any data source — database cursor, file reader, tree traversal — becomes a first-class iterator with zero overhead.

OCaml Approach

OCaml's Seq type represents lazy sequences: type 'a my_seq = unit -> 'a my_node with Nil | Cons of 'a * 'a my_seq. range_seq a b is a thunk that produces the next element on demand. seq_map, seq_filter, and seq_fold mirror Rust's adapters. The key difference: OCaml sequences are lazy by default (thunks), while Rust's iterators are lazy by protocol (pull-based next). Both achieve the same deferred evaluation.

Full Source

#![allow(clippy::all)]
// 085: Iterator Trait — implement from scratch

// Approach 1: Range iterator
struct MyRange {
    current: i32,
    end_: i32,
}

impl MyRange {
    fn new(start: i32, end_: i32) -> Self {
        MyRange {
            current: start,
            end_,
        }
    }
}

impl Iterator for MyRange {
    type Item = i32;
    fn next(&mut self) -> Option<Self::Item> {
        if self.current >= self.end_ {
            None
        } else {
            let val = self.current;
            self.current += 1;
            Some(val)
        }
    }
}

// Approach 2: Fibonacci iterator
struct Fibonacci {
    a: u64,
    b: u64,
}

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

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 iterator
    }
}

// Approach 3: Use free methods from implementing next()
fn demo_free_methods() -> Vec<i32> {
    MyRange::new(0, 10)
        .filter(|x| x % 2 == 0)
        .map(|x| x * x)
        .collect()
}

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

    #[test]
    fn test_range() {
        let v: Vec<i32> = MyRange::new(0, 5).collect();
        assert_eq!(v, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn test_empty_range() {
        let v: Vec<i32> = MyRange::new(5, 5).collect();
        assert!(v.is_empty());
    }

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

    #[test]
    fn test_free_methods() {
        assert_eq!(demo_free_methods(), vec![0, 4, 16, 36, 64]);
    }

    #[test]
    fn test_sum() {
        assert_eq!(MyRange::new(1, 6).sum::<i32>(), 15);
    }

    #[test]
    fn test_filter_map() {
        let v: Vec<i32> = MyRange::new(1, 4).map(|x| x * 2).collect();
        assert_eq!(v, vec![2, 4, 6]);
    }
}

(* 085: Iterator — implementing Seq from scratch *)

(* Approach 1: Simple sequence type *)
type 'a my_seq = unit -> 'a my_node
and 'a my_node = Nil | Cons of 'a * 'a my_seq

let empty () = Nil

let rec range_seq a b () =
  if a >= b then Nil
  else Cons (a, range_seq (a + 1) b)

(* Approach 2: Sequence operations *)
let rec seq_map f s () =
  match s () with
  | Nil -> Nil
  | Cons (x, rest) -> Cons (f x, seq_map f rest)

let rec seq_filter p s () =
  match s () with
  | Nil -> Nil
  | Cons (x, rest) ->
    if p x then Cons (x, seq_filter p rest)
    else seq_filter p rest ()

let seq_fold f init s =
  let rec aux acc s =
    match s () with
    | Nil -> acc
    | Cons (x, rest) -> aux (f acc x) rest
  in
  aux init s

let seq_to_list s =
  let rec aux acc s =
    match s () with
    | Nil -> List.rev acc
    | Cons (x, rest) -> aux (x :: acc) rest
  in
  aux [] s

(* Approach 3: Take and collect *)
let rec seq_take n s () =
  if n <= 0 then Nil
  else match s () with
    | Nil -> Nil
    | Cons (x, rest) -> Cons (x, seq_take (n - 1) rest)

(* Tests *)
let () =
  let r = range_seq 0 5 in
  assert (seq_to_list r = [0; 1; 2; 3; 4]);
  let doubled = seq_map (fun x -> x * 2) (range_seq 1 4) in
  assert (seq_to_list doubled = [2; 4; 6]);
  let evens = seq_filter (fun x -> x mod 2 = 0) (range_seq 0 10) in
  assert (seq_to_list evens = [0; 2; 4; 6; 8]);
  let sum = seq_fold ( + ) 0 (range_seq 1 6) in
  assert (sum = 15);
  let first3 = seq_take 3 (range_seq 0 100) in
  assert (seq_to_list first3 = [0; 1; 2]);
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_range() {
        let v: Vec<i32> = MyRange::new(0, 5).collect();
        assert_eq!(v, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn test_empty_range() {
        let v: Vec<i32> = MyRange::new(5, 5).collect();
        assert!(v.is_empty());
    }

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

    #[test]
    fn test_free_methods() {
        assert_eq!(demo_free_methods(), vec![0, 4, 16, 36, 64]);
    }

    #[test]
    fn test_sum() {
        assert_eq!(MyRange::new(1, 6).sum::<i32>(), 15);
    }

    #[test]
    fn test_filter_map() {
        let v: Vec<i32> = MyRange::new(1, 4).map(|x| x * 2).collect();
        assert_eq!(v, vec![2, 4, 6]);
    }
}

Deep Comparison

Core Insight

The Iterator trait is Rust's most powerful abstraction. Implement next() -> Option<Item> and get 70+ methods for free. OCaml uses Seq (lazy sequences) for similar functionality.

OCaml Approach

• Seq.t type: unit -> Seq.node where node = Nil | Cons of 'a * 'a Seq.t

• Lazy by construction

• Manual implementation via closures

Rust Approach

• trait Iterator { type Item; fn next(&mut self) -> Option<Self::Item>; }

• All adapter methods provided by default

• Lazy — nothing computed until consumed

Comparison Table

Feature	OCaml	Rust
Core	`unit -> node`	`fn next() -> Option<Item>`
Lazy	Yes (thunk)	Yes (pull-based)
Free methods	Few	70+ (map, filter, fold...)
State	Closure captures	`&mut self`

Exercises

Implement a Cycle<I: Iterator + Clone> iterator that wraps another iterator and repeats it infinitely.

Add a step_by field to MyRange and implement stepping (e.g. every 3rd element) in next.

Implement DoubleEndedIterator for MyRange by adding next_back(&mut self) -> Option<i32>.

Write a ZipIter<A: Iterator, B: Iterator> that zips two iterators into pairs without using std::iter::Zip.

In OCaml, implement an infinite sequence of prime numbers using the Seq module and the sieve of Eratosthenes.

Open Source Repos

functional-rust

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

Rust