🎬 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

085: Accumulate — Custom Map

Difficulty: Beginner Category: Higher-Order Functions Concept: Implementing map from scratch without using the standard library version Key Insight: The recursive structure is identical in both languages, but Rust's idiomatic approach uses iterators rather than manual recursion.

/// Accumulate — Custom Map Implementation
///
/// Ownership: The function takes ownership of input vec and returns new vec.
/// The closure borrows or moves each element depending on the function.

/// Recursive version (not tail-recursive — will stack overflow on large inputs)
pub fn accumulate<T, U, F>(lst: &[T], f: F) -> Vec<U>
where
    F: Fn(&T) -> U,
{
    fn inner<T, U>(lst: &[T], f: &dyn Fn(&T) -> U) -> Vec<U> {
        match lst {
            [] => vec![],
            [head, tail @ ..] => {
                let mut result = vec![f(head)];
                result.extend(inner(tail, f));
                result
            }
        }
    }
    inner(lst, &f)
}

/// Tail-recursive version using accumulator
pub fn accumulate_tr<T, U, F>(lst: &[T], f: F) -> Vec<U>
where
    F: Fn(&T) -> U,
{
    let mut acc = Vec::with_capacity(lst.len());
    for item in lst {
        acc.push(f(item));
    }
    acc
}

/// Iterator-based version (most idiomatic Rust)
pub fn accumulate_iter<T, U>(lst: impl IntoIterator<Item = T>, f: impl Fn(T) -> U) -> Vec<U> {
    lst.into_iter().map(f).collect()
}

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

    #[test]
    fn test_squares() {
        assert_eq!(accumulate(&[1, 2, 3, 4, 5], |x| x * x), vec![1, 4, 9, 16, 25]);
    }

    #[test]
    fn test_empty() {
        assert_eq!(accumulate::<i32, i32, _>(&[], |x| x * x), Vec::<i32>::new());
    }

    #[test]
    fn test_strings() {
        let words = vec!["hello".to_string(), "world".to_string()];
        assert_eq!(
            accumulate(&words, |s| s.to_uppercase()),
            vec!["HELLO", "WORLD"]
        );
    }

    #[test]
    fn test_tail_recursive() {
        assert_eq!(accumulate_tr(&[1, 2, 3], |x| x + 10), vec![11, 12, 13]);
    }

    #[test]
    fn test_iterator_version() {
        assert_eq!(accumulate_iter(vec![1, 2, 3], |x| x * 2), vec![2, 4, 6]);
    }

    #[test]
    fn test_type_change() {
        assert_eq!(accumulate(&[1, 2, 3], |x| x.to_string()), vec!["1", "2", "3"]);
    }
}

(* Accumulate — Custom Map *)

(* Version 1: Simple recursive *)
let rec accumulate f = function
  | [] -> []
  | h :: t -> f h :: accumulate f t

(* Version 2: Tail-recursive with accumulator *)
let accumulate_tr f lst =
  let rec go acc = function
    | [] -> List.rev acc
    | h :: t -> go (f h :: acc) t
  in go [] lst

let () =
  assert (accumulate (fun x -> x * x) [1;2;3;4;5] = [1;4;9;16;25]);
  assert (accumulate_tr String.uppercase_ascii ["hello";"world"] = ["HELLO";"WORLD"])

📊 Detailed Comparison

Accumulate — Comparison

Core Insight

Implementing `map` from scratch reveals how both languages handle recursion, list construction, and higher-order functions. The recursive pattern is identical, but idiomatic Rust favors iterators over manual recursion.

OCaml Approach

`let rec accumulate f = function | [] -> [] | h :: t -> f h :: accumulate f t`
Pattern matching on list constructors (`[]` and `h :: t`)
Tail-recursive version reverses accumulator at the end
`List.rev acc` is the standard tail-recursive pattern

Rust Approach

Slice patterns `[head, tail @ ..]` mirror OCaml list patterns
`Vec::with_capacity` pre-allocates for known size
Iterator version: `.into_iter().map(f).collect()` — one line
Closure takes `&T` (borrow) or `T` (ownership) depending on variant

Comparison Table

Aspect	OCaml	Rust
Pattern	`h :: t`	`[head, tail @ ..]`
Build result	`::` cons	`vec![]` + extend
Tail-recursive	`List.rev acc`	`Vec::push` (already efficient)
Idiomatic	`List.map`	`.iter().map().collect()`
Closure	`fun x -> ...`	`	x	...` or `\	x\	...`

Learner Notes

Rust slice patterns are nightly-stable since 1.42 — use them!
`Vec::push` is amortized O(1), no need for reverse trick
The iterator version is what you'd actually write in production Rust
OCaml's `::` cons is O(1); Rust's `vec!` + extend is O(n) total