Array#sort(prop)

Mark S. Miller erights at google.com
Sun Apr 1 18:56:08 PDT 2012


On Sun, Apr 1, 2012 at 3:53 PM, Brendan Eich <brendan at mozilla.org> wrote:

>
> arr.sort((a, b) =>  (a.prop<  b.prop) ?-1 :  (a.prop>  b.prop) ? 1 : 0);
>
>
> and if you weed out NaN to avoid the comparison function returning NaN,
> while taking advantage of the fact that the return value's sign is all that
> matters, not exact {-1, 0, 1} membership, then it's not much worse:
>
>
> arr.sort((a, b) =>  { let t = a.prop - b.prop; return (t !== t) ? 0 : t;
> });
>


Quoting from <http://es5.github.com/#x15.4.4.11>, the requirements on the
comparefn are:

A function *comparefn* is a consistent comparison function for a set of
values *S* if all of the requirements below are met for all values *a*, *b*,
and *c* (possibly the same value) in the set *S*: The notation *a* <CF *b*
 means *comparefn*(*a*,*b*) < 0; *a* =CF *b* means *comparefn*(*a*,*b*) = 0
(of either sign); and*a* >CF *b* means *comparefn*(*a*,*b*) > 0.

Calling *comparefn*(*a*,*b*) always returns the same value *v* when given a
specific pair of values *a*and *b* as its two arguments. Furthermore,
Type<http://es5.github.com/#Type>
(*v*) is Number, and *v* is not NaN. Note that this implies that exactly
one of *a* <CF *b*, *a* =CF *b*, and *a* >CF *b* will be true for a given
pair of *a* and *b*.

Calling *comparefn*(*a*,*b*) does not modify the *this* object.

*a* =CF *a* (reflexivity)

If *a* =CF *b*, then *b* =CF *a* (symmetry)

If *a* =CF *b* and *b* =CF *c*, then *a* =CF *c* (transitivity of =CF)

If *a* <CF *b* and *b* <CF *c*, then *a* <CF *c* (transitivity of <CF)

If *a* >CF *b* and *b* >CF *c*, then *a* >CF *c* (transitivity of >CF)

*NOTE*

 The above conditions are necessary and sufficient to ensure that *comparefn
* divides the set*S* into equivalence classes and that these equivalence
classes are totally ordered.


If sort is called with a comparefn which violates this constraint,
according to normative text

If *comparefn* is not *undefined* and is not a consistent comparison
function for the elements of this
array<http://es5.github.com/#array-element> (see
below), the behaviour of *sort* is implementation-defined.


a conforming implementation may kill the user, lose memory safety, or
launch the nukes.

Since in this note we're not concerned about new syntax but rather the
notion of "implementation-defined", let's rewrite Brendan's two sort
functions in ES5:


function c1(a, b) {
return a < b ? -1 : a > b ? 1 : 0;
}
function c2(a, b) {
var t = a - b;
return t !== t ? 0 : 1;
}

Both of these violate transitivity of =CF

c1(3,NaN);
0
c1(NaN,4);
0
c1(3,4);
-1
c2(3,NaN)
0
c2(NaN,4)
0
c2(3,4)
1


Fortunately, I have not tried passing either of these to sort, and so have
lived to tell the tale.

Let's kill "implementation-defined" rather than our users.


>
>
> I'm assuming you don't need to sort -0<  0 (which evaluates to false in
> JS).
>
> Another observation: this last version is the only one that avoids
> multiple implicit conversions via toString or valueOf of an object operand,
> if one or both of a and b is an object and the first condition (a.prop<
>  b.prop) evaluates to false. This means the only portable form is the last
> version.
>
> Yeah, it's a pain to write every time and people will mess up the NaN
> corner case. A standard built-in would be good. But why use a string
> parameter key instead of just a built-in function?
>
> /be
>
>
> ______________________________**_________________
> es-discuss mailing list
> es-discuss at mozilla.org
> https://mail.mozilla.org/**listinfo/es-discuss<https://mail.mozilla.org/listinfo/es-discuss>
>



-- 
    Cheers,
    --MarkM
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20120401/97819743/attachment.html>


More information about the es-discuss mailing list