lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


Comparing NaN with "<=" or ">=" is not significant at all, these operators are not suitable even for a partial order.

Sorting however requires a partial order. The sort function by default assumes that "<=" and ">=" are the logical negation of ">" and "<".

A total order is not always required for sorting (but it is needed if you want a "stable" sort). For a total order, you also need a semantic for "==" (which must be the logical inverse of "!="), something that is also false by default with NaN.

I wonder if the default sort() function should not already have a builtin test for NaN, and a *boolean* parameter saying how we want to sort them (lower than everything by default when it is nil/false, or higher than everything otherwise).

This way no need to specify a custom compare function, it would be implemented natively, may be faster than when using a custom compare function in Lua, and calls to the custom compare functions could be avoided when one of the two values is NaN (and unless you want for a "stable" total order, it can be avoided when both values are NaN; this could optimize for performance in many cases where NaN are very frequent, notably with data selected from database tables with outer joins, i.e. for relations with 0-1 or 0-N cardinality, something that occurs extremely frequently in many apps).

Le lun. 4 janv. 2021 à 00:19, Andrew Gierth <andrew@tao11.riddles.org.uk> a écrit :
>>>>> "Egor" == Egor Skriptunoff <egor.skriptunoff@gmail.com> writes:

 > $ lua
 > Lua 5.4.2  Copyright (C) 1994-2020 Lua.org, PUC-Rio
 >> nan = 0/0
 >> t = {nan, nan, 20, 10}
 >> table.sort(t)
 >> print(table.concat(t, ", "))
 > -nan, 20, -nan, 10

That's fairly standard for sort functions; the comparison function must
be at least a strict weak ordering if not a total order, a partial order
isn't sufficient, and if the comparison function isn't adequate then the
result may be garbage (or for some sort functions in some languages, it
may even crash).

The standard NaN semantics where all comparisons against NaN are false
means that sorting lists containing NaN is impossible; but testing for
this case would complicate the sort function.

The specific requirement that is violated is that the < relation used
for the sort must be a strict partial order with this additional
requirement: the relation (not (a < b or b < a)) must be an equivalence
relation. For the conventional < operator in the presence of NaN, this
is not the case: define (a EQ b) as (not (a < b or b < a)), and we find
that (a EQ nan) and (nan EQ b) is always true, but (a EQ b) may be false.

--
Andrew.