CC @eliben

These are the ones from x/exp/slices, which we've discussed at length before. The main blocker is how to spell 'cmp.Ordered'. For this discussion let's assume 'cmp.Ordered' is the spelling and not focus on that.

Are there any concerns about the APIs otherwise?

Sorry if this was explained elsewhere, but why isn't there a SortStable?

@willfaught see the paper trail from #47619 (comment)

Perhaps nitpicking, but the comment on Sort regarding NaNs seems a bit prescriptive considering that we now have math.Compare and math.Compare32.

@zephyrtronium Just to be clear, are you suggesting this:

// Use slices.SortFunc(x, func(a, b float64) bool {return math.Compare(a, b) < 0 })

More precisely, I am pointing out that the comment as written only says to use a < b || (math.IsNaN(a) && !math.IsNaN(b)), when math.Compare(a, b) < 0 is another way that exists. Each has different semantics and different advantages, but only one way is mentioned. Again, I think I am nitpicking, but it seems preferable to me to leave that sentence out of the documentation and leave the preferred approach(es) to examples.

Thanks. Updated the initial comment.

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

see the paper trail from #47619 (comment)

@eliben This seems to be the relevant comment:

One caveat: we chose to exclude SortStable based on @dsnet 's comments; the version with constraints.Ordered is indistinguishable from Sort because two elements that sort equal are otherwise indistinguishable for practical purposes.

However, it doesn't link to the other comment it references. Can you summarize it? This seems to be saying that the Sort func already does a stable sort. If that's the case, then don't we need an unstable sort func as well?

However, it doesn't link to the other comment it references. Can you summarize it? This seems to be saying that the Sort func already does a stable sort. If that's the case, then don't we need an unstable sort func as well?

It refers to this comment: #47619 (comment) (GitHub's auto-hiding comments in long threads interferes with the bread crumbing). It has to do with what values Ordered actually covers and the logical equivalence of stable and unstable sort for such values. See https://pkg.go.dev/golang.org/x/exp/constraints#Ordered for all the types - what does "stable" sorting mean for such values?

I once again would like to advocate to use a single type of comparison function - i.e. to either make SortFunc accept a cmp function, or to make BinarySearchFunc accept a less function. Personally, I think the former is better, as implementing less in terms of cmp is cheaper than vice-versa.

Having two flavors of comparison function means you have to implement both per type, or you have to spell out a wrapper every time you need to go from one to the other, or you have to have a generic function that can transform one into the other (and the latter two probably add function call overhead). ISTM that ~any use of BinarySearchFunc has to rely on at least one use of Sort, so the use cases seem fairly coupled.

I once again would like to advocate to use a single type of comparison function - i.e. to either make SortFunc accept a cmp function, or to make BinarySearchFunc accept a less function. Personally, I think the former is better, as implementing less in terms of cmp is cheaper than vice-versa.

FWIW this dual use is carried over from the sort package (https://pkg.go.dev/sort), which has cmp for Find (the spiritual ancestor of BinarySearchFunc) and Less for Sort (https://pkg.go.dev/sort#Interface).

So it seems like a bit of a conundrum; having just cmp for slices would make it more internally consistent, but on the other hand would also make the contract subtly differ from the sort package for sorting, creating another kind of inconsistency.

@eliben IMO adding a new package, with generics no less, frees us from this historical burden, if we choose so.

Also, FWIW, golang.org/x/exp/slices.BinarySearchFunc explicitly moved from less to cmp, pretty much at the same time sort.Find was added. So that still wouldn't explain why two different flavors where used to begin with, if consistency was the goal ([edit] the proposal answers that question [/edit]).

I don't believe we should only provide the func versions. It happens frequently that you want to sort or search a slice by the usual < order provided by the language. Providing that directly without having to say ", cmp.Less" is more convenient and can be made far more efficient. This also follows other APIs in the language that provide a reasonable default behavior but then also have the extensible Func version, like strings.Index vs strings.IndexFunc.

Along these same lines, after the discussion of min and max on #59488, we should probably provide slices.Min and slices.Max here, alongside slices.Sort, since Min and Max are the other natural operations that would use Ordered.
The specific signatures would be:

func Min[E cmp.Ordered](x []E) E
func Max[E cmp.Ordered](x []E) E
func MinFunc[E any](x []T, less func(E, E) bool) E
func MaxFunc[E any](x []T, less func(E, E) bool) E

If these are invoked with an empty list, they panic("slices.Min: min of empty list") and so on.

What do they return when len(x) == 0?

Updated: they panic.

If we are going to add slices.Min/Max then i would suggest also including variants that return the index of the element instead of the element itself. (These are sometimes called argmax/argmin.)

// {Min,Max}Index{,Func} returns the index of the leftmost smallest/largest element of [slice],
// according to the < operator or less function.
// Panics if [slice] is empty.
func MinIndex[E cmp.Ordered](slice []E) int
func MaxIndex[E cmp.Ordered](slice []E) int
func MinIndexFunc[E any](slice []E, less func(E, E) bool) int
func MaxIndexFunc[E any](slice []E, less func(E, E) bool) int

Alternatively, maybe Min/Max could return both the element and its index?

Along these same lines, after the discussion of min and max on #59488, we should probably provide slices.Min and slices.Max here, alongside slices.Sort, since Min and Max are the other natural operations that would use Ordered. The specific signatures would be:

func Min[E cmp.Ordered](x []E) E
func Max[E cmp.Ordered](x []E) E
func MinFunc[E any](x []T, less func(E, E) bool) E
func MaxFunc[E any](x []T, less func(E, E) bool) E

If these are invoked with an empty list, they panic("slices.Min: min of empty list") and so on.

I'll look into adding these to exp/slices as a prototype for now

@rsc
Small typo there, should be:

func MinFunc[E any](x []E, less func(E, E) bool) E
func MaxFunc[E any](x []E, less func(E, E) bool) E

Change https://go.dev/cl/495195 mentions this issue: slices: add Min/Max/MinFunc/MaxFunc

If we are going to add slices.Min/Max then i would suggest also including variants that return the index of the element instead of the element itself. (These are sometimes called argmax/argmin.)

// {Min,Max}Index{,Func} returns the index of the leftmost smallest/largest element of [slice],
// according to the < operator or less function.
// Panics if [slice] is empty.
func MinIndex[E cmp.Ordered](slice []E) int
func MaxIndex[E cmp.Ordered](slice []E) int
func MinIndexFunc[E any](slice []E, less func(E, E) bool) int
func MaxIndexFunc[E any](slice []E, less func(E, E) bool) int

Alternatively, maybe Min/Max could return both the element and its index?

IMHO Min and Max should return a single result, this makes them more usable in mathematical expressions. Moreover, I suspect that in the vast majority of cases users are interested in the min/max itself, not the index -- keeping only that will make these functions faster.

I don't object to adding Argmin/Argmax or *Index, but this can be done separately and maybe later as we assess demand.

Personally, I'd prefer argmin and argmax over min and max themselves:

• Going from argmin to min is simply s[slices.MinIndex(s)].
• Argmin has a reasonable non-panic behavior for empty slices: return -1. If you use the above expression directly, you still get a panic. (Granted, checking for len(s) == 0 first also isn't hard.)
• Anecdotally, I've needed the indices of extrema more often than their values. I think that is mostly from a time when I worked on scientific visualization software where it was useful to highlight the location of a maximum in a plot.

It isn't hard to imagine that I'm in the minority camp, though. 🌝

For concreteness, I believe this is the API being proposed:

package slices

func Compare[E cmp.Ordered](s1, s2 []E) int
func Sort[E cmp.Ordered](x []E)
func IsSorted[E cmp.Ordered](x []E) bool
func BinarySearch[E cmp.Ordered](x []E, target E) (int, bool)
func Min[E cmp.Ordered](x []E) E
func Max[E cmp.Ordered](x []E) E

func CompareFunc[E1, E2 any](s1 []E1, s2 []E2, cmp func(E1, E2) int) int
func SortFunc[E any](x []E, less func(a, b E) bool)
func SortStableFunc[E any](x []E, less func(a, b E) bool)
func IsSortedFunc[E any](x []E, less func(a, b E) bool) bool
func BinarySearchFunc[E, T any](x []E, target T, cmp func(E, T) int) (int, bool)
func MinFunc[E any](x []T, less func(E, E) bool) E
func MaxFunc[E any](x []T, less func(E, E) bool) E

There was a typo in the result of CompareFunc (it had no result), which I've fixed here and above.

@rsc there's a discussion in https://go-review.googlesource.com/c/exp/+/495195 about handling of NaNs in the newly added Min and Max functions.

Currently the Sort function in this package doesn't have any special NaN handling (since it's generic and written once for all Ordered types), so NaNs in a slice essentially lead to undefined sorting order (depending on their position, etc.) - with a comment:

// Sort may fail to sort correctly when sorting slices of floating-point
// numbers containing Not-a-number (NaN) values.
// Use slices.SortFunc(x, func(a, b float64) bool {return a < b || (math.IsNaN(a) && !math.IsNaN(b))}

A straightforward implementation of Min and Max will have the same issue, and may need a similar comment warning.

This could also be a topic for the proposal review committee to consider.

Thanks @rsc - I've updated the CL for x/exp/slices to follow this suggestion. I agree that distinguishing -0 vs. +0 in generic code will be tricky (math does it by checking Signbit).

Replying to @Merovius's suggestion about cmp vs less, yes, let's switch to cmp consistently throughout.
The updated API, then, is:

package slices

func Compare[E cmp.Ordered](s1, s2 []E) int
func Sort[E cmp.Ordered](x []E)
func IsSorted[E cmp.Ordered](x []E) bool
func BinarySearch[E cmp.Ordered](x []E, target E) (int, bool)
func Min[E cmp.Ordered](x []E) E
func Max[E cmp.Ordered](x []E) E

func CompareFunc[E1, E2 any](s1 []E1, s2 []E2, cmp func(E1, E2) int) int
func SortFunc[E any](x []E, cmp func(E, E) int)
func SortStableFunc[E any](x []E, cmp func(E, E) int)
func IsSortedFunc[E any](x []E, cmp func(E, E) int) bool
func BinarySearchFunc[E, T any](x []E, target T, cmp func(E, T) int) (int, bool)
func MinFunc[E any](x []E, cmp func(E, E) int) E
func MaxFunc[E any](x []E, cmp func(E, E) int) E

(Only the second half has changed.)

The argument in favor of cmp is consistency within package slices. Now if you are sorting a slice and then doing a binary search over it, you only need to write one comparison function and use it in both calls, instead of having to write two different ones.

The primary argument in favor of less is consistency with package sort. This argument doesn't hold up, for two reasons. First, if you are using a slice, you can do everything within package slices; you'll never import sort. Second, and more importantly, the less function signature used by sort is different from the one we were using here. Package sort's less takes indices, while package slices's less takes elements. So you can't use the same function with both packages, and knowing how to write a function for one package does not immediately mean you know how to write one for package slices. So this argument doesn't hold up.

A secondary argument in favor of less is that less functions tend to be shorter than cmp functions. That's true but being able to use the same function with all these different public APIs certainly beats that. If you were really attached to writing less functions you could write a generic converter. (Even so I wouldn't put one in the standard library since it would encourage inefficient code.)

The argument in favor of cmp is much more compelling than either of these, so consider it changed.

A secondary argument in favor of less is that less functions tend to be shorter than cmp functions.

This argument isn't all that compelling anymore, either. The main complexity of implementing cmp functions is the switch needed to produce ternary results. But with the addition of cmp.Compare, that becomes a single call to a generic helper function. More complex data structures will then be implemented in terms of cmp.Compare or slices.Compare, with complexity approximately equal to the less variant.

Change https://go.dev/cl/496078 mentions this issue: slices: add sorting and comparison functions

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.
— rsc for the proposal review group

Implemented in https://go.dev/cl/496078

Change https://go.dev/cl/498175 mentions this issue: doc: add release notes for additions to the slices package

Change https://go.dev/cl/505796 mentions this issue: slices: clarify MinFunc/MaxFunc result for equal elements