363040 - Implement Array.reduce/Array.prototype.reduce

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P2)

Description

[Brendan Eich [:brendan]]

Not sure why it was left out of the extras added in JS1.6 -- shaver may know.  Patch and test-ish demo next.

/be

Comment 1

[Brendan Eich [:brendan]]

Attachment: implementation, v1

Wondering about whether to support an "initial" optional parameter, as Python's moribund reduce does (if passed, it's used to seed the accumulator as if it were unshifted onto the left end of the sequence).

Comment 2

[Brendan Eich [:brendan]]

Attachment: Continued fraction non-summing application of reduce

Based on a LtU post (with a bug- or typo-fix), which argued that reduce is useful for more than + and * folds.

/be

Comment 3

[Brendan Eich [:brendan]]

Attachment: Continued fraction non-summing application of reduce

Confusing comment fixed.

/be

Comment 4

[Mike Shaver (:shaver emeritus)]

Comment on attachment 247789 [details] [diff] [review]
implementation, v1

r=shaver

Comment 5

[nanto_vi (TOYAMA Nao)]

I think initial value support is important.
  array.unshift(initial);
  array.reduce(func);
modifies array and can't be used with read-only array-like object such as NodeList.
  Array.reduce(nodeList, func, null, initial)
  // or Array.reduce(nodeList, initial, func, null) like Ruby's inject
is easier to read than
  [initial].concat(Array.slice(nodeList, 0)).reduce(func)

BTW, what
  // array = [, 1] can't be used because of bug 260106
  var array = [];
  array[1] = 1;
  array.reduce(function (x, y) { return x + y; });
should return?  With implementation v1, it returns NaN (undefined + 1).  But to match behaviors of other array extra methods which skip holes, it should return 1, the first non-hole value.

Comment 6

[Brendan Eich [:brendan]]

Not to worry, Dave Herman has been helping with the design.  We want initial, which plays hob with the optional |this| parameter for the other extras:

Array.map(arraylike, callback[, thisobj])    // thisobj passed to callback
Array.reduce(arraylike, callback[, initial]) // no thisobj, or else...
Array.reduce(arraylike, callback[, thisobj[, initial]])

The last sucks, because I expect initial to be more commonly supplied than an explicit thisobj for the callback.  Transposing the two doesn't help; it breaks symmetry with the other extras anyway, and separating thisobj from callback goes against their argv adjacency.  So Dave and I are in favor of the Pythonic

Array.reduce(arraylike, callback[, initial])

(which of course is available as an Array.prototype.reduce(callback[, initial]) method too).

After name haggling, we think there should be a reduceRight too, to relieve callers from having to reverse (which mutates).  Comments welcome.

/be

Comment 7

[Brendan Eich [:brendan]]

I should add that the need for the thisobj optional parameter by the other extras is questionable in ES4, as bound methods will be easier to make and extract then. Even now, with all the Ajax libs, closures are used to bind methods to various |this| parameters.  So reduce/reduceRight users can force a |this| binding if they need to.

Hmm, perhaps we should codify Function.bind(callback, thisobj) as a standard? I'll propose it to the ECMA TG1 group.

/be

Comment 8

[Igor Bukanov]

(In reply to comment #7)
> Hmm, perhaps we should codify Function.bind(callback, thisobj) as a standard?
> I'll propose it to the ECMA TG1 group.

That would be nice but slightly inconvenient as one would have to write something like:

getelem = document.getDocumentById.bind(document),

that is, it would be necessary to use "document" twice. So what about something like Object.prototype.boundMethods() with a usage:

getelem = document.boundMethods().getDocumentbyId ? 

Or alternatively something like
getelem = Function.boundMethods(document).getDocumentbyId ? 

 

Comment 9

[Brendan Eich [:brendan]]

(In reply to comment #8)
> (In reply to comment #7)
> > Hmm, perhaps we should codify Function.bind(callback, thisobj) as a standard?
> > I'll propose it to the ECMA TG1 group.
> 
> That would be nice but slightly inconvenient as one would have to write
> something like:
> 
> getelem = document.getDocumentById.bind(document),

Typically the need for bind is with top-level JS functions, not with native methods. Indeed document.getElementById should be a bound method, which means if you extract it, it knows it's bound to document. So this is not a strong use case.

/be

Comment 10

[Brendan Eich [:brendan]]

Attachment: implementation v2, with reduceRight and optional initial param

Comment 11

[Brendan Eich [:brendan]]

Attachment: Continued fraction non-summing application of reduceRight

Comment 12

[Brendan Eich [:brendan]]

Comment on attachment 248586 [details] [diff] [review]
implementation v2, with reduceRight and optional initial param

Gonna go for the crowder/mrbkap one-two in place of shaver, who is busy elsewhere.

/be

Comment 13

[Brian Crowder]

Comment on attachment 248586 [details] [diff] [review]
implementation v2, with reduceRight and optional initial param

Looks good to me

Comment 14

[Brendan Eich [:brendan]]

Attachment: Continued fraction non-summing application of reduceRight

Comment 15

[Brendan Eich [:brendan]]

Ok, this was checked in yesterday by mistake, but it was overdue.  Sheppy please take note of the example attachment, and rationale in comment 6 -- please mail me if you need more details.

/be

Comment 16

[Jeff Walden [:Waldo]]

Possible issue with this: the Prototype library apparently in its most recent version adds a reduce method to Array instances.  (My original source of info was <http://www.xml.com/lpt/a/1689>.)  Its semantics are as follows, and even without having given this bug a thorough reading yet I can say those semantics are nothing like what's here:

Array.prototype.reduce = function()
{
  return this.length > 1 ? this : this[0];
};

Do we care, particularly given the time until our reduce is usable by web developers?

Comment 17

[Brendan Eich [:brendan]]

Prototype still has not learned that <standardclass>.prototype is verboten. But that's ok -- the ES4 (JS1.8-JS2) reduce can be overridden (the one in no namespace on Array.prototype; Array.reduce and the intrinsic::reduce bindings for the static and prototype methods remain).

We don't care how this shakes out. Users of prototype will have to use the static reduce or the intrinsic::reduces if they want the standard one. Odds are they'll just want the one Prototype sets, until ES4 is more commonly implemented.

/be

Comment 18

[Jeff Walden [:Waldo]]

Attachment: Example: flatten the elements of an array and subarrays into a single array

Here's another use for Array.prototype.reduce: convert an array into a "flat" array.  See the attachment for examples.

Comment 19

[Bob Clary [:bc] (inactive)]

Checking in ./extensions/regress-363040-01.js;
/cvsroot/mozilla/js/tests/js1_7/extensions/regress-363040-01.js,v  <--  regress-363040-01.js
initial revision: 1.1
done
RCS file: /cvsroot/mozilla/js/tests/js1_7/extensions/regress-363040-02.js,v
done
Checking in ./extensions/regress-363040-02.js;
/cvsroot/mozilla/js/tests/js1_7/extensions/regress-363040-02.js,v  <--  regress-363040-02.js
initial revision: 1.1
done
RCS file: /cvsroot/mozilla/js/tests/js1_7/regress/regress-363040-01.js,v
done
Checking in ./regress/regress-363040-01.js;
/cvsroot/mozilla/js/tests/js1_7/regress/regress-363040-01.js,v  <--  regress-363040-01.js
initial revision: 1.1
done
RCS file: /cvsroot/mozilla/js/tests/js1_7/regress/regress-363040-02.js,v
done
Checking in ./regress/regress-363040-02.js;
/cvsroot/mozilla/js/tests/js1_7/regress/regress-363040-02.js,v  <--  regress-363040-02.js
initial revision: 1.1
done

Comment 20

[Bob Clary [:bc] (inactive)]

verified fixed 2007-02-17 1.9.0 windows/mac*/linux

Comment 21

[Eric Shepherd [:sheppy]]

What version of JavaScript does this affect?  I need to determine the best place to document this change.

Comment 22

[Brendan Eich [:brendan]]

(In reply to comment #21)
> What version of JavaScript does this affect?  I need to determine the best
> place to document this change.

JS1.8, to be defined in full... Firefox 3.

/be

Comment 23

[Eric Shepherd [:sheppy]]

jresig documented this a while ago.