# table.sort gives wrong result on partially ordered set

11 messages
Open this post in threaded view
|

## table.sort gives wrong result on partially ordered set

 \$ luaLua 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
Open this post in threaded view
|

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

 On Sun, Jan 3, 2021 at 5:48 PM Egor Skriptunoff <[hidden email]> wrote:\$ luaLua 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, 10Garbage in, garbage out. Every sort function I've ever seen has undefined behavior when you introduce NaNs, because a < b and b < a are both false when either is a NaN, so the sort function gets confused.Don't feed NaNs to a sort function, or if you must, define your own comparison function that detects NaNs and treats them specially (e.g by designating them as less than any other value).
Open this post in threaded view
|

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

 In reply to this post by Egor Skriptunoff-2 >>>>> "Egor" == Egor Skriptunoff <[hidden email]> 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.
Open this post in threaded view
|

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

 In reply to this post by Jonathan Goble On Mon, Jan 4, 2021 at 2:09 AM Jonathan Goble wrote:Every sort function I've ever seen has undefined behavior when you introduce NaNsNumbers with NaN is just the simplest example.The same problem will be observed with table.sort() on many other partially ordered sets (using custom sort function).Don't feed NaNs to a sort functionWhy not?The Lua manual claims that table.sort() can work with partially ordered sets.Probably it should not have promised that :-)BTW, why doesn't table.sort() return the table anymore as it was in Lua 5.1?
Open this post in threaded view
|

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

 In reply to this post by Andrew Gierth On Mon, Jan 4, 2021 at 2:19 AM Andrew Gierth wrote: 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.Interesting.But this condition is too complex to be included in the manual.It would be more natural to simply replace "strict partial order" with "strict total order" :-)
Open this post in threaded view
|

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

 In reply to this post by Egor Skriptunoff-2 It was returning new table in Lua 3.2. Lua manual for 4.0 says: setglobal and sort no longer return a value; On 4 Jan 2021, 02:09 +0300, wrote: BTW, why doesn't table.sort() return the table anymore as it was in Lua 5.1?
Open this post in threaded view
|

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

 In reply to this post by Egor Skriptunoff-2 >>>>> "Egor" == Egor Skriptunoff <[hidden email]> writes:  >> 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.  Egor> Interesting.  Egor> But this condition is too complex to be included in the manual.  Egor> It would be more natural to simply replace "strict partial order"  Egor> with "strict total order" :-) "strict weak order" is the correct minimum requirement - a total order is not necessary. (A strict weak order can be considered as a total order over classes of equivalent elements; if you're sorting data where distinguishable values can sort equally, e.g. objects sorted by some property value, this distinction matters.) The documentation is incorrect to state that a strict partial order is sufficient. (I believe I may have pointed this out before.) -- Andrew.
Open this post in threaded view
|

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

 In reply to this post by Egor Skriptunoff-2 > \$ 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 Thanks for the report. -- Roberto
Open this post in threaded view
|

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

 In reply to this post by Andrew Gierth > "strict weak order" is the correct minimum requirement - a total order > is not necessary. (A strict weak order can be considered as a total > order over classes of equivalent elements; if you're sorting data where > distinguishable values can sort equally, e.g. objects sorted by some > property value, this distinction matters.) > > The documentation is incorrect to state that a strict partial order is > sufficient. (I believe I may have pointed this out before.) Thanks for the explanation. (I don't think you did.) -- Roberto