[Python-ideas] NAN handling in the statistics module

[David Mertz]

OK, let me be more precise.  Obviously if the implementation in a class is:

class Foo:
    def __lt__(self, other):
        return random.random() < 0.5


Then we aren't going to rely on much.

* If comparison of any two items in a list (under __lt__) is deterministic,
is the resulting sort order deterministic? (Pretty sure this is a yes)
* If the pairwise comparisons are deterministic, is sorting idempotent?

This statement is certainly false:

* If two items are equal, and pairwise inequality is deterministic,
exchanging the items does not affect the sorting of other items in the list.

On Sun, Jan 6, 2019 at 11:09 PM Tim Peters <tim.peters at gmail.com> wrote:

> [David Mertz <david.mertz at gmail.com>]
> > Thanks Tim for clarifying.  Is it even the case that sorts are STABLE in
> > the face of non-total orderings under __lt__?  A couple quick examples
> > don't refute that, but what I tried was not very thorough, nor did I
> > think much about TimSort itself.
>
> I'm not clear on what "stable" could mean in the absence of a total
> ordering.  Not only does sort not assume __lt__ is a total ordering,
> it doesn't assume it's transitive, or even deterministic.  We really
> can't assume anything about potentially user-defined functions.
>
> What sort does guarantee is that the result list is some permutation
> of the input list, regardless of how insanely __lt__ may behave.  If
> __lt__ sanely defines a deterministic total order, then "stable" and
> "sorted" are guaranteed too, with their obvious meanings.
>


-- 
Keeping medicines from the bloodstreams of the sick; food
from the bellies of the hungry; books from the hands of the
uneducated; technology from the underdeveloped; and putting
advocates of freedom in prisons.  Intellectual property is
to the 21st century what the slave trade was to the 16th.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20190106/1a36f129/attachment.html>