Does min with lambda always return the first value in python?

Question

In python 2.7.3, using the min function with a lambda, such as min(list, key=f) where f is an lambda function. If it was the case that f(x) was always the same value for all x in list, is it guaranteed that list[0] will be returned?

Thanks

Answer 1

In CPython and PyPy yes. You can see in the source code that the maxval is updated only if the current value is lower than the maxval. Note that internally in CPython same function(min_max) is being used for both min() and mix(), the only difference is the op passed is case of both: for min it's Py_LT and for max it's Py_GT.

maxitem = NULL; /* the result */
maxval = NULL;  /* the value associated with the result */
while (( item = PyIter_Next(it) )) {
    /* get the value from the key function */
    if (keyfunc != NULL) {
        val = PyObject_CallFunctionObjArgs(keyfunc, item, NULL);
        if (val == NULL)
            goto Fail_it_item;
    }
    /* no key function; the value is the item */
    else {
        val = item;
        Py_INCREF(val);
    }

    /* maximum value and item are unset; set them */
    if (maxval == NULL) {
        maxitem = item;
        maxval = val;
    }
    /* maximum value and item are set; update them as necessary */
    else {
        int cmp = PyObject_RichCompareBool(val, maxval, op);
        if (cmp < 0)
            goto Fail_it_item_and_val;
        else if (cmp > 0) {
            Py_DECREF(maxval);
            Py_DECREF(maxitem);
            maxval = val;
            maxitem = item;
        }
        else {
            Py_DECREF(item);
            Py_DECREF(val);
        }
    }
}

---

Same case with PyPy, w_max_item and w_max_val are updated only if the item is the first item from the sequence or if it satisfies the condition as per the function chosen based on the value of implementation_of("max" or "min"):

if not has_item or \
        space.is_true(compare(w_compare_with, w_max_val)):
    has_item = True
    w_max_item = w_item
    w_max_val = w_compare_with

Answer 2

As Ashwini writes in his excellent answer, the implementation of CPython is such that the first result will be returned in the case of a tie. In the Python 3.4 documentation, this behavior is explicitly stated:

If multiple items are minimal, the function returns the first one encountered. This is consistent with other sort-stability preserving tools such as sorted(iterable, key=keyfunc)[0] and heapq.nsmallest(1, iterable, key=keyfunc).

Unfortunately there is no such statement in the Python 2 documentation: min's behavior upon encountering multiple minimal items is undefined as far as the documentation is concerned. This means that the CPython interpreter makes no guarantee that this behavior will be around in future versions, though one might argue that since this functionality is so well-known and established it is a de facto aspect of the language.

If you'd like to be really careful and explicit, you can define a function that is guaranteed to find the first minimum according to the Python 2 API:

def first_min(iterable, **kwargs):
    wrapped = ((x,i) for i,x in enumerate(x))
    if "key" in kwargs:
        keyfun = kwargs["key"]
        kwargs["key"] = lambda x: (keyfun(x[0]), x[1])
    return min(wrapped, **kwargs)[0]

Whether or not you use it over the built-in min depends upon how seriously you regard sticking to the defined and documented behavior.