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

//! 085: Iterator Trait — implementing `Iterator` from scratch.
//!
//! The OCaml original defines a custom `my_seq` type (a thunk returning
//! `Nil | Cons(x, rest)`) along with hand-written `seq_map`, `seq_filter`,
//! `seq_fold`, `seq_take`, and `seq_to_list` operations.
//!
//! In Rust, the standard library already provides this exact abstraction as
//! the [`Iterator`] trait. You implement a single method — [`Iterator::next`]
//! — and you automatically receive `map`, `filter`, `fold`, `take`, `collect`,
//! and dozens more combinators. This module therefore:
//!
//! 1. Implements a custom [`RangeIter`] to show how little code is needed to
//!    plug into the iterator ecosystem.
//! 2. Provides [`MySeq`], a direct structural translation of OCaml's
//!    `Nil | Cons` algebraic data type, with a borrowing iterator.
//! 3. Demonstrates that once the trait is implemented, the library's built-in
//!    combinators replace all the hand-written `seq_*` helpers.

/// Half-open integer range iterator: yields `start, start+1, …, end-1`.
///
/// Mirrors OCaml's `range_seq a b`. Implementing [`Iterator::next`] is enough
/// to make every standard combinator (`map`, `filter`, `fold`, `take`, …)
/// available on values of this type.
#[derive(Debug, Clone)]
pub struct RangeIter {
    current: i64,
    end: i64,
}

impl RangeIter {
    /// Build a new half-open range `[start, end)`.
    ///
    /// If `start >= end`, the iterator is empty.
    pub fn new(start: i64, end: i64) -> Self {
        Self {
            current: start,
            end,
        }
    }
}

impl Iterator for RangeIter {
    type Item = i64;

    fn next(&mut self) -> Option<Self::Item> {
        if self.current >= self.end {
            None
        } else {
            let value = self.current;
            self.current += 1;
            Some(value)
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining = (self.end - self.current).max(0) as usize;
        (remaining, Some(remaining))
    }
}

impl ExactSizeIterator for RangeIter {}

/// Direct translation of OCaml's `'a my_node = Nil | Cons of 'a * 'a my_seq`.
///
/// Because Rust does not allow infinite-size types, the recursive `Cons` arm
/// holds a `Box<MySeq<T>>` rather than a bare `MySeq<T>`. This is the same
/// indirection OCaml performs implicitly through its uniform value
/// representation.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum MySeq<T> {
    /// End of the sequence.
    Nil,
    /// A value followed by the rest of the sequence.
    Cons(T, Box<MySeq<T>>),
}

impl MySeq<i64> {
    /// Build a `MySeq` containing the integers in `[start, end)`.
    ///
    /// Equivalent to OCaml's `range_seq`, but eager rather than lazy.
    pub fn range(start: i64, end: i64) -> MySeq<i64> {
        let mut node = MySeq::Nil;
        let mut i = end;
        while i > start {
            i -= 1;
            node = MySeq::Cons(i, Box::new(node));
        }
        node
    }
}

impl<T> MySeq<T> {
    /// Borrowing iterator that walks a `MySeq` and yields `&T` values.
    pub fn iter(&self) -> MySeqIter<'_, T> {
        MySeqIter { node: self }
    }
}

/// Borrowing iterator over a [`MySeq`].
///
/// Produced by [`MySeq::iter`]. Implements [`Iterator`] so the standard
/// combinators (`map`, `filter`, `fold`, `take`, `collect`, …) replace the
/// hand-written `seq_*` helpers from the OCaml version.
pub struct MySeqIter<'a, T> {
    node: &'a MySeq<T>,
}

impl<'a, T> Iterator for MySeqIter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        match self.node {
            MySeq::Nil => None,
            MySeq::Cons(value, rest) => {
                self.node = rest;
                Some(value)
            }
        }
    }
}

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

    #[test]
    fn range_iter_collects_to_list() {
        let result: Vec<i64> = RangeIter::new(0, 5).collect();
        assert_eq!(result, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn range_iter_empty_when_start_not_less_than_end() {
        let result: Vec<i64> = RangeIter::new(5, 5).collect();
        assert!(result.is_empty());
        let result: Vec<i64> = RangeIter::new(7, 3).collect();
        assert!(result.is_empty());
    }

    #[test]
    fn range_iter_size_hint_is_exact() {
        let iter = RangeIter::new(0, 10);
        assert_eq!(iter.size_hint(), (10, Some(10)));
        assert_eq!(iter.len(), 10);
    }

    #[test]
    fn map_doubles_every_element() {
        let doubled: Vec<i64> = RangeIter::new(1, 4).map(|x| x * 2).collect();
        assert_eq!(doubled, vec![2, 4, 6]);
    }

    #[test]
    fn filter_keeps_even_numbers() {
        let evens: Vec<i64> = RangeIter::new(0, 10).filter(|x| x % 2 == 0).collect();
        assert_eq!(evens, vec![0, 2, 4, 6, 8]);
    }

    #[test]
    fn fold_builds_a_custom_accumulator() {
        // fold is the general form of sum/product — OCaml's `seq_fold`.
        let reversed: Vec<i64> = RangeIter::new(1, 6).fold(Vec::new(), |mut acc, x| {
            acc.insert(0, x);
            acc
        });
        assert_eq!(reversed, vec![5, 4, 3, 2, 1]);
        let sum: i64 = RangeIter::new(1, 6).sum();
        assert_eq!(sum, 15);
    }

    #[test]
    fn take_limits_output_to_first_n() {
        let first3: Vec<i64> = RangeIter::new(0, 100).take(3).collect();
        assert_eq!(first3, vec![0, 1, 2]);
    }

    #[test]
    fn combinators_compose() {
        let result: Vec<i64> = RangeIter::new(0, 20)
            .filter(|x| x % 2 == 0)
            .map(|x| x * x)
            .take(4)
            .collect();
        assert_eq!(result, vec![0, 4, 16, 36]);
    }

    #[test]
    fn my_seq_range_mirrors_ocaml() {
        let s = MySeq::range(0, 3);
        let collected: Vec<i64> = s.iter().copied().collect();
        assert_eq!(collected, vec![0, 1, 2]);
    }

    #[test]
    fn my_seq_empty_when_range_inverted() {
        let s = MySeq::range(4, 4);
        assert_eq!(s, MySeq::Nil);
    }

    #[test]
    fn my_seq_iter_supports_standard_combinators() {
        let s = MySeq::range(0, 10);
        let sum_of_squares: i64 = s
            .iter()
            .copied()
            .filter(|x| x % 2 == 1)
            .map(|x| x * x)
            .sum();
        assert_eq!(sum_of_squares, 1 + 9 + 25 + 49 + 81);
    }
}

(* 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

//! 085: Iterator Trait — implementing `Iterator` from scratch.
//!
//! The OCaml original defines a custom `my_seq` type (a thunk returning
//! `Nil | Cons(x, rest)`) along with hand-written `seq_map`, `seq_filter`,
//! `seq_fold`, `seq_take`, and `seq_to_list` operations.
//!
//! In Rust, the standard library already provides this exact abstraction as
//! the [`Iterator`] trait. You implement a single method — [`Iterator::next`]
//! — and you automatically receive `map`, `filter`, `fold`, `take`, `collect`,
//! and dozens more combinators. This module therefore:
//!
//! 1. Implements a custom [`RangeIter`] to show how little code is needed to
//!    plug into the iterator ecosystem.
//! 2. Provides [`MySeq`], a direct structural translation of OCaml's
//!    `Nil | Cons` algebraic data type, with a borrowing iterator.
//! 3. Demonstrates that once the trait is implemented, the library's built-in
//!    combinators replace all the hand-written `seq_*` helpers.

/// Half-open integer range iterator: yields `start, start+1, …, end-1`.
///
/// Mirrors OCaml's `range_seq a b`. Implementing [`Iterator::next`] is enough
/// to make every standard combinator (`map`, `filter`, `fold`, `take`, …)
/// available on values of this type.
#[derive(Debug, Clone)]
pub struct RangeIter {
    current: i64,
    end: i64,
}

impl RangeIter {
    /// Build a new half-open range `[start, end)`.
    ///
    /// If `start >= end`, the iterator is empty.
    pub fn new(start: i64, end: i64) -> Self {
        Self {
            current: start,
            end,
        }
    }
}

impl Iterator for RangeIter {
    type Item = i64;

    fn next(&mut self) -> Option<Self::Item> {
        if self.current >= self.end {
            None
        } else {
            let value = self.current;
            self.current += 1;
            Some(value)
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining = (self.end - self.current).max(0) as usize;
        (remaining, Some(remaining))
    }
}

impl ExactSizeIterator for RangeIter {}

/// Direct translation of OCaml's `'a my_node = Nil | Cons of 'a * 'a my_seq`.
///
/// Because Rust does not allow infinite-size types, the recursive `Cons` arm
/// holds a `Box<MySeq<T>>` rather than a bare `MySeq<T>`. This is the same
/// indirection OCaml performs implicitly through its uniform value
/// representation.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum MySeq<T> {
    /// End of the sequence.
    Nil,
    /// A value followed by the rest of the sequence.
    Cons(T, Box<MySeq<T>>),
}

impl MySeq<i64> {
    /// Build a `MySeq` containing the integers in `[start, end)`.
    ///
    /// Equivalent to OCaml's `range_seq`, but eager rather than lazy.
    pub fn range(start: i64, end: i64) -> MySeq<i64> {
        let mut node = MySeq::Nil;
        let mut i = end;
        while i > start {
            i -= 1;
            node = MySeq::Cons(i, Box::new(node));
        }
        node
    }
}

impl<T> MySeq<T> {
    /// Borrowing iterator that walks a `MySeq` and yields `&T` values.
    pub fn iter(&self) -> MySeqIter<'_, T> {
        MySeqIter { node: self }
    }
}

/// Borrowing iterator over a [`MySeq`].
///
/// Produced by [`MySeq::iter`]. Implements [`Iterator`] so the standard
/// combinators (`map`, `filter`, `fold`, `take`, `collect`, …) replace the
/// hand-written `seq_*` helpers from the OCaml version.
pub struct MySeqIter<'a, T> {
    node: &'a MySeq<T>,
}

impl<'a, T> Iterator for MySeqIter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        match self.node {
            MySeq::Nil => None,
            MySeq::Cons(value, rest) => {
                self.node = rest;
                Some(value)
            }
        }
    }
}

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

    #[test]
    fn range_iter_collects_to_list() {
        let result: Vec<i64> = RangeIter::new(0, 5).collect();
        assert_eq!(result, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn range_iter_empty_when_start_not_less_than_end() {
        let result: Vec<i64> = RangeIter::new(5, 5).collect();
        assert!(result.is_empty());
        let result: Vec<i64> = RangeIter::new(7, 3).collect();
        assert!(result.is_empty());
    }

    #[test]
    fn range_iter_size_hint_is_exact() {
        let iter = RangeIter::new(0, 10);
        assert_eq!(iter.size_hint(), (10, Some(10)));
        assert_eq!(iter.len(), 10);
    }

    #[test]
    fn map_doubles_every_element() {
        let doubled: Vec<i64> = RangeIter::new(1, 4).map(|x| x * 2).collect();
        assert_eq!(doubled, vec![2, 4, 6]);
    }

    #[test]
    fn filter_keeps_even_numbers() {
        let evens: Vec<i64> = RangeIter::new(0, 10).filter(|x| x % 2 == 0).collect();
        assert_eq!(evens, vec![0, 2, 4, 6, 8]);
    }

    #[test]
    fn fold_builds_a_custom_accumulator() {
        // fold is the general form of sum/product — OCaml's `seq_fold`.
        let reversed: Vec<i64> = RangeIter::new(1, 6).fold(Vec::new(), |mut acc, x| {
            acc.insert(0, x);
            acc
        });
        assert_eq!(reversed, vec![5, 4, 3, 2, 1]);
        let sum: i64 = RangeIter::new(1, 6).sum();
        assert_eq!(sum, 15);
    }

    #[test]
    fn take_limits_output_to_first_n() {
        let first3: Vec<i64> = RangeIter::new(0, 100).take(3).collect();
        assert_eq!(first3, vec![0, 1, 2]);
    }

    #[test]
    fn combinators_compose() {
        let result: Vec<i64> = RangeIter::new(0, 20)
            .filter(|x| x % 2 == 0)
            .map(|x| x * x)
            .take(4)
            .collect();
        assert_eq!(result, vec![0, 4, 16, 36]);
    }

    #[test]
    fn my_seq_range_mirrors_ocaml() {
        let s = MySeq::range(0, 3);
        let collected: Vec<i64> = s.iter().copied().collect();
        assert_eq!(collected, vec![0, 1, 2]);
    }

    #[test]
    fn my_seq_empty_when_range_inverted() {
        let s = MySeq::range(4, 4);
        assert_eq!(s, MySeq::Nil);
    }

    #[test]
    fn my_seq_iter_supports_standard_combinators() {
        let s = MySeq::range(0, 10);
        let sum_of_squares: i64 = s
            .iter()
            .copied()
            .filter(|x| x % 2 == 1)
            .map(|x| x * x)
            .sum();
        assert_eq!(sum_of_squares, 1 + 9 + 25 + 49 + 81);
    }
}

(* 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 range_iter_collects_to_list() {
        let result: Vec<i64> = RangeIter::new(0, 5).collect();
        assert_eq!(result, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn range_iter_empty_when_start_not_less_than_end() {
        let result: Vec<i64> = RangeIter::new(5, 5).collect();
        assert!(result.is_empty());
        let result: Vec<i64> = RangeIter::new(7, 3).collect();
        assert!(result.is_empty());
    }

    #[test]
    fn range_iter_size_hint_is_exact() {
        let iter = RangeIter::new(0, 10);
        assert_eq!(iter.size_hint(), (10, Some(10)));
        assert_eq!(iter.len(), 10);
    }

    #[test]
    fn map_doubles_every_element() {
        let doubled: Vec<i64> = RangeIter::new(1, 4).map(|x| x * 2).collect();
        assert_eq!(doubled, vec![2, 4, 6]);
    }

    #[test]
    fn filter_keeps_even_numbers() {
        let evens: Vec<i64> = RangeIter::new(0, 10).filter(|x| x % 2 == 0).collect();
        assert_eq!(evens, vec![0, 2, 4, 6, 8]);
    }

    #[test]
    fn fold_builds_a_custom_accumulator() {
        // fold is the general form of sum/product — OCaml's `seq_fold`.
        let reversed: Vec<i64> = RangeIter::new(1, 6).fold(Vec::new(), |mut acc, x| {
            acc.insert(0, x);
            acc
        });
        assert_eq!(reversed, vec![5, 4, 3, 2, 1]);
        let sum: i64 = RangeIter::new(1, 6).sum();
        assert_eq!(sum, 15);
    }

    #[test]
    fn take_limits_output_to_first_n() {
        let first3: Vec<i64> = RangeIter::new(0, 100).take(3).collect();
        assert_eq!(first3, vec![0, 1, 2]);
    }

    #[test]
    fn combinators_compose() {
        let result: Vec<i64> = RangeIter::new(0, 20)
            .filter(|x| x % 2 == 0)
            .map(|x| x * x)
            .take(4)
            .collect();
        assert_eq!(result, vec![0, 4, 16, 36]);
    }

    #[test]
    fn my_seq_range_mirrors_ocaml() {
        let s = MySeq::range(0, 3);
        let collected: Vec<i64> = s.iter().copied().collect();
        assert_eq!(collected, vec![0, 1, 2]);
    }

    #[test]
    fn my_seq_empty_when_range_inverted() {
        let s = MySeq::range(4, 4);
        assert_eq!(s, MySeq::Nil);
    }

    #[test]
    fn my_seq_iter_supports_standard_combinators() {
        let s = MySeq::range(0, 10);
        let sum_of_squares: i64 = s
            .iter()
            .copied()
            .filter(|x| x % 2 == 1)
            .map(|x| x * x)
            .sum();
        assert_eq!(sum_of_squares, 1 + 9 + 25 + 49 + 81);
    }
}

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