This partially answers the question how to memoize all kind of functions in a purely functional manner. The solution is completely different from your imperative one and the code is not production ready but just a proof of concept. Please note that I am also a rookie on this subject.
The answer is partial, because I am only going to show a memoize function whose domain (arguments) are integers. A more advanced polymorphic memoization function can handle all kinds of argument types and also recursive functions.
The basic idea is to have a function that operates on an infinite list of integers. A list can be only infinite if it is non-strictly evaluated, that is to say only evaluated when needed and only just enough. We will later see that non-strictness is not enough for memoization, we need proper lazy evaluation.
In the first example I am going to use explicit thunks (e.g. nullary functions of shape () => "do something" for the sake of simplicity:
// INFINITE LIST
// we only mimick such a type
const iterate = f => {
const go = x =>
[x, () => go(f(x))];
return go;
};
// Functor
const map = f => {
const go = ([x, thunk]) =>
[log(f(x)), () => go(thunk())];
return go;
};
// element lookup
const lookup = ([x, thunk]) => i =>
i === 0
? x
: lookup(thunk()) (i - 1);
// memoization
const memoize = f =>
lookup(
map(f)
(iterate(x => x + 1) (0)));
// auxiliary function
const log = x => (console.log(x), x);
const fib = n => {
return n > 1
? fib(n - 1) + fib(n - 2)
: n;
}
// MAIN
const foo = memoize(fib);
console.log("yields:", foo(6)); // logs 1, 1, 2, 3, 5, 8
console.log("yields:", foo(6)); // logs 1, 1, 2, 3, 5, 8
This works with an infinite sequence of fibonacci numbers and yields the expected result, but there is still no memoization. Right now it is just a cumbersome way to calculate places from the fibunacci sequence.
While this algorithm is non-strict, we need proper lazy evaluation as already mentioned. Lazy evaluation means non-strict evaluation with sharing of once computed thunks. We can mimic lazy evaluation with the native Proxy type in Javascript. Please note that the explicit thunks from the above example are now replaced with implicit ones, i.e. you don't need to call (thunk()) but just use them as if they were ordinary values. Here is a working sketch:
const NULL = "null";
const THUNK = "thunk";
const thunk = thunk =>
new Proxy(thunk, new ThunkProxy());
class ThunkProxy {
constructor() {
this.memo = NULL;
}
apply(g, that, args) {
if (this.memo === NULL) {
this.memo = g();
while (this.memo && this.memo[THUNK] === true)
this.memo = this.memo.valueOf();
}
return this.memo(...args);
}
get(g, k) {
if (k === THUNK)
return true;
else if (this.memo === NULL) {
this.memo = g();
while (this.memo && this.memo[THUNK] === true)
this.memo = this.memo.valueOf();
}
if (k === "valueOf")
return () => this.memo
else if (k === "toString")
return () => this.memo.toString();
else if (k === Symbol.toStringTag)
return Object.prototype.toString.call(this.memo).slice(8, -1);
while (this.memo[k] && this.memo[k] [THUNK] === true)
this.memo[k] = this.memo[k].valueOf();
if (typeof this.memo[k] === "function")
return this.memo[k].bind(this.memo);
else return this.memo[k];
}
has(g, k) {
if (k === THUNK)
return true;
else if (this.memo === NULL) {
this.memo = g();
while (this.memo && this.memo[THUNK] === true)
this.memo = this.memo.valueOf();
}
return k in this.memo;
}
}
const iterate = f => {
const go = x =>
[x, thunk(() => go(f(x)))];
return go;
};
const lookup = ([head, tail]) => i =>
i === 0
? head
: lookup(tail) (i - 1);
const map = f => {
const go = ([head, tail]) =>
[log(f(head)), thunk(() => go(tail))];
return go;
};
const memoize = f =>
lookup(
map(f)
(iterate(x => x + 1) (0)));
const log = x => (console.log(x), x);
const fib = n => {
return n > 1
? fib(n - 1) + fib(n - 2)
: n;
}
const foo = memoize(fib);
console.log("yields:", foo(6)); // logs 0, 1, 1, 2, 3, 5, 8, "yields: 8"
console.log("yields:", foo(6)); // logs "yields: 8"
console.log("yields:", foo(10)); // logs 13, 21, 34, 55, "yields: 55"
Finally we've achieved the desired memoization effect, but the way I mimic lazy evaluation in Javascript is impure as well - I am just cheating. In a purely functional language like Haskell, however, lazy evaluation is an implementation detail of the language and thus not part of the syntax you actually use. This way the language itself remains pure.
Please note that fib is a recursive function and memoize does not handle the recursive steps but only intermediate and the final result.
