880 Intermediate

880-custom-iterator — Custom Iterator

Functional Programming

Tutorial

The Problem

Standard ranges and slice iterators cover most use cases, but real programs require custom sequences: Fibonacci numbers, arithmetic progressions with arbitrary step sizes, geometric sequences, or domain-specific data streams. Implementing the Iterator trait for a custom struct allows these sequences to integrate fully with Rust's iterator ecosystem — all adapter methods (map, filter, take, chain) work automatically. This example shows two custom iterators: a stateful Fibonacci generator and a generic step range, both demonstrating how minimal trait implementation unlocks a rich API.

🎯 Learning Outcomes

• Implement stateful iterators using struct fields to track position

• Build an infinite iterator (Fibonacci) that always returns Some

• Build a finite iterator (StepRange) that returns None when exhausted

• Use custom iterators with standard adapter methods like .take() and .filter()

• Compare with OCaml's Seq.unfold for generating custom sequences

Code Example

struct Fibonacci { a: u64, b: u64 }

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

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

let fibonacci () =
  let rec aux a b () =
    Seq.Cons (a, aux b (a + b))
  in
  aux 0 1

let first10 = seq_take 10 (fibonacci ())

Key Differences

Mutable state: Rust iterators carry mutable state in the struct, modified by next(&mut self); OCaml Seq.unfold threads state functionally.

Infinite sequences: Both support infinite sequences; Rust via always-Some, OCaml via Seq.unfold with Some always.

Integration: Both integrate fully with their respective ecosystem (adapter chains in Rust, Seq.map/Seq.filter in OCaml).

Reusability: Rust iterators are consumed once (stateful); OCaml Seq values can be traversed multiple times (immutable).

OCaml Approach

OCaml generates custom sequences with Seq.unfold: ('a -> ('b * 'a) option) -> 'a -> 'b Seq.t. The seed state is passed functionally; each step returns Some(value, next_state) or None. Fibonacci: Seq.unfold (fun (a, b) -> Some(a, (b, a+b))) (0, 1). Step range: Seq.unfold (fun i -> if i > n then None else Some(i, i + step)) start. The functional style avoids mutable struct fields; Rust uses mutable struct state within the Iterator implementation.

Full Source

#![allow(clippy::all)]
// Example 086: Custom Iterator — Fibonacci and Range with Step

// === Approach 1: 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<u64> {
        let val = self.a;
        let next = self.a + self.b;
        self.a = self.b;
        self.b = next;
        Some(val)
    }
}

// === Approach 2: Range with step ===
struct StepRange<T> {
    current: T,
    end_: T,
    step: T,
}

impl StepRange<i64> {
    fn new(start: i64, end_: i64, step: i64) -> Self {
        StepRange {
            current: start,
            end_,
            step,
        }
    }
}

impl Iterator for StepRange<i64> {
    type Item = i64;

    fn next(&mut self) -> Option<i64> {
        if self.current >= self.end_ {
            None
        } else {
            let val = self.current;
            self.current += self.step;
            Some(val)
        }
    }
}

impl StepRange<f64> {
    fn new_float(start: f64, end_: f64, step: f64) -> Self {
        StepRange {
            current: start,
            end_,
            step,
        }
    }
}

impl Iterator for StepRange<f64> {
    type Item = f64;

    fn next(&mut self) -> Option<f64> {
        if self.current >= self.end_ {
            None
        } else {
            let val = self.current;
            self.current += self.step;
            Some(val)
        }
    }
}

// === Approach 3: Collatz sequence iterator ===
struct Collatz {
    current: u64,
    done_: bool,
}

impl Collatz {
    fn new(n: u64) -> Self {
        Collatz {
            current: n,
            done_: false,
        }
    }
}

impl Iterator for Collatz {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        if self.done_ {
            return None;
        }
        let val = self.current;
        if val == 1 {
            self.done_ = true;
        } else if val % 2 == 0 {
            self.current = val / 2;
        } else {
            self.current = 3 * val + 1;
        }
        Some(val)
    }
}

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

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

    #[test]
    fn test_fibonacci_sum() {
        let sum: u64 = Fibonacci::new().take(10).sum();
        assert_eq!(sum, 88);
    }

    #[test]
    fn test_step_range() {
        let v: Vec<i64> = StepRange::new(0, 10, 2).collect();
        assert_eq!(v, vec![0, 2, 4, 6, 8]);
    }

    #[test]
    fn test_step_range_by3() {
        let v: Vec<i64> = StepRange::new(0, 10, 3).collect();
        assert_eq!(v, vec![0, 3, 6, 9]);
    }

    #[test]
    fn test_step_range_float() {
        let v: Vec<f64> = StepRange::new_float(0.0, 1.0, 0.25).collect();
        assert_eq!(v.len(), 4);
        assert!((v[0] - 0.0).abs() < 1e-10);
        assert!((v[3] - 0.75).abs() < 1e-10);
    }

    #[test]
    fn test_collatz_6() {
        let v: Vec<u64> = Collatz::new(6).collect();
        assert_eq!(v, vec![6, 3, 10, 5, 16, 8, 4, 2, 1]);
    }

    #[test]
    fn test_collatz_1() {
        let v: Vec<u64> = Collatz::new(1).collect();
        assert_eq!(v, vec![1]);
    }

    #[test]
    fn test_collatz_length() {
        let len = Collatz::new(27).count();
        assert_eq!(len, 112);
    }

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

(* Example 086: Custom Iterator — Fibonacci and Range with Step *)

(* Approach 1: Fibonacci via Seq *)
let fibonacci () =
  let rec aux a b () =
    Seq.Cons (a, aux b (a + b))
  in
  aux 0 1

let seq_take n seq =
  let rec aux n seq acc =
    if n = 0 then List.rev acc
    else match seq () with
    | Seq.Nil -> List.rev acc
    | Seq.Cons (x, rest) -> aux (n - 1) rest (x :: acc)
  in
  aux n seq []

(* Approach 2: Range with step *)
type 'a step_range = {
  mutable current : 'a;
  stop : 'a;
  step : 'a;
  add : 'a -> 'a -> 'a;
  compare : 'a -> 'a -> int;
}

let step_range_next sr =
  if sr.compare sr.current sr.stop >= 0 then None
  else begin
    let v = sr.current in
    sr.current <- sr.add sr.current sr.step;
    Some v
  end

let int_step_range start stop step =
  { current = start; stop; step; add = (+); compare }

let float_step_range start stop step =
  { current = start; stop; step; add = (+.); compare = Float.compare }

let step_range_to_list sr =
  let rec aux acc =
    match step_range_next sr with
    | None -> List.rev acc
    | Some v -> aux (v :: acc)
  in
  aux []

(* Approach 3: Collatz sequence *)
let collatz n =
  let current = ref n in
  let done_ = ref false in
  fun () ->
    if !done_ then Seq.Nil
    else begin
      let v = !current in
      if v = 1 then (done_ := true; Seq.Cons (v, fun () -> Seq.Nil))
      else begin
        current := if v mod 2 = 0 then v / 2 else 3 * v + 1;
        Seq.Cons (v, fun () -> Seq.Nil) (* simplified *)
      end
    end

let collatz_list n =
  let rec aux v acc =
    if v = 1 then List.rev (1 :: acc)
    else aux (if v mod 2 = 0 then v / 2 else 3 * v + 1) (v :: acc)
  in
  aux n []

(* Tests *)
let () =
  let fibs = seq_take 10 (fibonacci ()) in
  assert (fibs = [0; 1; 1; 2; 3; 5; 8; 13; 21; 34]);

  let r = int_step_range 0 10 2 in
  assert (step_range_to_list r = [0; 2; 4; 6; 8]);

  let r2 = int_step_range 0 10 3 in
  assert (step_range_to_list r2 = [0; 3; 6; 9]);

  let r3 = float_step_range 0.0 1.0 0.25 in
  let result = step_range_to_list r3 in
  assert (List.length result = 4);

  let c = collatz_list 6 in
  assert (c = [6; 3; 10; 5; 16; 8; 4; 2; 1]);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

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

    #[test]
    fn test_fibonacci_sum() {
        let sum: u64 = Fibonacci::new().take(10).sum();
        assert_eq!(sum, 88);
    }

    #[test]
    fn test_step_range() {
        let v: Vec<i64> = StepRange::new(0, 10, 2).collect();
        assert_eq!(v, vec![0, 2, 4, 6, 8]);
    }

    #[test]
    fn test_step_range_by3() {
        let v: Vec<i64> = StepRange::new(0, 10, 3).collect();
        assert_eq!(v, vec![0, 3, 6, 9]);
    }

    #[test]
    fn test_step_range_float() {
        let v: Vec<f64> = StepRange::new_float(0.0, 1.0, 0.25).collect();
        assert_eq!(v.len(), 4);
        assert!((v[0] - 0.0).abs() < 1e-10);
        assert!((v[3] - 0.75).abs() < 1e-10);
    }

    #[test]
    fn test_collatz_6() {
        let v: Vec<u64> = Collatz::new(6).collect();
        assert_eq!(v, vec![6, 3, 10, 5, 16, 8, 4, 2, 1]);
    }

    #[test]
    fn test_collatz_1() {
        let v: Vec<u64> = Collatz::new(1).collect();
        assert_eq!(v, vec![1]);
    }

    #[test]
    fn test_collatz_length() {
        let len = Collatz::new(27).count();
        assert_eq!(len, 112);
    }

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

Deep Comparison

Comparison: Custom Iterator

Fibonacci

OCaml:

let fibonacci () =
  let rec aux a b () =
    Seq.Cons (a, aux b (a + b))
  in
  aux 0 1

let first10 = seq_take 10 (fibonacci ())

Rust:

struct Fibonacci { a: u64, b: u64 }

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

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

Range with Step

OCaml:

let int_step_range start stop step =
  { current = start; stop; step; add = (+); compare }

Rust:

struct StepRange<T> { current: T, end_: T, step: T }

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

Collatz Sequence

OCaml:

let collatz_list n =
  let rec aux v acc =
    if v = 1 then List.rev (1 :: acc)
    else aux (if v mod 2 = 0 then v / 2 else 3 * v + 1) (v :: acc)
  in aux n []

Rust:

struct Collatz { current: u64, done_: bool }

impl Iterator for Collatz {
    type Item = u64;
    fn next(&mut self) -> Option<u64> {
        if self.done_ { return None; }
        let val = self.current;
        if val == 1 { self.done_ = true; }
        else if val % 2 == 0 { self.current = val / 2; }
        else { self.current = 3 * val + 1; }
        Some(val)
    }
}

Exercises

Implement a Collatz iterator that generates the Collatz sequence starting from a given number until it reaches 1.

Implement a Geometric<T> iterator (geometric sequence: a, ar, ar², ...) that stops when the value exceeds a given limit.

Add DoubleEndedIterator to StepRange<i64> so it can iterate from either end and support .rev().

Open Source Repos

functional-rust

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

Rust