287 Intermediate

287: Recursive Sequences with successors()

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "287: Recursive Sequences with successors()" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Many mathematical and algorithmic sequences are defined recursively: each element is a function of its predecessor. Key difference from OCaml: 1. **Naming**: Rust calls it `successors`; Haskell calls it `iterate` (infinite) or `unfoldr`; OCaml uses `Seq.unfold`.

Tutorial

The Problem

Many mathematical and algorithmic sequences are defined recursively: each element is a function of its predecessor. Powers of 2 (1, 2, 4, 8, ...), the Collatz sequence, convergence sequences in numerical methods, and tree/graph traversal via repeated next_node(current) calls all share this structure. std::iter::successors() formalizes this pattern: given a first value and a function f(current) -> Option<next>, it generates the entire infinite (or finite) sequence.

🎯 Learning Outcomes

• Understand successors(first, f) as generating first, f(first), f(f(first)), ... until f returns None

• Use successors for power sequences, Collatz sequences, and convergence series

• Recognize successors as unfold specialized to single-value state

• Combine successors with take(), take_while(), and sum() to bound and aggregate sequences

Code Example

let powers_of_2: Vec<u32> = std::iter::successors(Some(1u32), |&n| {
    if n < 512 { Some(n * 2) } else { None }
}).collect();

let successors first f =
  Seq.unfold (fun state ->
    match state with
    | None -> None
    | Some x -> Some (x, f x)
  ) (Some first)

let powers_of_2 = successors 1 (fun x -> 
  if x < 256 then Some (x * 2) else None)

Key Differences

Naming: Rust calls it successors; Haskell calls it iterate (infinite) or unfoldr; OCaml uses Seq.unfold.

First value: Rust's successors takes Option<T> as the first argument — None produces an empty iterator immediately.

State vs output: successors uses the same type for state and output (current element is the state); from_fn separates them.

Convergence: Used in numerical methods (Newton's method iterations), parsing (advancing through AST nodes), and graph traversal (BFS/DFS via successive frontier sets).

OCaml Approach

OCaml's Seq.unfold is the equivalent — it threads a state through a generator function. For single-value state (where state equals current value), it directly mirrors successors:

let powers_of_2 max =
  Seq.unfold (fun n -> if n > max then None else Some (n, n * 2)) 1

let collatz start =
  Seq.unfold (fun n ->
    if n = 0 then None
    else Some (n, if n = 1 then 0  (* sentinel stop *)
                 else if n mod 2 = 0 then n/2 else 3*n+1)
  ) start

Full Source

#![allow(clippy::all)]
//! # Recursive Sequences with successors()
//!
//! `successors(first, f)` generates a sequence: first, f(first), f(f(first)), ...

/// Generate powers of 2 up to a maximum
pub fn powers_of_2(max: u32) -> impl Iterator<Item = u32> {
    std::iter::successors(
        Some(1u32),
        move |&n| {
            if n < max {
                Some(n * 2)
            } else {
                None
            }
        },
    )
}

/// Generate the Collatz sequence from a starting number
pub fn collatz(start: u64) -> impl Iterator<Item = u64> {
    std::iter::successors(Some(start), |&n| {
        if n == 1 {
            None
        } else if n % 2 == 0 {
            Some(n / 2)
        } else {
            Some(3 * n + 1)
        }
    })
}

/// Generate a geometric sequence (multiply by factor each step)
pub fn geometric(start: i32, factor: i32, max: i32) -> impl Iterator<Item = i32> {
    std::iter::successors(Some(start), move |&n| {
        let next = n.saturating_mul(factor);
        if next.abs() > max.abs() {
            None
        } else {
            Some(next)
        }
    })
}

/// Newton's method to approximate square root
pub fn newton_sqrt(target: f64, tolerance: f64) -> impl Iterator<Item = f64> {
    std::iter::successors(Some(1.0f64), move |&x| {
        let next = 0.5 * (x + target / x);
        if (next - x).abs() < tolerance {
            None
        } else {
            Some(next)
        }
    })
}

/// Shrinking string - remove first character each step
pub fn shrinking_string(s: String) -> impl Iterator<Item = String> {
    std::iter::successors(Some(s), |s| {
        if s.is_empty() {
            None
        } else {
            Some(s.chars().skip(1).collect())
        }
    })
}

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

    #[test]
    fn test_powers_of_2() {
        let result: Vec<u32> = powers_of_2(16).collect();
        assert_eq!(result, vec![1, 2, 4, 8, 16]);
    }

    #[test]
    fn test_powers_of_2_large() {
        let result: Vec<u32> = powers_of_2(512).collect();
        assert_eq!(result, vec![1, 2, 4, 8, 16, 32, 64, 128, 256, 512]);
    }

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

    #[test]
    fn test_collatz_27() {
        let result: Vec<u64> = collatz(27).collect();
        assert_eq!(result.len(), 112); // Famous long sequence
        assert_eq!(*result.last().unwrap(), 1);
    }

    #[test]
    fn test_geometric() {
        let result: Vec<i32> = geometric(1, 3, 729).collect();
        assert_eq!(result, vec![1, 3, 9, 27, 81, 243, 729]);
    }

    #[test]
    fn test_newton_sqrt() {
        let result: Vec<f64> = newton_sqrt(2.0, 1e-10).collect();
        let final_approx = *result.last().unwrap();
        assert!((final_approx - 2.0_f64.sqrt()).abs() < 1e-10);
    }

    #[test]
    fn test_shrinking_string() {
        let result: Vec<String> = shrinking_string("abc".to_string()).collect();
        assert_eq!(
            result,
            vec![
                "abc".to_string(),
                "bc".to_string(),
                "c".to_string(),
                "".to_string()
            ]
        );
    }

    #[test]
    fn test_successors_empty_if_first_is_none() {
        let result: Vec<i32> = std::iter::successors(None, |&_n: &i32| Some(1)).collect();
        assert!(result.is_empty());
    }
}

(* 287. Recursive sequences with successors() - OCaml *)

let successors first f =
  Seq.unfold (fun state ->
    match state with
    | None -> None
    | Some x -> Some (x, f x)
  ) (Some first)

let () =
  (* Powers of 2 *)
  let powers_of_2 = successors 1 (fun x -> if x < 256 then Some (x * 2) else None) in
  Printf.printf "Powers of 2: %s\n"
    (String.concat ", " (List.map string_of_int (List.of_seq powers_of_2)));

  (* Collatz sequence *)
  let collatz n =
    successors n (fun x ->
      if x = 1 then None
      else if x mod 2 = 0 then Some (x / 2)
      else Some (3 * x + 1)
    )
  in
  Printf.printf "Collatz(6): %s\n"
    (String.concat ", " (List.map string_of_int (List.of_seq (collatz 6))));

  (* Geometric sequence *)
  let geo = successors 1.0 (fun x -> if x > 100.0 then None else Some (x *. 3.0)) in
  Printf.printf "Geometric: %s\n"
    (String.concat ", " (List.map (Printf.sprintf "%.0f") (List.of_seq geo)))

✓ Tests Rust test suite

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

    #[test]
    fn test_powers_of_2() {
        let result: Vec<u32> = powers_of_2(16).collect();
        assert_eq!(result, vec![1, 2, 4, 8, 16]);
    }

    #[test]
    fn test_powers_of_2_large() {
        let result: Vec<u32> = powers_of_2(512).collect();
        assert_eq!(result, vec![1, 2, 4, 8, 16, 32, 64, 128, 256, 512]);
    }

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

    #[test]
    fn test_collatz_27() {
        let result: Vec<u64> = collatz(27).collect();
        assert_eq!(result.len(), 112); // Famous long sequence
        assert_eq!(*result.last().unwrap(), 1);
    }

    #[test]
    fn test_geometric() {
        let result: Vec<i32> = geometric(1, 3, 729).collect();
        assert_eq!(result, vec![1, 3, 9, 27, 81, 243, 729]);
    }

    #[test]
    fn test_newton_sqrt() {
        let result: Vec<f64> = newton_sqrt(2.0, 1e-10).collect();
        let final_approx = *result.last().unwrap();
        assert!((final_approx - 2.0_f64.sqrt()).abs() < 1e-10);
    }

    #[test]
    fn test_shrinking_string() {
        let result: Vec<String> = shrinking_string("abc".to_string()).collect();
        assert_eq!(
            result,
            vec![
                "abc".to_string(),
                "bc".to_string(),
                "c".to_string(),
                "".to_string()
            ]
        );
    }

    #[test]
    fn test_successors_empty_if_first_is_none() {
        let result: Vec<i32> = std::iter::successors(None, |&_n: &i32| Some(1)).collect();
        assert!(result.is_empty());
    }
}

Deep Comparison

OCaml vs Rust: successors()

Pattern 1: Powers of 2

OCaml

let successors first f =
  Seq.unfold (fun state ->
    match state with
    | None -> None
    | Some x -> Some (x, f x)
  ) (Some first)

let powers_of_2 = successors 1 (fun x -> 
  if x < 256 then Some (x * 2) else None)

Rust

let powers_of_2: Vec<u32> = std::iter::successors(Some(1u32), |&n| {
    if n < 512 { Some(n * 2) } else { None }
}).collect();

Pattern 2: Collatz Sequence

OCaml

let collatz n =
  successors n (fun x ->
    if x = 1 then None
    else if x mod 2 = 0 then Some (x / 2)
    else Some (3 * x + 1))

Rust

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();

Pattern 3: Newton's Method

Rust

let sqrt2: Vec<f64> = std::iter::successors(Some(1.0f64), |&x| {
    let next = 0.5 * (x + 2.0 / x);
    if (next - x).abs() < 1e-10 { None } else { Some(next) }
}).collect();

Key Differences

Aspect	OCaml	Rust
Builtin	`Seq.unfold` (manual)	`std::iter::successors`
First element	Part of unfold state	`Option<T>` parameter
Closure receives	Value (via seed)	`&T` reference
Termination	Return `None` state	Return `None`
Infinite	Return `Some` always	Same, use `.take(n)`

Exercises

Use successors to implement Newton's method for square root: starting from an initial guess, iterate x -> (x + n/x) / 2 until convergence.

Generate the binary representations of all powers of 2 up to 2^20 using successors(Some(1u32), |n| n.checked_mul(2)).

Use successors to traverse a linked structure: given a node type with an optional next pointer, traverse the entire list.

Open Source Repos

functional-rust

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

Rust