Re: table.sort gives wrong result on partially ordered set

[Andrew Gierth <andrew@...>]

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