Nothing exotic — a closure over one dictionary. Read what @memoize actually does to the name it decorates.
def memoize(function):
cache = {} # lives as long as the wrapper does
def wrapper(*args):
if args not in cache:
cache[args] = function(*args)
return cache[args]
return wrapper
@memoize
def slow(n): ...
# is exactly this:
slow = memoize(slow)
slow.__name__ # -> 'wrapper', unless you do something about it
- The cache is a closure variable, which is what makes it per-function
cache is created once each time memoize runs, and the wrapper it returns keeps a reference to that one dictionary. Decorate two functions and you get two calls to memoize, two dictionaries, no interference. Move the dictionary out to module level and every decorated function in the program shares one — which works perfectly until two of them are handed the same argument.
- args is already a tuple, and tuples are hashable
*args collects the positional arguments into a tuple, which can be a dictionary key as long as everything inside it can. That is the whole key-building step — no str(), no join, no clever hashing. And the moment someone passes a list, the TypeError that comes out is telling the truth: this call genuinely cannot be cached.
- @decorator is assignment, so the name is now the wrapper
After decoration the original function is only reachable through the closure; the module-level name points at wrapper. That is why functools.wraps exists — it copies __name__, __doc__, __module__ and __wrapped__ across, so tracebacks, help(), logging and every tool that reads those attributes keep working. Skipping it does not break the code, it breaks everything that has to debug the code.
memoize takes a function and returns a new one. Everything the new function needs to remember lives in a variable created before it — that is the closure doing the work.
Define cache = {} inside memoize, then define wrapper(*args, **kwargs) inside it too, and return wrapper. The key has to include the keyword arguments, and a dict is not hashable — so turn them into something that is.
key = (args, tuple(sorted(kwargs.items()))) — sorted so that f(a=1, b=2) and f(b=2, a=1) produce the same key. Check `if key not in cache` rather than using .get, so that a cached value of None is still a hit. And decorate wrapper with @functools.wraps(function).
import functools def memoize(function): cache = {} @functools.____(function) def wrapper(*args, **kwargs): key = (args, tuple(____(kwargs.items()))) if key ____ cache: cache[key] = function(*args, **kwargs) return cache[____] return ____
import functools
def memoize(function):
cache = {}
@functools.wraps(function)
def wrapper(*args, **kwargs):
key = (args, tuple(sorted(kwargs.items())))
if key not in cache:
# Assigning only after the call returns is what keeps a
# raised exception out of the cache.
cache[key] = function(*args, **kwargs)
return cache[key]
return wrapper
cached = cache.get(key) followed by `if cached is None` re-runs the function every single time it legitimately returns None — a cache that silently stops caching for the one value people use to mean 'nothing found', which is exactly the lookup worth caching. Membership asks the question you actually mean: have I seen this key, whatever the answer was.
Keyword arguments arrive in the order they were written, so f(a=1, b=2) and f(b=2, a=1) are the same call with two different key tuples — the cache would hold both and the hit rate would quietly depend on how people type. Sorting normalises them. It also means the key is built from something comparable, which is a fair assumption for keyword names and not for arbitrary values.
This dictionary grows for the lifetime of the process, holding a reference to every argument and every result it has ever seen. On a function called with a bounded set of arguments that is exactly right. On one called with user input it is an unbounded memory leak with a friendly name — which is why the real implementation takes a maximum size and evicts.
In real code, use functools.lru_cache (or functools.cache, which is lru_cache with no limit) — it is written in C, it bounds the size, it gives you .cache_info() and .cache_clear(), and it makes the same decisions this exercise does about keys. Do not memoize anything whose answer can change: a function that reads a file, a clock, a database or a random number is not a candidate, and neither is one whose result the caller then mutates — every caller would be handed the same object. Caching is a promise that the same input always means the same output, and it is your job to know whether that is true.
- Add a maxsize that evicts the oldest entry when the cache is full, and work out what 'oldest' should mean — least recently added, or least recently used?
- Expose the cache for inspection — wrapper.cache_clear() and a hit/miss count — and compare what you built with functools.lru_cache’s cache_info().
- Handle unhashable arguments by falling back to calling through uncached, then decide whether that is a kindness or a way to hide a performance bug.