Why Higher Order Function Is Only Called Once-CodePudding

I'm struggling to understand why memoize in this example appears to only be called once. Looking at the code, I would expect "memo prints once" to print with each layer of recursion. However, it is only printed once.

const memoize = fn => {
  console.log("memo prints once")
  const cache = {};
  
  return (...args) => {
      console.log("memo prints witch each iteration")
    const argsString = JSON.stringify(args);
    if (!cache[argsString]) {
      cache[argsString] = fn(...args);
    }
    return cache[argsString];
  }
};

const factorial = memoize(n => {
    if (n === 0) return 1;
    else return (factorial(n - 1) * n);
});



console.log(factorial(3))

Conversely, "memo prints with each iteration" prints with each layer of recursion.

CodePudding user response：

Factorial is actually the function returned by memo, so with each "iteration" it's that returned function being called, which doesn't invoke memo.

CodePudding user response：

The main point is that your logging is in the wrong place to demonstrate how the memoization works. This version should help explain:

const memoize = fn => {
  console.log("memo prints once")
  const cache = {};
  
  return (...args) => {
    // console.log("memo prints witch each iteration")
    const argsString = JSON.stringify(args);
    if (!cache[argsString]) {
      cache[argsString] = fn(...args);
    }
    return cache[argsString];
  }
};

const factorial = memoize(n => {
    console.log(`factorial prints once for the input ${n}`)
    if (n === 0) return 1;
    else return (factorial(n - 1) * n);
});


console .log (factorial (3))
console .log (factorial (5))
console .log (factorial (7))

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

The bit of code that runs once is the creation of the cache and of the new function that uses that cache. Running once per input value is the code inside the anonymous factorial function passed to memo. Running on every call is the code which checks the cache to decide whether to call that factorial function.

If you uncomment the commented line, you will see that it runs for 3, 2, 1, and 0, and then for 5, 4, 3, 2, 1, and 0, even though the last view values are cached, but it will take the branch that doesn't recalculate at those points, which we see by the output of the logging that anonymous function.

CodePudding user response：

recur using a parameter

Another technique is to give your functions an additional parameter and recur using that parameter. This allows for better control as the recursion mechanism can be completely abstracted -

const memorec = f => {
  let memo = new Map
  return function recur(x) {
    if (memo.has(x)) return memo.get(x)
    console.log(`${f.name}(${x})...`)
    const v = f(recur)(x)
    memo.set(x, v)
    return v
  }
}

const fact = recur => n =>
  n == 0
    ? 1
    : n * recur(n - 1)

const fib = recur => n =>
  n < 2
    ? n
    : recur(n - 1)   recur(n - 2)

const factmemo = memorec(fact)
const fibmemo = memorec(fib)

console.log(factmemo(3)) // 6
console.log(factmemo(6)) // 720
console.log(fibmemo(10)) // 55

.as-console-wrapper { min-height: 100%; top: 0; }

Let's talk about the evaluation -

fact(3)...
fact(2)...
fact(1)...
fact(0)...
6
fact(6)...
fact(5)...
fact(4)... // ✅ fact(3) already computed so fact(4) doesn't repeat work
720
fib(10)... // fib(10) computes fib(9) and fib(8)
fib(9)...  // ✅ fib(9) skips memoized fib(8) but computes fib(7)
fib(8)...  // ✅ fib(8) skips memoized fib(7) but computes fib(6)
fib(7)...  // ...
fib(6)...
fib(5)...
fib(4)...
fib(3)...
fib(2)...
fib(1)...
fib(0)...
55

you accidentally discovered the Y combinator

memorec as written above is actually just an expansion and optimization of the Y-combinator. If we strip out all of the memo-specific code, we can see a vanilla implementation of Y as rec below. Recursion is a functional heritage and so maybe it's exciting to feel connected to some of these ingenious techniques discovered by our ancestors -

const rec = f => {
  // ❌ const memo = ...
  return function recur(x) {
    // ❌ if(memo.has(x)) ...
    return f(recur)(x)
  }
}

const fact = recur => n =>
  n == 0
    ? 1
    : n * recur(n - 1)

const fib = recur => n =>
  n < 2
    ? n
    : recur(n - 1)   recur(n - 2)

const factrec = rec(fact)
const fibrec = rec(fib)

console.log(factrec(3))
console.log(factrec(6))
console.log(fibrec(10))

.as-console-wrapper { min-height: 100%; top: 0; }

factrec and fibrec are not optimized with memoization but still they arrive at the correct result -

6
720
55