proposal: cmp: add Reverse function

[adamroyjones]

Proposal Details

I propose a small, trivial addition to the cmp package. (Ed.: This now incorporates an observation from @itchyny here.)

// Reverse takes a comparison function and returns the reverse of it.
func Reverse[T any](fn func(x, y T) int) func(x, y T) int {
    return func(x, y T) int { return fn(y, x) }
}

As an example,

package main

import (
    "cmp"
    "fmt"
    "slices"
)

func main() {
    fn := func(x, y int) int { return cmp.Compare(x, y) }
    xs := []int{2, 3, 1}
    fmt.Printf("%v\n", xs)

    slices.SortFunc(xs, fn)
    fmt.Printf("%v\n", xs)

    slices.SortFunc(xs, Reverse(fn))
    fmt.Printf("%v\n", xs)
}

func Reverse[T any](fn func(x, y T) int) func(x, y T) int {
    return func(x, y T) int { return fn(y, x) }
}

prints out

[2 3 1]
[1 2 3]
[3 2 1]

I've found that it's frequently useful to want to assert that something is ordered ascending or descending; writing such a thing down is trivial but feels rather clumsy.

I'm happy to contribute a pull request with tests if this is considered a good idea.

[ianlancetaylor]

Just want to note that Rust has this; https://doc.rust-lang.org/std/cmp/struct.Reverse.html .

[fzipp]

The 'sort' package already has a Reverse function for sort.Interface, so a Reverse function for the 'cmp' package would fit well in analogy. https://pkg.go.dev/sort#Reverse

[itchyny]

I don't think T needs to be Ordered. This function can reverse any comparator on two values of any type. https://go.dev/play/p/1TNHMQ7Cnoe

[adamroyjones]

@itchyny: You're right. I'll update the proposal.

[randall77]

Just pondering here, should the implementation be fn(y,x) or -fn(x,y)? Maybe if fn is a strict weak ordering it doesn't matter?

[adamroyjones]

@randall77: It's a fair thing to ponder. I believe they're equivalent.

Let fn be a function of type func(x, y T) int and suppose that an asymmetric relation $<$ on $T$ can be defined as follows. (Strict weak orders are asymmetric.)

• If fn(x, y) > 0, then $y < x$.
• If fn(x, y) < 0, then $x < y$.
• If fn(x, y) == 0, then neither $x < y$ nor $y < x$.

The sign of fn(y, x) is the opposite of the sign of fn(x, y).

• If fn(y, x) > 0, then $x < y$, so fn(x, y) cannot be positive (as it'd break the asymmetry) or zero (as $x < y$).
• If fn(y, x) < 0, then $y < x$, so fn(x, y) cannot be negative (as it'd break the asymmetry) or zero (as $y < x$).
• If fn(y, x) == 0, then neither $x < y$ nor $y < x$, so fn(x, y) cannot be positive or negative.

I quite like the implementation that swaps the arguments as it gets quite directly to the duality, but I'm not totally wedded to it.