879 Intermediate

879-iterator-trait — Iterator Trait

Functional Programming

Tutorial

The Problem

Iteration is fundamental to every program. Languages handle it differently: C uses index-based loops, Java uses Iterable/Iterator interfaces, Python uses __iter__/__next__. Rust's Iterator trait requires only one method — fn next(&mut self) -> Option<Self::Item> — and provides over 70 adapter and consumer methods for free. This design unifies all iteration patterns: ranges, collections, generators, and lazy sequences all implement the same interface. OCaml's Seq module serves a similar role for lazy sequences, and List provides eager equivalents. Understanding the Iterator trait is essential for idiomatic Rust.

🎯 Learning Outcomes

• Implement the Iterator trait with only the next method

• Understand that all other iterator methods are provided automatically via default implementations

• Build both finite and infinite custom iterators

• Implement IntoIterator to make custom types work in for loops

• Compare Rust's Iterator with OCaml's Seq lazy sequence abstraction

Code Example

struct Range { current: i32, end_: i32 }

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

let range start stop =
  let rec aux n () =
    if n >= stop then Seq.Nil
    else Seq.Cons (n, aux (n + 1))
  in
  aux start

Key Differences

Method vs function: Rust iterator methods are called on the value (iter.map(f)); OCaml uses module-level functions (Seq.map f seq).

Infinite sequences: Both support infinite iterators; Rust via Option::Some always, OCaml via Seq.Cons always.

Laziness: Rust iterators are lazy by default (adapters don't evaluate until consumed); OCaml Seq is explicitly lazy via unit ->.

Mutability: Rust Iterator::next takes &mut self (mutable internal state); OCaml sequences are immutable — each step returns a new sequence.

OCaml Approach

OCaml's Seq module uses a lazy list: type 'a t = unit -> 'a node where node = Nil | Cons of 'a * 'a t. A custom sequence is a function returning the next node lazily. The Seq module provides map, filter, take, flat_map as standalone functions rather than methods. For eager iteration, OCaml uses List.iter, Array.iter, or explicit recursion. Seq.of_list and List.of_seq convert between representations.

Full Source

#![allow(clippy::all)]
// Example 085: Iterator Trait
// OCaml Seq → Rust Iterator

// === Approach 1: Implementing Iterator for a custom type ===
struct Range {
    current: i32,
    end_: i32,
}

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

impl Iterator for Range {
    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: Iterator with map/filter (free from trait) ===
struct Counter {
    current: u64,
}

impl Counter {
    fn from(start: u64) -> Self {
        Counter { current: start }
    }
}

impl Iterator for Counter {
    type Item = u64;

    fn next(&mut self) -> Option<Self::Item> {
        let val = self.current;
        self.current += 1;
        Some(val) // infinite!
    }
}

// === Approach 3: Iterator via IntoIterator ===
struct Repeat<T: Clone> {
    value: T,
    remaining: usize,
}

impl<T: Clone> Repeat<T> {
    fn new(value: T, count: usize) -> Self {
        Repeat {
            value,
            remaining: count,
        }
    }
}

impl<T: Clone> Iterator for Repeat<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.remaining == 0 {
            None
        } else {
            self.remaining -= 1;
            Some(self.value.clone())
        }
    }
}

// Generic function working with any iterator
fn sum_first_n<I: Iterator<Item = i32>>(iter: I, n: usize) -> i32 {
    iter.take(n).sum()
}

fn collect_mapped<I, F, B>(iter: I, f: F) -> Vec<B>
where
    I: Iterator,
    F: Fn(I::Item) -> B,
{
    iter.map(f).collect()
}

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

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

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

    #[test]
    fn test_range_map() {
        let v: Vec<i32> = Range::new(1, 4).map(|x| x * 10).collect();
        assert_eq!(v, vec![10, 20, 30]);
    }

    #[test]
    fn test_range_filter() {
        let v: Vec<i32> = Range::new(1, 11).filter(|x| x % 3 == 0).collect();
        assert_eq!(v, vec![3, 6, 9]);
    }

    #[test]
    fn test_counter_take() {
        let v: Vec<u64> = Counter::from(10).take(3).collect();
        assert_eq!(v, vec![10, 11, 12]);
    }

    #[test]
    fn test_counter_chain() {
        let sum: u64 = Counter::from(1).take(100).sum();
        assert_eq!(sum, 5050);
    }

    #[test]
    fn test_repeat() {
        let v: Vec<i32> = Repeat::new(42, 4).collect();
        assert_eq!(v, vec![42, 42, 42, 42]);
    }

    #[test]
    fn test_sum_first_n() {
        let sum = sum_first_n(Range::new(1, 100), 10);
        assert_eq!(sum, 55);
    }

    #[test]
    fn test_collect_mapped() {
        let v = collect_mapped(Range::new(1, 4), |x| x.to_string());
        assert_eq!(v, vec!["1", "2", "3"]);
    }
}

(* Example 085: Iterator Trait *)
(* OCaml Seq → Rust Iterator *)

(* Approach 1: Using Seq (lazy sequences) *)
let range start stop =
  let rec aux n () =
    if n >= stop then Seq.Nil
    else Seq.Cons (n, aux (n + 1))
  in
  aux start

let seq_to_list seq =
  Seq.fold_left (fun acc x -> x :: acc) [] seq |> List.rev

(* Approach 2: Custom iterator via closure *)
type 'a iterator = {
  next : unit -> 'a option;
}

let range_iter start stop =
  let current = ref start in
  { next = fun () ->
    if !current >= stop then None
    else begin
      let v = !current in
      incr current;
      Some v
    end
  }

let iter_to_list it =
  let rec aux acc =
    match it.next () with
    | None -> List.rev acc
    | Some v -> aux (v :: acc)
  in
  aux []

let iter_map f it =
  { next = fun () ->
    match it.next () with
    | None -> None
    | Some v -> Some (f v)
  }

let iter_filter pred it =
  let rec find () =
    match it.next () with
    | None -> None
    | Some v -> if pred v then Some v else find ()
  in
  { next = find }

(* Approach 3: Using List as iterator source *)
let counter_from n =
  let c = ref n in
  { next = fun () ->
    let v = !c in
    c := v + 1;
    Some v
  }

let take n it =
  let count = ref 0 in
  { next = fun () ->
    if !count >= n then None
    else begin
      incr count;
      it.next ()
    end
  }

(* Tests *)
let () =
  let s = range 1 6 in
  assert (seq_to_list s = [1; 2; 3; 4; 5]);

  let it = range_iter 1 6 in
  assert (iter_to_list it = [1; 2; 3; 4; 5]);

  let it2 = range_iter 1 11 in
  let doubled = iter_map (fun x -> x * 2) it2 in
  let evens = iter_filter (fun x -> x <= 10) doubled in
  assert (iter_to_list evens = [2; 4; 6; 8; 10]);

  let inf = counter_from 0 in
  let first5 = take 5 inf in
  assert (iter_to_list first5 = [0; 1; 2; 3; 4]);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

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

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

    #[test]
    fn test_range_map() {
        let v: Vec<i32> = Range::new(1, 4).map(|x| x * 10).collect();
        assert_eq!(v, vec![10, 20, 30]);
    }

    #[test]
    fn test_range_filter() {
        let v: Vec<i32> = Range::new(1, 11).filter(|x| x % 3 == 0).collect();
        assert_eq!(v, vec![3, 6, 9]);
    }

    #[test]
    fn test_counter_take() {
        let v: Vec<u64> = Counter::from(10).take(3).collect();
        assert_eq!(v, vec![10, 11, 12]);
    }

    #[test]
    fn test_counter_chain() {
        let sum: u64 = Counter::from(1).take(100).sum();
        assert_eq!(sum, 5050);
    }

    #[test]
    fn test_repeat() {
        let v: Vec<i32> = Repeat::new(42, 4).collect();
        assert_eq!(v, vec![42, 42, 42, 42]);
    }

    #[test]
    fn test_sum_first_n() {
        let sum = sum_first_n(Range::new(1, 100), 10);
        assert_eq!(sum, 55);
    }

    #[test]
    fn test_collect_mapped() {
        let v = collect_mapped(Range::new(1, 4), |x| x.to_string());
        assert_eq!(v, vec!["1", "2", "3"]);
    }
}

Deep Comparison

Comparison: Iterator Trait

Core Implementation

OCaml — Seq:

let range start stop =
  let rec aux n () =
    if n >= stop then Seq.Nil
    else Seq.Cons (n, aux (n + 1))
  in
  aux start

Rust — Iterator trait:

struct Range { current: i32, end_: i32 }

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

Map/Filter (Manual vs Free)

OCaml — Must implement manually for custom iterators:

let iter_map f it =
  { next = fun () -> match it.next () with
    | None -> None | Some v -> Some (f v) }

Rust — Free from Iterator trait:

// Just implementing next() gives you:
Range::new(1, 6).map(|x| x * 2).filter(|x| x > 5).collect::<Vec<_>>()

Infinite Sequences

OCaml:

let counter_from n =
  let c = ref n in
  { next = fun () -> let v = !c in c := v + 1; Some v }

let first5 = take 5 (counter_from 0)

Rust:

impl Iterator for Counter {
    type Item = u64;
    fn next(&mut self) -> Option<u64> {
        let v = self.current; self.current += 1; Some(v)
    }
}

let first5: Vec<u64> = Counter::from(0).take(5).collect();

Exercises

Implement a Primes iterator that yields prime numbers lazily using a sieve or trial division.

Implement IntoIterator for a custom Grid<T> type that yields elements in row-major order.

Implement a Zip2<A: Iterator, B: Iterator> struct that pairs elements from two iterators, stopping when either is exhausted.

Open Source Repos

functional-rust

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

Rust