843 Advanced

Generic Memoization

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Generic Memoization" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Recursive functions with overlapping subproblems waste exponential time recomputing the same results. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Recursive functions with overlapping subproblems waste exponential time recomputing the same results. Memoization wraps a function with a cache: on the first call with given arguments, compute and store the result; on subsequent calls, return the cached value. While specific DP algorithms hard-code their memoization tables, generic memoization provides a reusable cache wrapper for any pure function. This pattern is fundamental in functional languages (Haskell's memoize, OCaml's Hashtbl-based wrappers) and enables transparent DP without restructuring code. Real-world uses: web request caching, computed property memoization in UI frameworks, and expensive query result caching.

🎯 Learning Outcomes

• Implement a HashMap-backed memoizer that wraps any Fn(K) -> V where K is hashable

• Handle recursive memoization using RefCell<HashMap> for interior mutability

• Understand the challenge: recursive memoized functions cannot easily call themselves through the cache

• Apply memoization to Fibonacci, LCS, and graph shortest paths to see exponential → polynomial speedup

• Recognize the difference from tabulation: memoization is top-down and lazy; tabulation is bottom-up and eager

Code Example

#![allow(clippy::all)]
//! Placeholder

(* Generic Memoisation in OCaml *)

(* Generic memoize: wrap any function f with a hash-table cache *)
let memoize (f : ('a, 'b) Hashtbl.t -> 'a -> 'b) : ('a -> 'b) =
  let cache = Hashtbl.create 64 in
  let rec go arg =
    match Hashtbl.find_opt cache arg with
    | Some v -> v
    | None ->
      let v = f cache arg in
      Hashtbl.add cache arg v;
      v
  in
  ignore go;  (* go is the memoised version, but we need to close over it *)
  (* Better pattern: pass cache explicitly *)
  let cache2 = Hashtbl.create 64 in
  fun arg ->
    match Hashtbl.find_opt cache2 arg with
    | Some v -> v
    | None ->
      let v = f cache2 arg in
      Hashtbl.add cache2 arg v;
      v

(* Fibonacci with memoisation — the classic example *)
let fib_memo : int -> int =
  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

(* Coin change: minimum coins to make amount *)
let coin_change (coins : int list) (amount : int) : int option =
  let cache = Hashtbl.create 128 in
  let inf = max_int / 2 in
  let rec go amt =
    if amt = 0 then 0
    else if amt < 0 then inf
    else
      match Hashtbl.find_opt cache amt with
      | Some v -> v
      | None ->
        let best = List.fold_left (fun best c ->
          min best (1 + go (amt - c))
        ) inf coins in
        Hashtbl.add cache amt best;
        best
  in
  let result = go amount in
  if result >= inf then None else Some result

(* Edit distance with memoisation *)
let edit_distance (s : string) (t : string) : int =
  let m = String.length s and n = String.length t in
  let cache = Hashtbl.create 256 in
  let rec go i j =
    if i = m then n - j
    else if j = n then m - i
    else
      match Hashtbl.find_opt cache (i, j) with
      | Some v -> v
      | None ->
        let v =
          if s.[i] = t.[j] then go (i+1) (j+1)
          else 1 + min (go (i+1) j) (min (go i (j+1)) (go (i+1) (j+1)))
        in
        Hashtbl.add cache (i, j) v;
        v
  in
  go 0 0

let () =
  for n = 0 to 15 do
    Printf.printf "fib(%d) = %d\n" n (fib_memo n)
  done;
  Printf.printf "\ncoin_change([1,5,10,25], 41) = %s\n"
    (match coin_change [1;5;10;25] 41 with Some v -> string_of_int v | None -> "None");
  Printf.printf "coin_change([2], 3) = %s\n"
    (match coin_change [2] 3 with Some v -> string_of_int v | None -> "None");
  Printf.printf "\nedit_distance('kitten', 'sitting') = %d  (expected 3)\n"
    (edit_distance "kitten" "sitting");
  Printf.printf "edit_distance('', 'abc') = %d\n" (edit_distance "" "abc")

Key Differences

Aspect	Rust	OCaml
Interior mutability	`RefCell<HashMap>`	`Hashtbl` (inherently mutable)
Recursive wrapper	`&Self` second arg	`ref` to function
Key constraint	`Eq + Hash + Clone`	`Hashtbl` equality
Thread safety	Use `Mutex<HashMap>` instead	Not needed for single-threaded
Eviction	Manual `HashMap::retain`	`Weak.t` for GC integration
Lazy vs eager	Lazy (top-down)	Same

OCaml Approach

OCaml memoization is simpler: let memoize f = let tbl = Hashtbl.create 16 in fun x -> match Hashtbl.find_opt tbl x with Some v -> v | None -> let v = f x in Hashtbl.add tbl x v; v. Recursive memoization uses a ref for the function: let rec_memo f = let r = ref (fun _ -> assert false) in let m = memoize (fun x -> f !r x) in r := m; m. OCaml's first-class mutability makes this straightforward. The Weak.t module enables cache eviction for memory-constrained situations.

Full Source

#![allow(clippy::all)]
//! Placeholder

(* Generic Memoisation in OCaml *)

(* Generic memoize: wrap any function f with a hash-table cache *)
let memoize (f : ('a, 'b) Hashtbl.t -> 'a -> 'b) : ('a -> 'b) =
  let cache = Hashtbl.create 64 in
  let rec go arg =
    match Hashtbl.find_opt cache arg with
    | Some v -> v
    | None ->
      let v = f cache arg in
      Hashtbl.add cache arg v;
      v
  in
  ignore go;  (* go is the memoised version, but we need to close over it *)
  (* Better pattern: pass cache explicitly *)
  let cache2 = Hashtbl.create 64 in
  fun arg ->
    match Hashtbl.find_opt cache2 arg with
    | Some v -> v
    | None ->
      let v = f cache2 arg in
      Hashtbl.add cache2 arg v;
      v

(* Fibonacci with memoisation — the classic example *)
let fib_memo : int -> int =
  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

(* Coin change: minimum coins to make amount *)
let coin_change (coins : int list) (amount : int) : int option =
  let cache = Hashtbl.create 128 in
  let inf = max_int / 2 in
  let rec go amt =
    if amt = 0 then 0
    else if amt < 0 then inf
    else
      match Hashtbl.find_opt cache amt with
      | Some v -> v
      | None ->
        let best = List.fold_left (fun best c ->
          min best (1 + go (amt - c))
        ) inf coins in
        Hashtbl.add cache amt best;
        best
  in
  let result = go amount in
  if result >= inf then None else Some result

(* Edit distance with memoisation *)
let edit_distance (s : string) (t : string) : int =
  let m = String.length s and n = String.length t in
  let cache = Hashtbl.create 256 in
  let rec go i j =
    if i = m then n - j
    else if j = n then m - i
    else
      match Hashtbl.find_opt cache (i, j) with
      | Some v -> v
      | None ->
        let v =
          if s.[i] = t.[j] then go (i+1) (j+1)
          else 1 + min (go (i+1) j) (min (go i (j+1)) (go (i+1) (j+1)))
        in
        Hashtbl.add cache (i, j) v;
        v
  in
  go 0 0

let () =
  for n = 0 to 15 do
    Printf.printf "fib(%d) = %d\n" n (fib_memo n)
  done;
  Printf.printf "\ncoin_change([1,5,10,25], 41) = %s\n"
    (match coin_change [1;5;10;25] 41 with Some v -> string_of_int v | None -> "None");
  Printf.printf "coin_change([2], 3) = %s\n"
    (match coin_change [2] 3 with Some v -> string_of_int v | None -> "None");
  Printf.printf "\nedit_distance('kitten', 'sitting') = %d  (expected 3)\n"
    (edit_distance "kitten" "sitting");
  Printf.printf "edit_distance('', 'abc') = %d\n" (edit_distance "" "abc")

Deep Comparison

OCaml vs Rust: Memoization Generic

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement thread-safe memoization using Arc<Mutex<HashMap>> and measure the synchronization overhead.

Add a cache eviction policy: LRU (evict least recently used) or LFU (evict least frequently used).

Implement memoize_recursive that allows the function to call itself via the memoized wrapper without &Self threading.

Benchmark memoized Fibonacci(50) vs. tabulated DP and compare code clarity.

Implement memoization with TTL (time-to-live): entries expire after a configurable duration.

Open Source Repos

functional-rust

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

Rust