How to convert a Python 2 comparison function to a Python 3 key function?

Question

In Python 2, there is a comparison function.

A comparison function is any callable that accept two arguments, compares them, and returns a negative number for less-than, zero for equality, or a positive number for greater-than.

In Python 3, the comparison function is replaced with a key function.

A key function is a callable that accepts one argument and returns another value to be used as the sort key.

Now, I've a list of tuple[int, int, str] that I want to sort, and the string can be S or E. There are some tie breaker rules that use values from two tuples.

Given a tuple x: int, y: int, z: str, the rules are as follows:

1. If x are equal, and both z = S, larger y comes first.
2. If x are equal, and both z = E, smaller y comes first.
3. If x are equal, and one z = E another z = S, S record comes first.

A Python 2 style implementation is as follows:

def _cmp(coord1: tuple[int, int, str], coord2: tuple[int, int, str]) -> int:
    x1, y1, type1 = coord1
    x2, y2, type2 = coord2
    if x1 != x2:
        return x1 - x2
    if type1 == type2:
        return y2 - y1 if type1 == "S" else y1 - y2
    return -1 if type1 == "S" else 1

Expected output:

[(0, 3, "S"), (0, 2, "S"), (1, 2, "E"), (2, 3, "E")],
[(3, 3, "S"), (4, 2, "S"), (5, 2, "E"), (5, 3, "E")],
[(6, 2, "S"), (7, 3, "S"), (7, 2, "E"), (8, 3, "E")]

I'm aware that a comparison function can be converted to a key function using functools.cmp_to_key; however, I'm wondering if there's a way to implement it directly as a key function since the docs say:

This function is primarily used as a transition tool for programs being converted from Python 2 which supported the use of comparison functions.

Answer 1

Consider how tuples normally compare: element by element, going to the next element when the current values are equal (sometimes called lexicographic order).

Our required comparison algorithm, rewritten in steps that match that general approach, is:

• First, we want to compare the x values, putting them in ascending order.
• Then we want to compare the z values; we want tuples with an S to come first. This is the opposite of what normally happens, and we can't easily specify reverse order for only part of the key, and we can't negate a string value. However, since only S and E are possible, we can simply map S to 0 and E to 1. Or more simply, S can map to False and E to True, since those are numerically equal to 0 and 1 respectively.
• Finally, if the z values were equal, we want to compare the y values - in normal order if we have a E, and in reverse order (so, negate the numeric values) if we have a S.

So, we create a key that corresponds to that rule:

• The first element is x.
• The second element is our translation of the original z value.
• The third element is the y value, possibly negated depending on z.

In code:

def fancy_key(xyz: tuple[int, int, str]) -> tuple[int, bool, int]:
    x, y, z = xyz
    is_e = z == 'E'
    return (x, is_e, (y if is_e else -y))

Answer 2

Alternately, one can replicate the work that the built-in cmp_to_key does, but hard-wiring the comparison logic from the original cmp function. I don't recommend this, obviously; but it is still in some sense "direct", and it highlights a few important things about Python internals.

The idea is, we create a wrapper class that implements the relational operators <, == etc. via the corresponding magic methods - __lt__, __eq__ etc. By using another tool from functools - the @total_ordering decorator - we only need to implement those two; the rest can be inferred by combining those results.

That could look like, for example:

import functools # since we're still using `total_ordering`

@functools.total_ordering
class fancy_key:
    def __init__(self, xyz):
        self.xyz = xyz
    def __lt__(self, other: fancy_key) -> bool:
        x1, y1, type1 = self.xyz
        x2, y2, type2 = other.xyz
        if x1 != x2:
            return x1 < x2
        if type1 != type2:
            return type1 == "S"
        return y2 < y1 if type1 == "S" else y1 < y2
    def __eq__(self, other: fancy_key) -> bool:
        return self.xyz == other.xyz

Notice that for __lt__ we have rewritten the comparison logic, modelled off the original _cmp - except that we return True for the cases where _cmp would return -1, and False otherwise. For __eq__, of course, we can simplify greatly; just compare the underlying data directly.

Because classes are callable, we can directly use this class as the key for a sort call. Python will use it to create instances of the wrapper for each original tuple (rather than calling a function to create transformed data for each original tuple). The instances compare in the way we want them to (because of the operator overload). Thus, we are done.

The actual cmp_to_key function (thanks to @George for the reference) generalizes this process by creating a new class on the fly, and returning that class. It uses a closure to provide the original mycmp (as it's named in that source code) to the new class, which has a hard-coded implementation of the magic methods - these all just call mycmp and check whether the result was negative, zero or positive. This implementation does not use total_ordering, presumably for efficiency; and also uses __slots__ for efficiency. It also tries to replace this code with a native C implementation, if available.

Answer 3

Since the original version of this was rec'd for deletion as supposedly not actually answering the question due to it... being too long, I guess?, here's a shorter version of the exact same answer that gives less insight but uses fewer words. (Yes, it was too long. It also answered the question. "omg tl;dr" shouldn't be sufficient cause to claim that it didn't.)

The accepted answer uses the entire original tuple as the key, and simply reorders it so that the built-in sort can handle it correctly. It is, in my opinion, the best solution, as even though that's not really a "key" by any meaningful typical definition of a "key" (and it certainly doesn't give the efficiency benefits of a key-based sort) the efficiency of the sort itself is probably as close to the original compare-based sort as you can get it.

Additionally, there is another way to solve the problem of converting the comparison function to a key function, which is the way cmp_to_key solves it (as the OP alluded to). That is to use the key function to instead define a class with a single sort item (here, your tuple) as the sole member variable and define the class's __lt__() built-in (and ideally the other comparison built-ins as well) by having them call the comparison function with self as the first parameter.

To be exceedingly clear about this: that is a second solution to the problem. I don't know that it can be made any clearer that the above approach -- the approach that a Python standard library function itself uses -- does indeed solve the problem stated by the OP. Hopefully the review agrees, I suppose.

How and why does that work, and what are the pros and cons of going about it that way instead? Well, I'd explain, but it has unfortunately been deemed outside of the scope of the question to do so by the deletion review, which suggested asking a separate question to get more detail on how it works. As the OP seems more than capable and can likely figure it out themselves, I'll just leave that part out and make the reviewers happy. I've learned my lesson from how they treated the version of the question the OP posted yesterday.

(Ironically, lengthening the answer by including a code example that would basically be just a class definition and would only be useful to those that don't know how to define one already would seem to be unobjectionable, perhaps even preferable, to reviewers -- for those that need that, I'm sure there are already asked-and-answered questions elsewhere on SO regarding how to define and instantiate a class.)

Now that it is hopefully clear that an additional answer to the question was provided, I'll also note firstly that I still think the currently accepted answer is better for this specific case, and secondly that the cmp_to_key approach doesn't really create a traditional "key function" by any commonly accepted plain-face meaning of the term, and there likely really isn't any simple way to programmatically construct a "real" key function from a comparison function in the general case as is implied by the portion of the cmp_to_key docs quoted by the OP in the question itself (hopefully noting that it was specifically stated in the question is sufficient indication to reviewers that it is a relevant observation, despite it being seemingly insufficient the first time around).