cleveragents-core/.opencode/skills/programming-patterns/references/functional/memoization.md

Memoization Pattern

Problem

A pure function is called repeatedly with the same arguments, performing expensive computation each time. This wastes CPU cycles when the result is deterministic for given inputs.

Solution

Memoize the function by caching its results keyed by the input arguments. On the first call with given arguments, compute and store the result. On subsequent calls with the same arguments, return the cached result directly.

When to Use

• Recursive algorithms with overlapping subproblems (Fibonacci, dynamic programming)
• Expensive pure computations called with repeated inputs
• API response caching (same request parameters -> same response)
• Any pure function where time can be traded for space

When to Avoid

• Functions with side effects (cache hides the side effect on repeated calls)
• Functions with very large input/output spaces (unbounded memory)
• Functions where inputs are rarely repeated
• When cache invalidation is complex (time-based, dependency-based)

Pseudocode

function memoize(fn):
    cache = {}
    return function(...args):
        key = hash(args)
        if key not in cache:
            cache[key] = fn(...args)
        return cache[key]

@memoize
function fibonacci(n):
    if n <= 1: return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(50))  // instant, not 2^50 calls

Python

from functools import lru_cache
import time
from typing import Dict, Callable, TypeVar

# Method 1: functools.lru_cache (built-in)
@lru_cache(maxsize=128)
def fibonacci(n: int) -> int:
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# Method 2: Manual memoization decorator
def memoize(fn: Callable) -> Callable:
    cache: Dict = {}
    def wrapper(*args):
        if args not in cache:
            cache[args] = fn(*args)
        return cache[args]
    wrapper.cache = cache
    return wrapper

@memoize
def expensive_compute(x: int, y: int) -> int:
    time.sleep(0.1)  # simulate expensive work
    return x * y + x + y

def main() -> None:
    # Fibonacci with lru_cache
    print("=== Fibonacci (lru_cache) ===")
    start = time.time()
    result = fibonacci(40)
    elapsed = time.time() - start
    print(f"fibonacci(40) = {result} (took {elapsed:.4f}s)")
    print(f"Cache info: {fibonacci.cache_info()}")

    # Manual memoization
    print("\n=== Expensive Compute (manual memo) ===")
    start = time.time()
    r1 = expensive_compute(5, 10)
    t1 = time.time() - start

    start = time.time()
    r2 = expensive_compute(5, 10)  # cached
    t2 = time.time() - start

    start = time.time()
    r3 = expensive_compute(3, 7)   # new args
    t3 = time.time() - start

    print(f"compute(5,10) = {r1} ({t1:.4f}s)")
    print(f"compute(5,10) = {r2} ({t2:.4f}s) [cached]")
    print(f"compute(3,7)  = {r3} ({t3:.4f}s)")
    print(f"Cache size: {len(expensive_compute.cache)}")

    # Practical: memoized path computation
    @lru_cache(maxsize=None)
    def grid_paths(m: int, n: int) -> int:
        if m == 1 or n == 1:
            return 1
        return grid_paths(m - 1, n) + grid_paths(m, n - 1)

    print(f"\n=== Grid Paths ===")
    print(f"Paths in 10x10 grid: {grid_paths(10, 10)}")
    print(f"Paths in 20x20 grid: {grid_paths(20, 20)}")

if __name__ == "__main__":
    main()

Go

package main

import (
	"fmt"
	"sync"
	"time"
)

// Memoized Fibonacci using sync.Map for thread safety
var fibCache sync.Map

func fibonacci(n int) int {
	if n <= 1 {
		return n
	}
	if val, ok := fibCache.Load(n); ok {
		return val.(int)
	}
	result := fibonacci(n-1) + fibonacci(n-2)
	fibCache.Store(n, result)
	return result
}

// Generic memoize function
func Memoize[K comparable, V any](fn func(K) V) func(K) V {
	cache := make(map[K]V)
	var mu sync.Mutex
	return func(key K) V {
		mu.Lock()
		if val, ok := cache[key]; ok {
			mu.Unlock()
			return val
		}
		mu.Unlock()
		result := fn(key)
		mu.Lock()
		cache[key] = result
		mu.Unlock()
		return result
	}
}

// Expensive computation
func expensiveCompute(n int) int {
	time.Sleep(100 * time.Millisecond)
	return n * n
}

func main() {
	// Fibonacci
	fmt.Println("=== Fibonacci (memoized) ===")
	start := time.Now()
	result := fibonacci(40)
	elapsed := time.Since(start)
	fmt.Printf("fibonacci(40) = %d (took %v)\n", result, elapsed)

	// Generic memoize
	fmt.Println("\n=== Expensive Compute (generic memo) ===")
	memoized := Memoize(expensiveCompute)

	start = time.Now()
	r1 := memoized(5)
	t1 := time.Since(start)

	start = time.Now()
	r2 := memoized(5) // cached
	t2 := time.Since(start)

	start = time.Now()
	r3 := memoized(7) // new arg
	t3 := time.Since(start)

	fmt.Printf("compute(5) = %d (%v)\n", r1, t1)
	fmt.Printf("compute(5) = %d (%v) [cached]\n", r2, t2)
	fmt.Printf("compute(7) = %d (%v)\n", r3, t3)

	// Grid paths
	fmt.Println("\n=== Grid Paths ===")
	type gridKey struct{ m, n int }
	gridCache := make(map[gridKey]int)

	var gridPaths func(int, int) int
	gridPaths = func(m, n int) int {
		if m == 1 || n == 1 {
			return 1
		}
		key := gridKey{m, n}
		if val, ok := gridCache[key]; ok {
			return val
		}
		result := gridPaths(m-1, n) + gridPaths(m, n-1)
		gridCache[key] = result
		return result
	}

	fmt.Printf("Paths in 10x10 grid: %d\n", gridPaths(10, 10))
	fmt.Printf("Paths in 20x20 grid: %d\n", gridPaths(20, 20))
}

JavaScript

// Generic memoize utility
function memoize(fn) {
  const cache = new Map();
  const memoized = function (...args) {
    const key = JSON.stringify(args);
    if (cache.has(key)) {
      return cache.get(key);
    }
    const result = fn.apply(this, args);
    cache.set(key, result);
    return result;
  };
  memoized.cache = cache;
  return memoized;
}

// Fibonacci (memoized)
const fibonacci = memoize(function (n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
});

// Expensive computation
function expensiveComputeRaw(x, y) {
  // Simulate expensive work with busy loop
  const start = Date.now();
  while (Date.now() - start < 100) {} // 100ms delay
  return x * y + x + y;
}
const expensiveCompute = memoize(expensiveComputeRaw);

function main() {
  // Fibonacci
  console.log("=== Fibonacci (memoized) ===");
  let start = performance.now();
  const fib40 = fibonacci(40);
  let elapsed = performance.now() - start;
  console.log(`fibonacci(40) = ${fib40} (took ${elapsed.toFixed(2)}ms)`);
  console.log(`Cache size: ${fibonacci.cache.size}`);

  // Expensive compute
  console.log("\n=== Expensive Compute (memoized) ===");
  start = performance.now();
  const r1 = expensiveCompute(5, 10);
  const t1 = performance.now() - start;

  start = performance.now();
  const r2 = expensiveCompute(5, 10); // cached
  const t2 = performance.now() - start;

  start = performance.now();
  const r3 = expensiveCompute(3, 7); // new args
  const t3 = performance.now() - start;

  console.log(`compute(5,10) = ${r1} (${t1.toFixed(2)}ms)`);
  console.log(`compute(5,10) = ${r2} (${t2.toFixed(2)}ms) [cached]`);
  console.log(`compute(3,7)  = ${r3} (${t3.toFixed(2)}ms)`);

  // Grid paths (memoized recursive)
  console.log("\n=== Grid Paths ===");
  const gridPaths = memoize(function (m, n) {
    if (m === 1 || n === 1) return 1;
    return gridPaths(m - 1, n) + gridPaths(m, n - 1);
  });

  console.log(`Paths in 10x10 grid: ${gridPaths(10, 10)}`);
  console.log(`Paths in 20x20 grid: ${gridPaths(20, 20)}`);
}

main();

Related Patterns

• Proxy — a caching proxy is the OOP equivalent of memoization: the proxy intercepts calls and returns cached results.
• Flyweight — flyweight shares computed representations; memoization caches computed results keyed by input.
• Lazy Evaluation — lazy evaluation defers computation; memoization caches deferred results so they are only computed once.