Array#sort(prop)

Mark S. Miller erights at google.com
Sun Apr 1 19:03:30 PDT 2012


On Sun, Apr 1, 2012 at 6:56 PM, Mark S. Miller <erights at google.com> wrote:

>
>
> 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;
>
>
Oops, typo. The "1" immediately above should be "t". But this doesn't
affect the point.


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



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


More information about the es-discuss mailing list