If there is nothing to sort (i.e. one item), why call key function at all?

In my practical situation, simplest key() function will lead to recursion in case of such trivial lists.  I can make similar cmp-type function (i.e. mycmp=lambda a, b: cmp(key(a), key(b))) and then wrap this with cmp_to_key.  But that looks silly.

Simple test case:
$ cat a.py
a = [1]

def spam(x):
    raise Exception

a.sort(key=spam)
print(a)
$ python a.py 
Traceback (most recent call last):
  File "a.py", line 6, in <module>
    a.sort(key=spam)
  File "a.py", line 4, in spam
    raise Exception
Exception

The patch is ok for me,

should I add a regression test?

If so, where?  ./Lib/test/test_sort.py?

Yep, add a regression test.

Why does your key function depend on the size of the list? That seems like the root of the problem. Considering calling the key function is observable behavior, I don't think this should be changed. The patch makes behavior list.sort() inconsistent.

FWIW, I don't think this is worth special casing.

> Considering calling the key function is observable behavior, I don't think this should be changed.

+1

On Wed, Apr 29, 2015 at 02:32:34PM +0000, Benjamin Peterson wrote:
> Why does your key function depend on the size of the list?

Because it's a real life.  Here is the code:
https://github.com/skirpichev/omg/blob/gruntz-use-subs/sympy/series/gruntz.py#L337

Algorithm is recursive and computation of MRV set will be finished only
if I add an exceptional case for len(Omega).  Or even more ugly solution
with cmp-style function:
https://github.com/skirpichev/omg/blob/efc70377639f78fc0f246629989056cb80a71923/sympy/series/gruntz.py#L339

> Considering calling the key function is observable behavior, I don't think this
> should be changed. The patch makes behavior list.sort() inconsistent.

Yes, in some sense.

On another hand, it's reasonable to believe that key function will be
called iff we need one.  But if there is nothing to sort at all - why do
sorting, why you want to call key function?  Looks irrational to me.

Last by not least.  Why the return value of the key function *must*
be defined in this case?  Just a hidden, undocumented restriction and
has no practical value.

BTW, why this issue was closed?

On Wed, Apr 29, 2015, at 11:03, Sergey B Kirpichev wrote:
> 
> Sergey B Kirpichev added the comment:
> 
> On Wed, Apr 29, 2015 at 02:32:34PM +0000, Benjamin Peterson wrote:
> > Why does your key function depend on the size of the list?
> 
> Because it's a real life.  Here is the code:
> https://github.com/skirpichev/omg/blob/gruntz-use-subs/sympy/series/gruntz.py#L337
> 
> Algorithm is recursive and computation of MRV set will be finished only
> if I add an exceptional case for len(Omega).  Or even more ugly solution
> with cmp-style function:
> https://github.com/skirpichev/omg/blob/efc70377639f78fc0f246629989056cb80a71923/sympy/series/gruntz.py#L339

So, basically you need a base case for recursion? What's wrong with
explicitly writing that out?

> 
> > Considering calling the key function is observable behavior, I don't think this
> > should be changed. The patch makes behavior list.sort() inconsistent.
> 
> Yes, in some sense.
> 
> On another hand, it's reasonable to believe that key function will be
> called iff we need one.  But if there is nothing to sort at all - why do
> sorting, why you want to call key function?  Looks irrational to me.
> 
> Last by not least.  Why the return value of the key function *must*
> be defined in this case?  Just a hidden, undocumented restriction and
> has no practical value.

It's practical if you have a broken key function and test it with a one
element list.

> 
> BTW, why this issue was closed?

3 of us agreed this doesn't seem like a suitable change.

On Wed, Apr 29, 2015 at 03:25:19PM +0000, Benjamin Peterson wrote:
> So, basically you need a base case for recursion? What's wrong with
> explicitly writing that out?

Because it's complex (and costly).  This is not a trivial test and
I don't see reasons to fix that is not broken.  And it will be difficult
to explain for readers: remember, I need this exceptional case only in
the world with a strange Python's convention (Python try to sort a list
when it doesn't make sense).

Mathematical algorithm is not broken - programming language is.

Here is C:
https://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/msort.c;#l45
Here is Ruby:
https://github.com/ruby/ruby/blob/trunk/array.c#L2454

> It's practical if you have a broken key function and test it with a one
> element list.

It's silly to test key function on a single-element list *only*.

> > BTW, why this issue was closed?
> 
> 3 of us agreed this doesn't seem like a suitable change.

And 1 seems to be ok with patch.  Is this just a question of
number of votes?

At least, please consider this as a documentation issue.  That ...
feature may be obvious for a Python developer, but not for
mathematician (as well as ordinary Python user).

When key function value has no sense at all - it's not clear from
the documentation, that the key function will be called.

I think the documentation is fine:

"""
The key corresponding to each item in the list is calculated once and then used for the entire sorting process.
"""

This corresponds with the standard "decorate-sort-undecorate" approach to handling key functions in sorts. It's a common computer science technique, possibly not as familiar to a mathematician, but regardless, the docs clearly state that the key is calculated for each item.

Your existing code, with a check for Omega having length 1 and omitting the sort in that case, looks entirely reasonable to me. Maybe you could add a comment "Avoid a costly calculation of the key when length is 1, as we know we don't need to sort then" and leave it at that.

On Wed, Apr 29, 2015 at 05:44:22PM +0000, Paul Moore wrote:
> I think the documentation is fine:
> """
> The key corresponding to each item in the list is calculated once and then used for the entire sorting process.
> """

Does any "sorting process" make sense for [1] or []?!  No, it
isn't.  So, it's not clear if this "process" started at all.

This not just mine opinion - most computer languages
implement the quick exit in question (see examples above).

> It's a common computer science technique

Could you provide any language that avoid this optimization?

Here is Perl 5:
http://perl5.git.perl.org/perl.git/blob/HEAD:/pp_sort.c#l367

(third example)

> Your existing code, with a check for Omega having length 1 and omitting
> the sort in that case, looks entirely reasonable to me.

(Well, then I should look for other languages, if Python devs
insist in doing useless work...)

> Maybe you could add a comment "Avoid a costly calculation of the
> key when length is 1, as we know we don't need to sort then"

I sure, for most people - the idea of sorting list with one
element will look crazy.  There is no room for any "costly
calculations".  (Common sense, nothing more.)  So, such comment
will add more questions...

On 29 April 2015 at 19:42, Sergey B Kirpichev <report@bugs.python.org> wrote:
>> It's a common computer science technique
>
> Could you provide any language that avoid this optimization?
>
> Here is Perl 5:
> http://perl5.git.perl.org/perl.git/blob/HEAD:/pp_sort.c#l367
>
> (third example)

But that's a sort without a key. In Perl you do a key sort via:

@sorted = map  { $_->[0] }
          sort { $a->[1] <=> $b->[1] } # use numeric comparison
          map  { [$_, length($_)] }    # calculate the length of the string
               @unsorted;

(From http://en.wikipedia.org/wiki/Schwartzian_transform). That
computes the keys first, and would compute the key for a list of
length 1, just like Python does. It's just that Python bundles that
whole construct into the "key=" argument.

But it's your choice - if this is a big enough deal to put you off
Python, I guess no-one will be able to stop you. The fact of the
matter is that what Python does is documented behaviour, and the
benefit (small) isn't worth the cost of making a change (which would
only be in Python 3.5 and later anyway, as it's a backward
incompatible change, not a bug fix).

On Wed, Apr 29, 2015, at 13:25, Sergey B Kirpichev wrote:
> 
> Sergey B Kirpichev added the comment:
> 
> On Wed, Apr 29, 2015 at 03:25:19PM +0000, Benjamin Peterson wrote:
> > So, basically you need a base case for recursion? What's wrong with
> > explicitly writing that out?
> 
> Because it's complex (and costly).  This is not a trivial test and
> I don't see reasons to fix that is not broken.  And it will be difficult
> to explain for readers: remember, I need this exceptional case only in
> the world with a strange Python's convention (Python try to sort a list
> when it doesn't make sense).
> 
> Mathematical algorithm is not broken - programming language is.
> 
> Here is C:
> https://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/msort.c;#l45
> Here is Ruby:
> https://github.com/ruby/ruby/blob/trunk/array.c#L2454

I don't understand the analogy, since neither of these two have key
functions.

> 
> > It's practical if you have a broken key function and test it with a one
> > element list.
> 
> It's silly to test key function on a single-element list *only*.
> 
> > > BTW, why this issue was closed?
> > 
> > 3 of us agreed this doesn't seem like a suitable change.
> 
> And 1 seems to be ok with patch.  Is this just a question of
> number of votes?

I should also clarify that Raymond and Mark and responsible for
maintaining most of the algorithmic/data structure code in Python.

> 
> At least, please consider this as a documentation issue.  That ...
> feature may be obvious for a Python developer, but not for
> mathematician (as well as ordinary Python user).

This is probably impossible to prove either way.

On Wed, Apr 29, 2015 at 06:51:21PM +0000, Paul Moore wrote:
> But that's a sort without a key.

Why it does matter?  It have quick exit.  For same reasons - Python could...

> In Perl you do a key sort via:

That's just your implementation.  But we could add here a
quick exit as well.

> The fact of the matter is that what Python does is documented behaviour

No.  Unless you absolutely sure - all readers think that "sorting
process" starts even for trivial lists.  No reasons to believe in that
nonsense - as you could see from sorting implementations in other languages.

> benefit (small) isn't worth the cost of making a change (which would
> only be in Python 3.5 and later anyway

It's easy for users (i.e. me) to backport this feature (i.e. make wrapper for
sorted()).  Benefit is small, I admit, but why not remove unnecessary
restrictions from the language?  I hope, I did my best to explain why.

> I should also clarify that Raymond and Mark and responsible for
maintaining most of the algorithmic/data structure code in Python.

Well, Raymond at least.  I plead not guilty; I think you're confusing me with someone else. :-)

But for this issue, this mathematician prefers the simple invariant that the key function is called exactly once per list item. If your key function doesn't work for one of those items for some reason, that sounds like a problem with the key function rather than a reason to change the sorting implementation.