Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

proposal: cmp: add Reverse function #65632

Open
adamroyjones opened this issue Feb 9, 2024 · 6 comments
Open

proposal: cmp: add Reverse function #65632

adamroyjones opened this issue Feb 9, 2024 · 6 comments
Labels
Proposal
Milestone
Proposal

Comments

@adamroyjones
Copy link

adamroyjones commented Feb 9, 2024 •
edited

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.
@gopherbot gopherbot added this to the Proposal milestone Feb 9, 2024
@ianlancetaylor
Copy link
Contributor

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

@fzipp
Copy link
Contributor

fzipp commented Feb 10, 2024

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
Copy link
Contributor

itchyny commented Apr 17, 2024

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
Copy link
Author

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

@randall77
Copy link
Contributor

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
Copy link
Author

@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 &lt; y$.
  • If fn(x, y) == 0, then neither $x &lt; y$ nor $y &lt; x$.

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

  • If fn(y, x) > 0, then $x &lt; y$, so fn(x, y) cannot be positive (as it'd break the asymmetry) or zero (as $x &lt; y$).
  • If fn(y, x) < 0, then $y &lt; x$, so fn(x, y) cannot be negative (as it'd break the asymmetry) or zero (as $y &lt; x$).
  • If fn(y, x) == 0, then neither $x &lt; y$ nor $y &lt; 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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
Proposal
Projects
Proposals
Status: Incoming
Milestone
Proposal
Development

No branches or pull requests
6 participants
@itchyny @fzipp @ianlancetaylor @randall77 @gopherbot @adamroyjones