[Python-ideas] Make max() stable

[Steven D'Aprano]

On Fri, Jan 17, 2014 at 03:45:14PM +0200, אלעזר wrote:
> Hi all,
> 
> Given several objects with the same key, max() returns the first one:
> 
>     >>> key = lambda x: 0
>     >>> max(1, 2, key=key)
>     1

A more natural example showing that both min and max return the *first* 
of equal elements is:

py> values = (1, 2, 1.0, 2.0)
py> min(values)
1
py> max(values)
2


> This means it is not stable, at least according to the definition in
> "Elements of Programming" by Alexander Stepanov and Paul McJones (pg. 52):
> 
> "Informally, an algorithm is stable if it respects the original order of
> equivalent objects.

Stability is normally only of concern with sorting algorithms. I'm not 
sure whether Stepanov and McJones' definition is widely accepted, or 
important. There are clear reasons for desiring sorting to be stable. 
Are there any clear reasons to desire max to be stable in this sense?

(There is another, unrelated, meaning of stability with regard to 
numeric algorithms, but it has nothing to do with the order of objects.)

Note that stability in this sense only is meaningful when your values 
are objects that you care about their identity as well as value.


> So if we think of minimum and maximum as selecting,
> respectively, the smallest and the second smallest from a list of two
> arguments, stability requires that when called with equivalent elements,
> minimum should return the first and maximum should return the second."
> 
> A page later, In a side note, the authors mention that "STL incorrectly
> requires that `max(a, b)` return `a` when `a` and `b` are equivalent." (As
> a reminder, Stepanov is the chief designer of the STL).
>
> So, I know this is not a big issue, to say the least, but is there any
> reason *not* to return the last argument? Are we trying to be compatible
> with STL somehow?

No, I expect that the result is an accident of implementation. 
Specifically, the min and max algorithms probably look something like 
this:

min = first item
for each item:
    if item < min: min = item

max = first item
for each item:
    if item > max: max = item


> I admit I don't know of any real use case where this really matters, but I
> can point out that
> 
>    >>> ab = (1, 2)
>    >>> (min(ab, key=key), max(ab, key=key))
>    (1, 1)
> 
> is visibly less sensible than (1, 2).

Using your weird key function here is going to give bizarre results. 
Consider:

ab = (2, 1)
min(ab, key=key), max(ab, key=key)

Current behaviour is to return (2, 2). I don't think that returning 2 
for the minimum and 1 for the maximum is more sensible, but that's 
because the key function is not sensible, not because of any objection 
to making max stable in this sense.



-- 
Steven