• Closures capture variables from their environment — by reference, mutable reference, or by value (move)
• Three traits: Fn (shared borrow), FnMut (mutable borrow), FnOnce (takes ownership)
• Higher-order functions like .map(), .filter(), .fold() accept closures as arguments
• move closures take ownership of captured variables — essential for threading
• Closures enable functional patterns: partial application, composition, and strategy
use std::collections::HashMap;
use std::hash::Hash;
// Generic memoizer: wraps any Fn(K)->V in an FnMut(K)->V with caching
fn memoize<K, V, F>(mut f: F) -> impl FnMut(K) -> V
where
K: Eq + Hash + Clone, // K must be hashable and cloneable for storage
V: Clone, // V must be cloneable to return from cache
F: FnMut(K) -> V,
{
let mut cache: HashMap<K, V> = HashMap::new();
move |key: K| {
if let Some(val) = cache.get(&key) {
return val.clone(); // cache hit — return immediately
}
let val = f(key.clone()); // cache miss — compute
cache.insert(key, val.clone());
val
}
}
// Usage: the cache lives inside the closure
let mut expensive = memoize(|n: i32| {
println!("computing {}^2...", n); // only prints on first call
n * n
});
expensive(5); // "computing 5^2..." → 25
expensive(5); // silent → 25 (cached)
expensive(6); // "computing 6^2..." → 36
// Fibonacci with memoization — wraps the recursive logic
fn make_fib() -> impl FnMut(u64) -> u64 {
let mut cache: HashMap<u64, u64> = HashMap::new();
cache.insert(0, 0);
cache.insert(1, 1);
fn fib_inner(n: u64, cache: &mut HashMap<u64, u64>) -> u64 {
if let Some(&v) = cache.get(&n) { return v; }
let v = fib_inner(n-1, cache) + fib_inner(n-2, cache);
cache.insert(n, v);
v
}
move |n| fib_inner(n, &mut cache) // cache is owned by the closure
}
let mut fib = make_fib();
println!("{}", fib(40)); // instant — all sub-results cached| Concept | OCaml | Rust |
|---|---|---|
| Mutable cache | `Hashtbl.t` with `ref` | `HashMap` captured by `FnMut` closure |
| Cache lookup | `Hashtbl.find_opt` | `HashMap::get(&key)` |
| First call | Compute + `Hashtbl.add` | Compute + `HashMap::insert` |
| Closure trait | N/A — all functions are `FnMut`-like | Must be `FnMut` (cache mutation) |
| Thread-safe version | `Mutex` + shared state | `Arc<Mutex<HashMap>>` in the closure |
//! # Closure Memoization — Caching Results
use std::collections::HashMap;
use std::hash::Hash;
/// Simple memoization wrapper
pub struct Memoize<F, A, R>
where
A: Eq + Hash + Clone,
R: Clone,
{
func: F,
cache: HashMap<A, R>,
}
impl<F, A, R> Memoize<F, A, R>
where
F: Fn(A) -> R,
A: Eq + Hash + Clone,
R: Clone,
{
pub fn new(func: F) -> Self {
Self {
func,
cache: HashMap::new(),
}
}
pub fn call(&mut self, arg: A) -> R {
if let Some(result) = self.cache.get(&arg) {
return result.clone();
}
let result = (self.func)(arg.clone());
self.cache.insert(arg, result.clone());
result
}
pub fn cache_size(&self) -> usize {
self.cache.len()
}
}
/// Recursive memoization (e.g., fibonacci)
pub fn memoized_fib() -> impl FnMut(u64) -> u64 {
let mut cache: HashMap<u64, u64> = HashMap::new();
fn fib_inner(n: u64, cache: &mut HashMap<u64, u64>) -> u64 {
if let Some(&result) = cache.get(&n) {
return result;
}
let result = if n <= 1 {
n
} else {
fib_inner(n - 1, cache) + fib_inner(n - 2, cache)
};
cache.insert(n, result);
result
}
move |n| fib_inner(n, &mut cache)
}
/// Once-computed lazy value
pub struct Lazy<T, F: FnOnce() -> T> {
value: Option<T>,
init: Option<F>,
}
impl<T, F: FnOnce() -> T> Lazy<T, F> {
pub fn new(init: F) -> Self {
Self {
value: None,
init: Some(init),
}
}
pub fn get(&mut self) -> &T {
if self.value.is_none() {
let init = self.init.take().expect("already initialized");
self.value = Some(init());
}
self.value.as_ref().unwrap()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_memoize() {
let mut memo = Memoize::new(|x: i32| {
x * x
});
assert_eq!(memo.call(5), 25);
assert_eq!(memo.call(5), 25); // Cached
assert_eq!(memo.call(6), 36);
assert_eq!(memo.cache_size(), 2);
}
#[test]
fn test_memoized_fib() {
let mut fib = memoized_fib();
assert_eq!(fib(0), 0);
assert_eq!(fib(1), 1);
assert_eq!(fib(10), 55);
assert_eq!(fib(20), 6765);
assert_eq!(fib(40), 102334155);
}
#[test]
fn test_lazy() {
use std::cell::Cell;
let computed = Cell::new(false);
let mut lazy = Lazy::new(|| {
computed.set(true);
42
});
assert!(!computed.get());
assert_eq!(*lazy.get(), 42);
assert!(computed.get());
assert_eq!(*lazy.get(), 42); // Doesn't recompute
}
#[test]
fn test_expensive_computation() {
let mut memo = Memoize::new(|s: String| {
s.chars().map(|c| c as u32).sum::<u32>()
});
let result1 = memo.call("hello".to_string());
let result2 = memo.call("hello".to_string());
assert_eq!(result1, result2);
}
}
(* Memoization in OCaml using Hashtbl *)
let memoize f =
let cache = Hashtbl.create 16 in
fun x ->
match Hashtbl.find_opt cache x with
| Some v -> v
| None ->
let v = f x in
Hashtbl.add cache x v;
v
(* Fibonacci without memoization — exponential *)
let rec fib_slow n =
if n <= 1 then n
else fib_slow (n - 1) + fib_slow (n - 2)
(* With memoization — but naive approach doesn't help recursive calls *)
let fib_memo =
let cache = Hashtbl.create 100 in
let rec fib n =
match Hashtbl.find_opt cache n with
| Some v -> v
| None ->
let v = if n <= 1 then n else fib (n - 1) + fib (n - 2) in
Hashtbl.add cache n v;
v
in
fib
(* Generic expensive computation *)
let expensive_square =
memoize (fun n ->
(* Simulate work *)
let result = n * n in
Printf.printf " [computing %d^2]\n" n;
result)
let () =
Printf.printf "fib(10) = %d\n" (fib_memo 10);
Printf.printf "fib(20) = %d\n" (fib_memo 20);
Printf.printf "fib(10) = %d (cached)\n" (fib_memo 10);
Printf.printf "\nSquares:\n";
Printf.printf "5^2 = %d\n" (expensive_square 5);
Printf.printf "5^2 = %d\n" (expensive_square 5); (* cached *)
Printf.printf "6^2 = %d\n" (expensive_square 6)