Challenge 14: Implement a General Memoization Function (memo())

Memoization is a powerful optimization technique used in computer science, especially for functions that perform expensive computations. This challenge asks you to implement a general memo() utility function that takes any pure function as input and returns a memoized version of it. This memoized function will cache its results, significantly speeding up subsequent calls with the same arguments.

Problem Description

Your task is to implement a memo() function that transforms a given function (func) into a new, memoized function. The memoized function should behave as follows:

1. Initial Call: When the memoized function is called with a specific set of arguments for the first time, it should execute the original func with those arguments.
2. Result Caching: The result returned by func should be stored in an internal cache, associated with a unique "cache key" derived from the arguments used in that call.
3. Subsequent Calls: If the memoized function is called again with the exact same set of arguments, it should not re-execute the original func. Instead, it should retrieve and return the previously cached result.
4. Argument Handling: The memoized function must be able to handle functions that take zero or more arguments.
5. Cache Key Generation: A robust strategy for generating a unique cache key from the input arguments is crucial. For this challenge, assume arguments are primitive types (numbers, strings, booleans, null, undefined) or simple arrays/objects where a consistent string representation (e.g., concatenation or simple serialization) can serve as a unique key.
6. Purity Assumption: The input func is assumed to be a "pure function," meaning it always produces the same output for the same input arguments and has no side effects. Memoization is only effective and correct for pure functions.
7. Error Handling: For simplicity, only successful function computations should be cached. If the original func throws an error, the error should be propagated, and that specific input-output pair should not be cached.

Your memo() function will act as a higher-order function, returning a wrapped version of the original function that incorporates caching logic.

Examples

For the examples below, original_func_call_count is a global counter to demonstrate when the original function is actually executed.

Example 1: Memoizing a Fibonacci function

// The original, expensive Fibonacci function
GLOBAL fib_call_count = 0
FUNCTION original_fib(n):
    fib_call_count = fib_call_count + 1 // Increment counter each time original_fib is truly called
    IF n <= 1:
        RETURN n
    RETURN original_fib(n - 1) + original_fib(n - 2)
END FUNCTION

// Memoize the original_fib function
memoized_fib = memo(original_fib)

// --- First call ---
fib_call_count = 0
Output: "Calling memoized_fib(5)..."
Result: memoized_fib(5) // This will trigger original_fib(5) computation and cache it.
Output: Result: 5
Output: "original_fib was called " + fib_call_count + " times for memoized_fib(5)"
// Expected: fib_call_count for computing fib(5) is typically high (e.g., 15 for a naive recursive fib)

// --- Second call with same arguments ---
fib_call_count = 0 // Reset counter to show no new original calls
Output: "Calling memoized_fib(5) again..."
Result: memoized_fib(5) // This should retrieve from cache without calling original_fib.
Output: Result: 5
Output: "original_fib was called " + fib_call_count + " times for memoized_fib(5)"
// Expected: fib_call_count is 0

// --- Call with different arguments ---
fib_call_count = 0 // Reset counter
Output: "Calling memoized_fib(6)..."
Result: memoized_fib(6) // This will trigger original_fib(6) computation and cache it.
Output: Result: 8
Output: "original_fib was called " + fib_call_count + " times for memoized_fib(6)"
// Expected: fib_call_count for computing fib(6) is high, but independent of fib(5) calls

Explanation: The first call to memoized_fib(5) executes original_fib and stores the result. The second call with 5 directly retrieves the stored result, avoiding re-computation. A call with 6 is a new input, so original_fib is executed again.

Example 2: Memoizing a multi-argument function

GLOBAL add_call_count = 0
FUNCTION original_add(a, b):
    add_call_count = add_call_count + 1
    RETURN a + b
END FUNCTION

memoized_add = memo(original_add)

// --- First call ---
add_call_count = 0
Output: "Calling memoized_add(2, 3)..."
Result: memoized_add(2, 3)
Output: Result: 5
Output: "original_add was called " + add_call_count + " times"
// Expected: add_call_count is 1

// --- Second call with same arguments ---
add_call_count = 0
Output: "Calling memoized_add(2, 3) again..."
Result: memoized_add(2, 3)
Output: Result: 5
Output: "original_add was called " + add_call_count + " times"
// Expected: add_call_count is 0

// --- Call with different arguments ---
add_call_count = 0
Output: "Calling memoized_add(5, 7)..."
Result: memoized_add(5, 7)
Output: Result: 12
Output: "original_add was called " + add_call_count + " times"
// Expected: add_call_count is 1

// --- Call with arguments in different order (if key generation considers order) ---
// Note: For simple serialization, (2,3) and (3,2) might result in different keys.
// The problem expects a unique key per specific argument set.
add_call_count = 0
Output: "Calling memoized_add(3, 2)..."
Result: memoized_add(3, 2)
Output: Result: 5
Output: "original_add was called " + add_call_count + " times"
// Expected: add_call_count is 1 (as (3,2) is a distinct call from (2,3))

Explanation: The memoization correctly distinguishes between different sets of arguments (e.g., (2,3) vs. (5,7) vs. (3,2)) and caches results separately for each unique input combination.

Constraints

• The input func to memo() is always a pure function.
• The arguments passed to the memoized function will be primitive types (numbers, strings, booleans, null, undefined) or simple arrays/objects where a default string representation (e.g., concatenation or JSON.stringify equivalent) can uniquely identify them for caching purposes.
• The maximum number of unique argument sets (cache entries) is not strictly limited but should be manageable (e.g., consider up to 1000 distinct entries).
• The memoized function must provide a significant performance improvement for subsequent calls with identical arguments (i.e., cache lookup should be much faster than re-executing func).
• No external libraries or frameworks are allowed for the core memo() implementation.

Notes

• Purity is Key: Remember that memoization relies on the assumption that the input function is pure. If a function's output can change for the same inputs (e.g., due to random numbers, global state, or time-dependent factors), memoizing it might lead to incorrect results.
• Cache Key Generation: A simple approach for generating cache keys from arguments is to concatenate their string representations or use a serialization method (like JSON.stringify if available in your chosen language, ensuring a consistent order for object keys). Be mindful of how different argument types (especially objects and arrays) translate into unique keys. For this challenge, you can assume simple enough arguments that a straightforward serialization will produce unique keys.
• this Context: In some languages, functions might rely on their this context. A robust memo() implementation should typically preserve the this context for the wrapped function. For this challenge, you can assume func does not heavily rely on this, or handle it according to common patterns in your chosen language if it's applicable.
• Cache Invalidation: This problem focuses on the core memoization mechanism. Implementing cache invalidation (e.g., clearing the cache, setting a time-to-live) is an advanced topic and is outside the scope of this challenge.
• Design Choice: Consider what data structure is best suited for the cache (e.g., a hash map/dictionary where keys are the generated argument strings and values are the cached results).