15.4.4.21 Array.prototype.reduce ( callbackfn [ , initialValue [ , thisArg ] ] )

Brendan Eich brendan at mozilla.com
Sat Mar 21 09:57:44 PDT 2009


On Mar 21, 2009, at 9:01 AM, Allen Wirfs-Brock wrote:

> Adding to David-Sarah's comments, here is how I would expect a call  
> that needs to supply a thisArg to be expressed:
>
> a.reduce(f.bind(thisArg),init)

That's one way; the other way was to use a closure. Dave Herman  
developed the reduce (and reduceRight) specs for ES4 and JS1.8 based  
on my proposals, without thisArg in order to keep the signature short  
and Pythonic. Here's Dave's write-up, I don't think he'll mind me  
sharing it:

SYNOPSIS:

- Haskell and ML both have essentially the same versions of  
"foldl" (i.e., reduce left-to-right) and "foldr" (i.e., reduce right- 
to-left), other than laziness and slight differences in currying.

- Haskell also has "foldl1" and "foldr1", which don't take the "basis  
element" argument, and use the first element of the list instead.

- SRFI 1 has "fold" and "fold-right", which are similar to ML and  
Haskell, except they can take any number of lists, and the function  
argument has to accept one argument for every list. (This is hard to  
give precise types for, though, and it doesn't fit into a single- 
dispatch OO paradigm.)

- SRFI 1 also has what it calls "reduce" and "reduce-right", which are  
optimized special cases of fold and fold-right: they require the basis  
element to be a right identity of the function argument, so they don't  
have to call the function argument in the one-element case (in case  
that function is expensive). This is only applicable when the basis  
element is a right identity, though.

- Python has "reduce" which takes a function, a list, and optionally a  
basis element. If the basis element is provided, it's essentially  
foldl. If the basis element is not provided, it's essentially foldl1.


MY SUGGESTION:

I think we should offer a reduce method similar to Python's except as  
a method on arrays (to be consistent with JS 1.6's map). However,  
because of the JS 1.6 precedent for the signature of map, it's gonna  
be hard to add an optional argument, since it already accepts an  
optional "thisObject". I'm guessing this is because we won't have  
bound methods until ES4, so anything that accepts a callback should  
also accept an optional "this" object to use in the call to the  
callback.

So this would mean reduce takes one callback argument and two optional  
arguments: thisObject and init. Which one should come first? The more  
common one is probably init, but then you separate the callback arg  
from the "thisObject" arg, which is maybe okay. Multiple optional  
arguments are kinda messy this way...

Alternatively, we could just eliminate that extra "thisObject"  
argument, since people can always do something like:

    arr.map(function(x,i,me) { return obj.method(x,i.me) })

to ensure that the desired method gets called with the appropriate  
binding for "this". Then in ES4 they'll be able to do even better with  
bound methods.

This way we could then make the signatures of map and reduce signature  
really simple:

    map(callback)
    reduce(callback[, init])

The benefits:

- 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.

Details attached.

Dave

1.) Haskell [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html#3 
]

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z [x1, x2, ..., xn] =
  f (f ... (f (f z x1) x2) ...) xn

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [x1, x2, ..., xn] =
  f x1 (f x2 ... (f xn z) ...)

foldl1 :: (a -> a -> a) -> [a] -> a
foldl1 f (x1:xs) = foldl f x1 xs

foldr1 :: (a -> a -> a) -> [a] -> a
foldr1 f (x1:xs) = foldr f x1 xs


2.) ML [http://www.standardml.org/Basis/list.html#SIG:LIST.foldl:VAL]

foldl : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b
foldl f init [x1, x2, ..., xn] =
  f(xn, ..., f(x2, f(x1, init)) ...)

foldr : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b
foldr f init [x1, x2, ..., xn] =
  f(x1, f(x2, ..., f(xn, init) ...))


3.) SRFI 1 [http://srfi.schemers.org/srfi-1/srfi-1.html#FoldUnfoldMap]

fold : ('a1 * ... * 'ak * 'b -> 'b) * 'b * 'a1 list * ... * 'ak list - 
 > 'b
(fold f init (list x1 x2 ... xn)) =
  (f x1.n x2.n ... xk.n ... (f x1.2 x2.2 ... xk.2 (f x1.1 x2.1 ... xk. 
1 init)) ...)

fold-right : ('a1 * ... * 'ak * 'b -> 'b) * 'b * 'a1 list * ... * 'ak  
list -> 'b
(fold-right f init (list x1 x2 ... xn)) =
  (f x1.1 x2.1 ... xk.1 (f x1.2 x2.2 ... xk.2 ... (f x1.n x2.n ...  
xk.n init) ...))

reduce : ('a * 'a -> 'a) * 'a * 'a list -> 'a
PRECONDITION: (f x ridentity) = x
(reduce f ridentity ()) = ridentity
(reduce f ridentity (list x1 x2 ... xn)) =
  (fold f x1 (list x2 ... xn))

reduce-right : ('a * 'a -> 'a) * 'a * 'a list -> 'a
PRECONDITION: (f x ridentity) = x
(reduce-right f ridentity ()) = ridentity
(reduce-right f ridentity (list x1)) = x1
(reduce-right f ridentity (list x1 x2 ... xn)) =
  (f x1 (reduce-right f ridentity (list x2 ... xn)))


4.) Python [http://docs.python.org/lib/built-in-funcs.html]

reduce(f, ls[, init])

reduce(f, ls) => same as Haskell's foldl1
reduce(f, ls, init) => same as Haskell's foldl

----- END DAVE CITE -----

> It almost makes me wonder if we should drop the thisArg from the  
> standard for the other "array extra" functions and leave it as an  
> implementation extension:
> Pros: It's unnecessary, leaving it out of the standard may wean  
> thisArg usage.

The spec is not mommy; it can't reliably wean anyone off of anything  
already out there in use.

The anti-|this| animus on parade in David-Sarah's message is at war  
with compatibility and convention. It should not sweep all that came  
before aside, by sub-committee fiat. I admit this makes things  
messier, but that's life in Compatibility Kingdom (AKA the Web).


> Cons: Because of the legacy, all implementation are going to  
> implement the thisArg any, so it is better to have a standard  
> specification for it.

Right. This is plausible with something ancient and in decline  
(foo.arguments, e.g.) but for new stuff it's bad for business. We  
should specify what implementations must do to interoperate when using  
recently added methods.


> Of course, all the other "array extras" are specified with a thisArg  
> so consistency argues that reduce and reduceRight should be  
> specified that way too.

I had to remind myself of Dave's analysis/argument, cited in full  
above, to see why we didn't do that.

By breaking symmetry we have made at least one browser-based  
implementation precedent (Rhino also supports reduce and reduceRight)  
with no thisArg for the "fold" methods. At this point I would rather  
we stand on precedent than waver or haver further.

Ed, what do you think? Apologies for forgetting the details.

/be
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20090321/d7c72ca0/attachment-0001.html>


More information about the Es-discuss mailing list