Memoize a curried function

Question

const f = (arg1) => (arg2) => { /* returns something */ }

Is it possible to memoize f with regard to the 2 arguments, namely:

f(1)(2);
f(1)(3); // Cache not hit
f(4)(2); // Cache not hit
f(1)(2); // Cache hit

Answer 1

You could take a Map as cache and take nested maps for all following arguments.

This cache works for arbitrary count of arguments and reuses the values from the former calls.

It works by taking a curried function and an optional Map. If the map is not supplied, a new map is created which serves as base cache for all other calls of the returned closure or the final result.

The inner function takes a single argument and checks if this value is in the map.

• If not, call the curried function and check the returned value

  • if function, create a new closure over the function and a new map,

  • if no function take the result,

  as value for a new element of the map.

• Finally return the value from the map.

const cached = (fn, map = new Map()) => arg => {
    const inCache = map.has(arg);
    const hint = inCache ? 'in cache' : 'not in cache';

    console.log(arg, hint);

    if (!inCache) {
        const value = fn(arg);
        const result = typeof value === 'function' ? cached(value, new Map()) : value;

        map.set(arg, result);
    }

    return map.get(arg);
};

const f = a => b => c => a * b * c; // the original curried function
const g = cached(f); // its cached variant

console.log(g(1)(2)(5)); // not not not 10
console.log(g(1)(3)(4)); //  in not not 12
console.log(g(4)(2)(3)); // not not not 24
console.log(g(1)(2)(6)); //  in  in not 12
console.log(g(4)(2)(3)); //  in  in  in 24

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

Interesting question — you could have independent caches for each function. The cache on the outside function will hold functions. Each inside function could get its own independent cache. So calling f(10)(1) followed by f(10)(2) would result in calling a cached version of the inside function. Calling f(10)(1) again would hit both caches:

function getCachedF() {
  // outer cache holds functions keyed to argument
  let outer_memo = {}  
                
  const f = (arg1) => {
    if (!outer_memo.hasOwnProperty(arg1)) {
      // Create inner function on outer cache
      // each inner function needs its own cache
      // because it will return different values
      // given different outer function calls
      let inner_memo = {}                  
      console.log("outer cache miss")
      
      outer_memo[arg1] = (arg2) => {
        // just a normal memoized function
        // cache is simple key:value pair
        if (!inner_memo.hasOwnProperty(arg2)) {
          console.log("inner cache miss")
          inner_memo[arg2] = arg1 + arg2
        }
        return inner_memo[arg2]
      }
    }
    return outer_memo[arg1]
  }
  return f
}

let f = getCachedF()
// both caches miss
console.log("3+5", f(3)(5))

// cached result
console.log("3+5", f(3)(5))

// only inside cache hit
console.log("3+8", f(3)(8))

// inside cache only hits if both args are the same
console.log("10+8", f(10)(8))

Another alternative would be to have single cache with keys that are a combination of both arguments, but then the inner function would always have to be called.

Answer 3

This probably isn't the canonical memoization function.

A function that needs to cache its result is given a cache function that is used to store and retrieve previous results:

const sum = memo(cache => a => b => cache(`${a}+${b}`, () => a + b));
//               ^^^^^                    ^^^^^^^^^^^  ^^^^^^^^^^^
//               A                        B            C

• A — The cache function is provided by the memo function.
  (A memoized function can opt-out from caching some results if necessary.)

• B — A unique key for the result. (e.g. cache['1+2'] = 3)

• C — A thunk that returns the result.
  (So we can check if we have it already before computing it.)

This supports both curried and non-curried functions but also functions that return a function as a value.

The memo function can be implemented as follow:

const memo = fn => {
  const ns = Symbol();
  const cache = (key, thunk) => cache[ns][key] ??= thunk();
  cache[ns] = {};
  return fn(cache);
};

I quite like the logical nullish assignment operator for managing the cache:

a ??= answer()

The expression on the right is evaluated and assigned to a if and only if a is not already defined. Then it returns the value of a:

const answer = () => (console.log('returning the answer'), 42);

let a;

a ??= answer();
//=> LOG: returning the answer
//=> 42

a ??= answer();
//=> 42

a ??= 40;
//=> 42

I've used a symbol to hide the actual cache set on the cache function. A symbol is not returned when enumerating properties of an object:

const foo = {};
const key1 = Symbol();
const key2 = 'bar';

foo[key1] = 42;
foo[key2] = 41;

Object.keys(foo);
//=> ['bar']

Object.entries(foo);
//=> [['bar', 41]]

Demo

// curried memoized function
const sum = memo(cache => a => b =>
  cache(`${a}+${b}`,
    () => (console.log(`computing ${a}+${b}…`), a+b)));
  
console.log(sum(1)(2));
console.log(sum(1)(2));
console.log(sum(1)(2));

// non-curried memoized function
const mul = memo(cache => (a, b) =>
  cache(`${a}*${b}`,
    () => (console.log(`computing ${a}*${b}…`), a*b)));
  
console.log(mul(2, 3));
console.log(mul(2, 3));
console.log(mul(2, 3));

// function-returning function
const deferred_sum = memo(cache => a => b =>
  cache(`${a}+${b}`,
    () => (console.log(`defer computing ${a}+${b}…`), () => a+b)));
    
console.log(deferred_sum(1)(2)());
console.log(deferred_sum(1)(2)());
console.log(deferred_sum(1)(2)());

<script>
const memo = fn => {
  const ns = Symbol();
  const cache = (key, thunk) => cache[ns][key] ??= thunk();
  cache[ns] = {};
  return fn(cache);
};
</script>

Answer 4

You can not to pass map to every function. You can do like the next:

const memoize = fn => {
  const cache = {};
  return (...args) => {
    const curriedFn = fn(...args);
    return (...next) => {
      const key = // generate your key
      if (key in cache) return cache[key];
      return (cache[key] = curriedFn(...next));
    }
  }
}