High-order function that memoizes a function

memoize.generic.ts

/**
 * High-order function that memoizes a function, by creating a scope
 * to store the result of each function call, returning the cached
 * result when the same inputs is given.
 *
 * @description
 * Memoization is an optimization technique used primarily to speed up
 * functions by storing the results of expensive function calls, and returning
 * the cached result when the same inputs occur again.
 *
 * Each time a memoized function is called, its parameters are used as keys to index the cache.
 * If the index/key is present, then it can be returned, without executing the entire function.
 * If the index is not cached, then the original function is executed, and the result is
 * stored into the cache.
 *
 * LIMITATIONS
 *
 * As memoize is a higher-order function that accepts a function as its argument
 * and returns a memoized version of the function itself, it's perfect to work with
 * pure functions because of the Referential transparency, but it is not suitable
 * for a function that modifies itself like the Lazy function definition pattern,
 * or for memoizing recursive functions.
 *
 * @warn Do not use with arguments of type `Object` or `Array`.
 * If you need memoize a function with object arguments, then
 * serialize the arguments and use it as key.
 *
 * @param func Function to memoize
 * @returns Memoized function
 */
function memoize<K extends unknown[], R>(func: (...args: K) => R) {
  const cache = new Map<string, R>();

  return function memoized(...args: K): R {
    // For performance reasons, it is not recommended
    // memoizing functions with `Object` or `Array` arguments,
    // but if the body function is really cpu consuming, you can
    // serialize arguments, for example, using `JSON.stringify(args)`
    // or a better serializer. Map() uses identity comparison for keys
    // and, that's why we need to serialize the arguments.
    // const key = JSON.stringify(args);
    const key = `[${args}]`;
    if (cache.has(key)) {
      return cache.get(key);
    }
    const result = func(...args);
    cache.set(key, result);
    return result;
  };
}

memoize.test.js

/**
 * In the code below, there is a memory leak because the `maxPow999` function is redefined
 * and the `cache` object created by the memoized version of `maxPow999` is out of reach.
 * It is no longer accesible, but still not a candidate to be garbage-collected because of
 * the scope created by the `memoizeTest` function.
 */
function memoizeTest(func) {
  const cache = Object.create(null);
  
  return function memoized(...args) {
    // const key = JSON.stringify(args);
    const key = `[${args}]`;
    if (!(key in cache)) cache[key] = func(...args);
    console.log('cache:', cache); // remove this
    return cache[key];
  };
}

// creates the memoized version
var maxPow999 = memoizeTest((x) => {
  const result = x ** 2;
  if (result >= 999) {
    // function is redefined
    maxPow999 = () => result;
  }
  return result;
});

maxPow999(30); // creates the index "[30]" and returns 900
maxPow999(31); // creates the index "[31]" and returns 961

// this call redefines the function, overwriting the memoized version
maxPow999(32); // creates the index "[32]" and returns 1024

// these calls are no longer using the cache, because
// it was redefined as maxPow999 = () => result;
maxPow999(30); // => 1024
maxPow999(15); // => 1024
maxPow999(1);  // => 1024

test.js

/**
 * Return the value of the number 'a' to the power of 'b'
 */
function pow(a, b) {
  return a ** b;
}

// creates the memoized version
const powMemo = memoize(pow);

powMemo(3, 5); // creates the index "[3,5]" and returns 243
powMemo(6, 2); // creates the index "[6,2]" and returns 36

powMemo(3, 5); // return the cached result at "[3,5]"

The usage of JSON.stringify to generalize it is incredibly time-consuming and even the simplest function (like the pow) pays a huge bill. To see it just try to push it a bit maybe testing the Math.pow against his memoized version returned by the memoize in something like a function to compute all narcissistic numbers smaller than 1 billion 🗡️

here a fiddle, .... hint: stay low far below 1E9

Thanks for your feedback @fedeghe
I saw your useful test-case in fiddle.

Maybe using a hash and a custom serializer can help with the performance.
My first thought was using something like this: How to implement a simple hash table.