For an associative operation f
over the elements of array a
, the following relation should hold true: a.reduce(f)
should be equivalent to a.reduceRight(f)
.
Indeed, it does hold true for operations that are both associative and commutative. For example:
const a = [0,1,2,3,4,5,6,7,8,9];
const add = (a, b) => a + b;
console.log(a.reduce(add));
console.log(a.reduceRight(add));
However it doesn't hold true for operations that are associative but not commutative. For example:
const a = [[0,1],[2,3],[4,5],[6,7],[8,9]];
const concat = (a, b) => a.concat(b);
console.log(JSON.stringify(a.reduce(concat)));
console.log(JSON.stringify(a.reduceRight(concat)));
We need to flip the arguments of f
for reduceRight
to make them equivalent:
const a = [[0,1],[2,3],[4,5],[6,7],[8,9]];
const concat = (a, b) => a.concat(b);
const concatRight = (b, a) => a.concat(b);
console.log(JSON.stringify(a.reduce(concat)));
console.log(JSON.stringify(a.reduceRight(concatRight)));
This makes me believe that the native implementation of reduceRight
is wrong.
I believe that the reduceRight
function should be implemented as follows:
var REDUCE_ERROR = "Reduce of empty array with no initial value";
Array.prototype.reduceRight = function (f, acc) {
let { length } = this;
const noAcc = arguments.length < 2;
if (noAcc && length === 0) throw new TypeError(REDUCE_ERROR);
let result = noAcc ? this[--length] : acc;
while (length > 0) result = f(this[--length], result, length, this);
return result;
};
Since result
represents the previous value (right-hand side value), it makes sense to make it the second parameter of the function f
. The current value represents the left-hand side value. Hence, it makes sense to make the current value the first parameter of the function f
. This way, even for non-commutative associative operations, the aforementioned relation holds true.
So, my questions are:
reduceRight
to be implemented the way I did?reduceRight
not implemented the way I did?Doesn't it indeed make more sense for
reduceRight
to be implemented the way I did?
Maybe. However, the JavaScript array iterators do not come from a pure functional programming background.
Why is the native
reduceRight
not implemented the way I did?
Because it's simpler (easier to remember) to have the same parameter order, the accumulator always first.
The primitive operation on arrays is reduce
, which iterates from 0 to n-1 as always. Only in Haskell with its recursively-built lists foldr
makes more sense (has the build
duality, works well lazily on infinite lists…). Notice how the naming is not reduce
+reduceLeft
…
Then reduceRight
does not inverse the fold operation, it just reverses the iteration order. This is also how it is typically explained in documentation and tutorials, for example in The Definitive Guide:
reduceRight()
works just likereduce()
, except that it processes the array from highest.
Also the first implementation of reduce
/reduceRight
(see Bug 363040) in Mozilla's array extras for JS 1.8 followed this approach: It just flipped start with end and negated the step value.
The notes of Dave Herman for the ES4 spec followed this line of thought. It does mention Haskell, but the whole document does not deal with the parameter order of the callback
at all. Maybe the distinct order was lost in Haskells uncommon syntax, or the canonical type names so that both signatures began with (a -> b -> …
. More discussion went into the missing thisObject
parameter.
Some relevant excerpts:
The benefits [of the approach]:
- just like Python => Python community mindshare
- full generality of fold (left)
- but also make the simple case, where the first element is the basis element, simpler
I'd guess most people find the left-to-right version of reduce more
intuitive, since they usually iterate over arrays from left to right. Plus that's what Python does.I think it would also be important to provide a reduceRight as well,
since not every operation is associative, and sometimes people need to go from right to left.
And finally, that is what got into the EcmaScript spec:
Array extras: Spec it the way it is currently supported in FF