🎬 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

1051: Fibonacci with HashMap Memoization

Difficulty: Intermediate Category: Dynamic Programming / Memoization Concept: Top-down memoization using hash maps to cache recursive Fibonacci results Key Insight: OCaml's Hashtbl and Rust's HashMap both enable O(n) memoized Fibonacci, but Rust's ownership rules make the memoization closure pattern more complex — requiring explicit lifetime management or interior mutability patterns.

// 1051: Fibonacci with HashMap Memoization

use std::collections::HashMap;

// Approach 1: Iterative with HashMap cache
fn fib_memo(n: u64, cache: &mut HashMap<u64, u64>) -> u64 {
    if n <= 1 {
        return n;
    }
    if let Some(&v) = cache.get(&n) {
        return v;
    }
    let v = fib_memo(n - 1, cache) + fib_memo(n - 2, cache);
    cache.insert(n, v);
    v
}

// Approach 2: Closure-based memoizer
fn make_fib_memo() -> impl FnMut(u64) -> u64 {
    let mut cache = HashMap::new();
    move |n| {
        fn inner(n: u64, cache: &mut HashMap<u64, u64>) -> u64 {
            if n <= 1 {
                return n;
            }
            if let Some(&v) = cache.get(&n) {
                return v;
            }
            let v = inner(n - 1, cache) + inner(n - 2, cache);
            cache.insert(n, v);
            v
        }
        inner(n, &mut cache)
    }
}

// Approach 3: Generic memoization wrapper
struct Memoize<F> {
    cache: HashMap<u64, u64>,
    func: F,
}

impl<F: Fn(u64, &mut dyn FnMut(u64) -> u64) -> u64> Memoize<F> {
    fn new(func: F) -> Self {
        Memoize {
            cache: HashMap::new(),
            func,
        }
    }

    fn call(&mut self, n: u64) -> u64 {
        if let Some(&v) = self.cache.get(&n) {
            return v;
        }
        // We need to use unsafe here or restructure; instead use a simpler pattern
        let mut cache = std::mem::take(&mut self.cache);
        let v = (self.func)(n, &mut |x| {
            if x <= 1 {
                return x;
            }
            if let Some(&v) = cache.get(&x) {
                return v;
            }
            // For deeply nested, fall back to iterative
            let mut a = 0u64;
            let mut b = 1u64;
            for _ in 2..=x {
                let t = a + b;
                a = b;
                b = t;
            }
            cache.insert(x, b);
            b
        });
        cache.insert(n, v);
        self.cache = cache;
        v
    }
}

fn main() {
    let mut cache = HashMap::new();
    println!("fib(10) = {}", fib_memo(10, &mut cache));
    println!("fib(20) = {}", fib_memo(20, &mut cache));
    println!("fib(30) = {}", fib_memo(30, &mut cache));

    let mut fib = make_fib_memo();
    println!("closure fib(30) = {}", fib(30));

    let mut memo = Memoize::new(|n, recurse: &mut dyn FnMut(u64) -> u64| {
        if n <= 1 {
            n
        } else {
            recurse(n - 1) + recurse(n - 2)
        }
    });
    println!("generic fib(30) = {}", memo.call(30));
}

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

    #[test]
    fn test_fib_memo() {
        let mut cache = HashMap::new();
        assert_eq!(fib_memo(0, &mut cache), 0);
        assert_eq!(fib_memo(1, &mut cache), 1);
        assert_eq!(fib_memo(10, &mut cache), 55);
        assert_eq!(fib_memo(20, &mut cache), 6765);
        assert_eq!(fib_memo(30, &mut cache), 832040);
    }

    #[test]
    fn test_fib_closure() {
        let mut fib = make_fib_memo();
        assert_eq!(fib(0), 0);
        assert_eq!(fib(1), 1);
        assert_eq!(fib(10), 55);
        assert_eq!(fib(20), 6765);
        assert_eq!(fib(30), 832040);
    }

    #[test]
    fn test_fib_generic() {
        let mut memo = Memoize::new(|n, recurse: &mut dyn FnMut(u64) -> u64| {
            if n <= 1 { n } else { recurse(n - 1) + recurse(n - 2) }
        });
        assert_eq!(memo.call(0), 0);
        assert_eq!(memo.call(10), 55);
        assert_eq!(memo.call(30), 832040);
    }
}

(* 1051: Fibonacci with HashMap Memoization *)

(* Approach 1: Recursive with Hashtbl memoization *)
let fib_memo () =
  let cache = Hashtbl.create 64 in
  let rec fib n =
    if n <= 1 then n
    else
      match Hashtbl.find_opt cache n with
      | Some v -> v
      | None ->
        let v = fib (n - 1) + fib (n - 2) in
        Hashtbl.add cache n v;
        v
  in
  fib

(* Approach 2: Functional memoization with ref to Map *)
module IntMap = Map.Make(Int)

let fib_map n =
  let cache = ref IntMap.empty in
  let rec fib n =
    if n <= 1 then n
    else
      match IntMap.find_opt n !cache with
      | Some v -> v
      | None ->
        let v = fib (n - 1) + fib (n - 2) in
        cache := IntMap.add n v !cache;
        v
  in
  fib n

(* Approach 3: CPS with memoization *)
let fib_cps n =
  let cache = Hashtbl.create 64 in
  let rec fib n k =
    if n <= 1 then k n
    else
      match Hashtbl.find_opt cache n with
      | Some v -> k v
      | None ->
        fib (n - 1) (fun a ->
          fib (n - 2) (fun b ->
            let v = a + b in
            Hashtbl.add cache n v;
            k v))
  in
  fib n Fun.id

let () =
  let fib = fib_memo () in
  assert (fib 0 = 0);
  assert (fib 1 = 1);
  assert (fib 10 = 55);
  assert (fib 20 = 6765);
  assert (fib 30 = 832040);

  assert (fib_map 10 = 55);
  assert (fib_map 20 = 6765);
  assert (fib_map 30 = 832040);

  assert (fib_cps 10 = 55);
  assert (fib_cps 20 = 6765);
  assert (fib_cps 30 = 832040);

  Printf.printf "✓ All tests passed\n"

📊 Detailed Comparison

Fibonacci with HashMap Memoization — Comparison

Core Insight

Memoization transforms exponential O(2^n) Fibonacci into O(n). Both languages support hash-based caching, but OCaml's mutable Hashtbl is simpler to thread through recursion than Rust's HashMap due to borrowing constraints.

OCaml Approach

`Hashtbl.create` for imperative memoization — simple and direct
`Map` module for a more functional flavor using immutable maps with a ref cell
CPS (continuation-passing style) variant shows functional composition with memoization
The `find_opt` / pattern match idiom is clean and readable

Rust Approach

`HashMap` passed as `&mut` parameter — explicit but requires threading through calls
Closure-based memoizer captures HashMap in a `move` closure
Generic `Memoize` struct demonstrates the complexity of self-referential memoization in Rust
Rust's borrow checker makes recursive memoization harder: you can't borrow `cache` mutably while also recursing

Comparison Table

Aspect	OCaml	Rust
Hash map type	`Hashtbl.t` (mutable)	`HashMap<K, V>`
Memoization pattern	`find_opt` + `add`	`get` + `insert`
Closure capture	Trivial — closures capture freely	Requires `move` + ownership management
Recursive memo	Natural — just call `fib` recursively	Borrow checker friction with `&mut`
Immutable variant	`Map` module + `ref` cell	Not idiomatic — would need `RefCell`
Performance	GC-managed hash table	Zero-cost HashMap with predictable perf