🎬 How Rust Iterators Work Lazy evaluation, chaining, collect(), and zero-cost abstractions.

📝 Text version (for readers / accessibility)

• Iterators are lazy — .map(), .filter(), .take() build a chain but do no work until consumed

• .collect() triggers evaluation, transforming the chain into a Vec, HashMap, or other collection

• Zero-cost abstraction: iterator chains compile to the same machine code as hand-written loops

• .iter() borrows, .into_iter() consumes, .iter_mut() borrows mutably

• Chaining replaces nested loops with a readable, composable pipeline

087: Difference of Squares

Difficulty: Beginner Category: Math / Recursion Concept: Mathematical computation with iterators and closed-form formulas Key Insight: Both languages support iterator-based and formula-based approaches. Rust ranges (1..=n) are more ergonomic than OCaml's List.init.

/// Difference of Squares
///
/// Ownership: All values are Copy integers. No ownership concerns.

/// Square of the sum of first n natural numbers
pub fn square_of_sum(n: u64) -> u64 {
    let s: u64 = (1..=n).sum();
    s * s
}

/// Sum of the squares of first n natural numbers
pub fn sum_of_squares(n: u64) -> u64 {
    (1..=n).map(|x| x * x).sum()
}

/// Difference
pub fn difference(n: u64) -> u64 {
    square_of_sum(n) - sum_of_squares(n)
}

/// Version 2: Using closed-form formulas (O(1))
pub fn square_of_sum_formula(n: u64) -> u64 {
    let s = n * (n + 1) / 2;
    s * s
}

pub fn sum_of_squares_formula(n: u64) -> u64 {
    n * (n + 1) * (2 * n + 1) / 6
}

pub fn difference_formula(n: u64) -> u64 {
    square_of_sum_formula(n) - sum_of_squares_formula(n)
}

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

    #[test]
    fn test_square_of_sum() {
        assert_eq!(square_of_sum(10), 3025);
    }

    #[test]
    fn test_sum_of_squares() {
        assert_eq!(sum_of_squares(10), 385);
    }

    #[test]
    fn test_difference() {
        assert_eq!(difference(10), 2640);
    }

    #[test]
    fn test_one() {
        assert_eq!(difference(1), 0);
    }

    #[test]
    fn test_formula_matches() {
        for n in 1..=100 {
            assert_eq!(difference(n), difference_formula(n));
        }
    }

    #[test]
    fn test_large() {
        assert_eq!(difference_formula(100), 25164150);
    }
}

fn main() {
    println!("{:?}", square_of_sum(10), 3025);
    println!("{:?}", sum_of_squares(10), 385);
    println!("{:?}", difference(10), 2640);
}

(* Difference of Squares *)

(* Version 1: Using fold *)
let square_of_sum n =
  let s = List.init n (fun i -> i + 1) |> List.fold_left (+) 0 in
  s * s

let sum_of_squares n =
  List.init n (fun i -> i + 1)
  |> List.fold_left (fun acc x -> acc + x * x) 0

let difference n = square_of_sum n - sum_of_squares n

(* Version 2: Closed-form *)
let square_of_sum_formula n =
  let s = n * (n + 1) / 2 in s * s

let sum_of_squares_formula n =
  n * (n + 1) * (2 * n + 1) / 6

let () =
  assert (difference 10 = 2640);
  assert (square_of_sum_formula 10 = square_of_sum 10);
  assert (sum_of_squares_formula 10 = sum_of_squares 10)

📊 Detailed Comparison

Difference of Squares — Comparison

Core Insight

Simple mathematical computations highlight the difference between OCaml's list-based iteration and Rust's range iterators. Rust ranges are lazy and allocation-free; OCaml's `List.init` creates a temporary list.

OCaml Approach

`List.init n (fun i -> i + 1)` creates [1..n] as a list (heap allocation)
`List.fold_left (+) 0` sums the list
`|>` pipe operator chains transformations
Closed-form formulas avoid list creation

Rust Approach

`(1..=n)` creates a lazy range (no allocation)
`.sum()` and `.map(|x| x * x).sum()` consume the iterator
Ranges are zero-cost abstractions
Same closed-form formulas work identically

Comparison Table

Aspect	OCaml	Rust
Range	`List.init n (fun i -> i+1)`	`(1..=n)`
Sum	`List.fold_left (+) 0`	`.sum()`
Map+Sum	`fold_left (fun acc x -> ...)`	`.map().sum()`
Allocation	List created in memory	Zero allocation (lazy)
Overflow	Silent	Panic in debug mode

Learner Notes

Rust ranges `1..=n` are inclusive; `1..n` is exclusive (like Python)
`.sum()` requires type annotation sometimes: `let s: u64 = (1..=n).sum()`
OCaml `List.init` is O(n) space; Rust ranges are O(1) space
Both closed-form versions are O(1) time and space