Last Comment Bug 363040 - Implement Array.reduce/Array.prototype.reduce
: Implement Array.reduce/Array.prototype.reduce
Status: VERIFIED FIXED
: dev-doc-complete
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Trunk
: All All
: P2 normal (vote)
: mozilla1.9alpha1
Assigned To: Brendan Eich [:brendan]
:
Mentors:
Depends on:
Blocks: js1.8 es5
  Show dependency treegraph
 
Reported: 2006-12-06 23:19 PST by Brendan Eich [:brendan]
Modified: 2008-07-16 06:29 PDT (History)
9 users (show)
bob: in‑testsuite+
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
implementation, v1 (5.96 KB, patch)
2006-12-06 23:22 PST, Brendan Eich [:brendan]
shaver: review+
Details | Diff | Review
Continued fraction non-summing application of reduce (1.11 KB, text/plain)
2006-12-06 23:24 PST, Brendan Eich [:brendan]
no flags Details
Continued fraction non-summing application of reduce (1.11 KB, text/plain)
2006-12-06 23:28 PST, Brendan Eich [:brendan]
no flags Details
implementation v2, with reduceRight and optional initial param (8.11 KB, patch)
2006-12-13 16:31 PST, Brendan Eich [:brendan]
crowderbt: review+
mrbkap: review+
Details | Diff | Review
Continued fraction non-summing application of reduceRight (1.13 KB, text/plain)
2006-12-13 16:32 PST, Brendan Eich [:brendan]
no flags Details
Continued fraction non-summing application of reduceRight (1.15 KB, text/plain)
2007-01-10 11:10 PST, Brendan Eich [:brendan]
no flags Details
Example: flatten the elements of an array and subarrays into a single array (489 bytes, text/plain)
2007-02-10 21:08 PST, Jeff Walden [:Waldo] (remove +bmo to email)
no flags Details

Description Brendan Eich [:brendan] 2006-12-06 23:19:29 PST
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] 2006-12-06 23:22:54 PST
Created attachment 247789 [details] [diff] [review]
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] 2006-12-06 23:24:42 PST
Created attachment 247790 [details]
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] 2006-12-06 23:28:37 PST
Created attachment 247791 [details]
Continued fraction non-summing application of reduce

Confusing comment fixed.

/be
Comment 4 Mike Shaver (:shaver -- probably not reading bugmail closely) 2006-12-07 05:23:23 PST
Comment on attachment 247789 [details] [diff] [review]
implementation, v1

r=shaver
Comment 5 nanto_vi (TOYAMA Nao) 2006-12-12 07:36:30 PST
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] 2006-12-12 09:49:26 PST
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] 2006-12-12 09:52:19 PST
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 2006-12-12 10:24:47 PST
(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] 2006-12-12 11:29:48 PST
(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] 2006-12-13 16:31:41 PST
Created attachment 248586 [details] [diff] [review]
implementation v2, with reduceRight and optional initial param
Comment 11 Brendan Eich [:brendan] 2006-12-13 16:32:30 PST
Created attachment 248587 [details]
Continued fraction non-summing application of reduceRight
Comment 12 Brendan Eich [:brendan] 2006-12-18 16:04:09 PST
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 2006-12-18 16:57:33 PST
Comment on attachment 248586 [details] [diff] [review]
implementation v2, with reduceRight and optional initial param

Looks good to me
Comment 14 Brendan Eich [:brendan] 2007-01-10 11:10:04 PST
Created attachment 251094 [details]
Continued fraction non-summing application of reduceRight
Comment 15 Brendan Eich [:brendan] 2007-01-10 11:13:33 PST
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] (remove +bmo to email) 2007-02-04 02:13:42 PST
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] 2007-02-04 11:18:45 PST
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] (remove +bmo to email) 2007-02-10 21:08:31 PST
Created attachment 254710 [details]
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:] 2007-02-16 21:49:24 PST
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:] 2007-02-19 13:48:19 PST
verified fixed 2007-02-17 1.9.0 windows/mac*/linux
Comment 21 Eric Shepherd [:sheppy] 2007-03-06 08:06:33 PST
What version of JavaScript does this affect?  I need to determine the best place to document this change.
Comment 22 Brendan Eich [:brendan] 2007-04-12 13:58:59 PDT
(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] 2007-10-08 08:32:36 PDT
jresig documented this a while ago.

Note You need to log in before you can comment on or make changes to this bug.