Factorial by Proxy
2024-04-16
A cool snippet I came up with for calculating recursively defined sequences
with built-in memoization.
const factorial = new Proxy([1], {
get(f, n) {
return f[n] ?? (f[n] = this.get(f, n-1) * n);
}
});
Use like this:
factorial[0] // 1
factorial[1] // 1
factorial[2] // 2
factorial[3] // 6
// ...
Explanation:
The proxy allows us to overwrite property access on the array using a
custom
get function,
which we abuse use here to get a seemingly infinite array
containig the entire sequence.
Within it, we can set and get properties of the underlying
array normally: f[k] = 3 and return f[n] work as
expected (the array is available as f). However, for recursion
to work we want to use our new get, so we use this.get(f, k) to
call the new getter recursively, calculating unknown
(undefined) values along the way.
Our get function does the following: if f[n] is already set—i.e.
not undefined (or false)—it is returned instantly. Otherwise, we calculate it
recursively, assign the calculated value to f[n] and return
that value.
Note that we don’t overwrite anything to do with iterators, so
factorial.forEach(...) will only iterate over previously
calculated values. If you want to be fancy, you could make it so that
iterating works, that the underlying array cannot be modified other than
from within the getter and maybe some handling for very large inputs or
inputs < 0.
Judging by the
browser
compatibility for handler.get() listed on mdn,
this should work everywhere in browsers updated since 2016.
Other sequences:
Here’s how it looks for the Fibonacci numbers:
const fibonacci = new Proxy([0,1], {
get(f, n) {
return f[n] ?? (f[n] = this.get(f, n-2) + this.get(f, n-1));
}
});
fibonacci[0] // 1
fibonacci[1] // 1
fibonacci[2] // 2
fibonacci[3] // 5
// ...
Build your own:
const yourSequence = new Proxy([/* array containing the first elements of the sequence */], {
get(f, n) {
return f[n] ?? (f[n] = /* formula to calculate the n-th element,
use `this.get(f, k)` instead of `f[k]` or `yourSequence[k]` */);
}
});