884 Intermediate

884-infinite-iterators — Infinite Iterators

Functional Programming

Tutorial

The Problem

Many algorithms require generating sequences without a predetermined endpoint: cycling through a palette, repeating a default value, generating an arithmetic sequence of any length. In languages without lazy evaluation, this requires explicit loop counters and early exits. Rust provides std::iter::repeat, repeat_with, cycle, and successors as built-in infinite iterator constructors. These integrate naturally with .take(n) to produce finite results. Haskell's iterate and OCaml's Seq.unfold serve the same role. This example surveys all the standard infinite iterator patterns in Rust.

🎯 Learning Outcomes

• Use repeat, repeat_with, and cycle for constant and periodic sequences

• Use std::iter::successors to implement OCaml's iterate function

• Use from_fn with mutable state for stateful infinite generators

• Implement a generic unfold using from_fn for functional-style generation

• Recognize when infinite iterators simplify code compared to explicit loops

Code Example

std::iter::repeat(42).take(5).collect::<Vec<_>>()  // [42, 42, 42, 42, 42]

let repeat x () = Seq.Cons (x, repeat x)
seq_take 5 (repeat 42)  (* [42; 42; 42; 42; 42] *)

Key Differences

API breadth: Rust has repeat, repeat_with, cycle, successors, from_fn as distinct constructors; OCaml unifies everything under Seq.unfold.

Termination: Rust successors terminates when the closure returns None; repeat and cycle never terminate — .take(n) is required.

Stateful generators: Rust from_fn captures mutable state in a closure; OCaml threads state as the unfold seed.

Performance: Rust's repeat and cycle are zero-allocation; OCaml's Seq allocates a new closure thunk per step.

OCaml Approach

OCaml's equivalent is Seq.unfold: ('a -> ('b * 'a) option) -> 'a -> 'b Seq.t. Seq.repeat x = Seq.unfold (fun () -> Some(x, ())) (). Seq.cycle is not in standard OCaml but trivially expressible via Seq.unfold with modular index state. iterate f x = Seq.unfold (fun s -> Some(s, f s)) x. The OCaml approach is more uniform (everything is unfold) while Rust provides specialized constructors for common patterns.

Full Source

#![allow(clippy::all)]
// Example 090: Infinite Iterators
// iterate, repeat, cycle, unfold

// === Approach 1: repeat and cycle ===
fn repeat_demo() -> Vec<i32> {
    std::iter::repeat(42).take(5).collect()
}

fn cycle_demo() -> Vec<i32> {
    [1, 2, 3].iter().copied().cycle().take(7).collect()
}

// repeat_with for computed values
fn repeat_with_demo() -> Vec<f64> {
    let mut n = 1.0;
    std::iter::repeat_with(move || {
        let v = n;
        n *= 2.0;
        v
    })
    .take(5)
    .collect()
}

// === Approach 2: successors (like OCaml iterate) ===
fn iterate<T: Clone>(init: T, f: impl Fn(&T) -> T) -> impl Iterator<Item = T> {
    std::iter::successors(Some(init), move |prev| Some(f(prev)))
}

fn doubles_from(n: u64) -> impl Iterator<Item = u64> {
    iterate(n, |x| x * 2)
}

fn add_step(step: i32) -> impl Iterator<Item = i32> {
    iterate(0, move |x| x + step)
}

// === Approach 3: from_fn (like OCaml unfold) ===
fn unfold<T, S, F>(init: S, f: F) -> impl Iterator<Item = T>
where
    F: Fn(&S) -> Option<(T, S)>,
{
    let mut state = Some(init);
    std::iter::from_fn(move || {
        let s = state.take()?;
        let (value, next) = f(&s)?;
        state = Some(next);
        Some(value)
    })
}

fn fibonacci_unfold() -> impl Iterator<Item = u64> {
    unfold((0u64, 1u64), |&(a, b)| Some((a, (b, a + b))))
}

fn digits(mut n: u64) -> Vec<u64> {
    if n == 0 {
        return vec![0];
    }
    let mut result: Vec<u64> =
        unfold(n, |&n| if n == 0 { None } else { Some((n % 10, n / 10)) }).collect();
    result.reverse();
    result
}

// Combine infinite iterators
fn interleave<T>(
    a: impl Iterator<Item = T>,
    b: impl Iterator<Item = T>,
) -> impl Iterator<Item = T> {
    a.zip(b)
        .flat_map(|(x, y)| std::iter::once(x).chain(std::iter::once(y)))
}

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

    #[test]
    fn test_repeat() {
        assert_eq!(repeat_demo(), vec![42, 42, 42, 42, 42]);
    }

    #[test]
    fn test_cycle() {
        assert_eq!(cycle_demo(), vec![1, 2, 3, 1, 2, 3, 1]);
    }

    #[test]
    fn test_doubles() {
        let v: Vec<u64> = doubles_from(1).take(5).collect();
        assert_eq!(v, vec![1, 2, 4, 8, 16]);
    }

    #[test]
    fn test_iterate_add() {
        let v: Vec<i32> = add_step(3).take(5).collect();
        assert_eq!(v, vec![0, 3, 6, 9, 12]);
    }

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

    #[test]
    fn test_digits() {
        assert_eq!(digits(12345), vec![1, 2, 3, 4, 5]);
        assert_eq!(digits(0), vec![0]);
        assert_eq!(digits(9), vec![9]);
    }

    #[test]
    fn test_interleave() {
        let v: Vec<i32> = interleave(0..5, 10..15).collect();
        assert_eq!(v, vec![0, 10, 1, 11, 2, 12, 3, 13, 4, 14]);
    }

    #[test]
    fn test_successors_collatz() {
        let collatz: Vec<u64> = std::iter::successors(Some(6u64), |&n| {
            if n == 1 {
                None
            } else if n % 2 == 0 {
                Some(n / 2)
            } else {
                Some(3 * n + 1)
            }
        })
        .collect();
        assert_eq!(collatz, vec![6, 3, 10, 5, 16, 8, 4, 2, 1]);
    }
}

(* Example 090: Infinite Iterators *)
(* iterate, repeat, cycle, unfold *)

(* Approach 1: repeat and cycle *)
let repeat x () = Seq.Cons (x, repeat x)

let rec cycle lst () =
  let rec from = function
    | [] -> cycle lst ()
    | x :: rest -> Seq.Cons (x, fun () -> from rest)
  in
  from lst

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: iterate — apply function repeatedly *)
let iterate f x =
  let rec aux v () = Seq.Cons (v, aux (f v)) in
  aux x

let doubles_from n = iterate (fun x -> x * 2) n
let collatz_seq n = iterate (fun x -> if x mod 2 = 0 then x / 2 else 3 * x + 1) n

(* Approach 3: unfold — generalized sequence generation *)
let unfold f init =
  let rec aux state () =
    match f state with
    | None -> Seq.Nil
    | Some (value, next_state) -> Seq.Cons (value, aux next_state)
  in
  aux init

let fibonacci_unfold () =
  unfold (fun (a, b) -> Some (a, (b, a + b))) (0, 1)

let range_unfold start stop =
  unfold (fun n -> if n >= stop then None else Some (n, n + 1)) start

let digits n =
  if n = 0 then [0]
  else
    unfold (fun n -> if n = 0 then None else Some (n mod 10, n / 10)) n
    |> seq_take 100
    |> List.rev

(* Tests *)
let () =
  assert (seq_take 5 (repeat 42) = [42; 42; 42; 42; 42]);
  assert (seq_take 7 (cycle [1; 2; 3]) = [1; 2; 3; 1; 2; 3; 1]);

  assert (seq_take 5 (doubles_from 1) = [1; 2; 4; 8; 16]);
  assert (seq_take 5 (iterate (( + ) 3) 0) = [0; 3; 6; 9; 12]);

  assert (seq_take 8 (fibonacci_unfold ()) = [0; 1; 1; 2; 3; 5; 8; 13]);
  assert (seq_take 5 (range_unfold 3 8) = [3; 4; 5; 6; 7]);
  assert (digits 12345 = [1; 2; 3; 4; 5]);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_repeat() {
        assert_eq!(repeat_demo(), vec![42, 42, 42, 42, 42]);
    }

    #[test]
    fn test_cycle() {
        assert_eq!(cycle_demo(), vec![1, 2, 3, 1, 2, 3, 1]);
    }

    #[test]
    fn test_doubles() {
        let v: Vec<u64> = doubles_from(1).take(5).collect();
        assert_eq!(v, vec![1, 2, 4, 8, 16]);
    }

    #[test]
    fn test_iterate_add() {
        let v: Vec<i32> = add_step(3).take(5).collect();
        assert_eq!(v, vec![0, 3, 6, 9, 12]);
    }

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

    #[test]
    fn test_digits() {
        assert_eq!(digits(12345), vec![1, 2, 3, 4, 5]);
        assert_eq!(digits(0), vec![0]);
        assert_eq!(digits(9), vec![9]);
    }

    #[test]
    fn test_interleave() {
        let v: Vec<i32> = interleave(0..5, 10..15).collect();
        assert_eq!(v, vec![0, 10, 1, 11, 2, 12, 3, 13, 4, 14]);
    }

    #[test]
    fn test_successors_collatz() {
        let collatz: Vec<u64> = std::iter::successors(Some(6u64), |&n| {
            if n == 1 {
                None
            } else if n % 2 == 0 {
                Some(n / 2)
            } else {
                Some(3 * n + 1)
            }
        })
        .collect();
        assert_eq!(collatz, vec![6, 3, 10, 5, 16, 8, 4, 2, 1]);
    }
}

Deep Comparison

Comparison: Infinite Iterators

Repeat

OCaml:

let repeat x () = Seq.Cons (x, repeat x)
seq_take 5 (repeat 42)  (* [42; 42; 42; 42; 42] *)

Rust:

std::iter::repeat(42).take(5).collect::<Vec<_>>()  // [42, 42, 42, 42, 42]

Cycle

OCaml:

let rec cycle lst () =
  let rec from = function
    | [] -> cycle lst ()
    | x :: rest -> Seq.Cons (x, fun () -> from rest)
  in from lst

Rust:

[1, 2, 3].iter().copied().cycle().take(7).collect::<Vec<_>>()

Iterate (Successors)

OCaml:

let iterate f x =
  let rec aux v () = Seq.Cons (v, aux (f v)) in
  aux x

let doubles = iterate (fun x -> x * 2) 1

Rust:

std::iter::successors(Some(1u64), |&x| Some(x * 2))

Unfold

OCaml:

let unfold f init =
  let rec aux state () =
    match f state with
    | None -> Seq.Nil
    | Some (value, next) -> Seq.Cons (value, aux next)
  in aux init

let fib = unfold (fun (a,b) -> Some (a, (b, a+b))) (0, 1)

Rust:

fn fibonacci() -> impl Iterator<Item = u64> {
    let mut state = (0u64, 1u64);
    std::iter::from_fn(move || {
        let val = state.0;
        state = (state.1, state.0 + state.1);
        Some(val)
    })
}

Exercises

Implement powers_of_two as an infinite iterator and use it to find the first power of 2 exceeding one million.

Use cycle to implement round_robin<T: Clone>(vecs: &[Vec<T>]) -> impl Iterator<Item = T> that cycles through elements in rotation.

Implement collatz_lengths() as an infinite iterator yielding the Collatz sequence length for n = 1, 2, 3, ...

Open Source Repos

functional-rust

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

Rust