proposal: exp/slices: change slices.BinarySearchFunc E, T ordering in the closure

[twmb]

Today we have:

func BinarySearchFunc[E, T any](x []E, target T, cmp func(E, T) int) (int, bool)

The proposal is to switch it to:

func BinarySearchFunc[E, T any](x []E, target T, cmp func(T, E) int) (int, bool)

Why?

tldr: the current ordering feels like sort.Search, which is awkward because "you have to think in terms of greater-than rather than less-than"

The original BinarySearchFunc was:

func BinarySearchFunc[E any](x []E, target E, cmp func(E, E) int) (int, bool)

Meaning that if I wanted to implement an inline closure, it was not obvious which argument my target would be. I would most likely implement this as general less function: given left and right, return whether left is less than right.

#57348 proposed allowing the target to be a different type. @rsc asked whether E, T is the standard order here, and @aclements mentioned that it is, given Python's bisect and Java's binarySearch. I think the @aclements reply was actually talking about the first two arguments to the binary search function, not the closure's arguments: the first two arguments are always array, then target.

No other language that has a binary search function uses a comparison function similar to BinarySearchFunc's closure: no other language explicitly has the target being the first argument or the second argument. C++'s std::binary_search existed before lambda expressions and the Compare function never calls out argument ordering (in fact, it flips: here then here). C# is similar to C++, C is just completely type blind through void *. Java's Arrays.binarySearch existed since 1.6, before lambdas were introduced in 1.8, and the input Comparator never mentions argument ordering. Rust and Ruby do not even have something similar to slices.BinarySearchFunc -- they have something similar to sort.Find.

In #50340, @rogpeppe mentions that sort.Search is awkward and one of the reasons is that "you have to think in terms of greater-than rather than less-than". This is the basis of the proposal.

When the comparison function uses identical types a person never needs to consider the target in the comparison function. Now that the comparison function supports a different type, if you use a different type, you are thinking backwards. If a person wants to implement the comparator function against a target whose type T is different from the input slice element type E, they now have to think in terms of greater-than rather than less-than. The new comparison function feels like sort.Search.

Example of how I want to write slices.BinarySearchFunc using sort.Find, following with how I always actually do write a buggy comparison function and then spend too much time thinking about conditionals: https://go.dev/play/p/RLsTqohcXcA.

---

Also as a last unimportant aside that might be in a later proposal, I'd actually prefer:

• making it much clearer why I'd use sort.Find vs. slices.BinarySearchFunc
• revert x/exp/slices: Allow different types for haystack/needle in BinarySearchFunc #57348 because these multi-type use cases seems better suited for sort.Find
• mention sort.Find in the docs of slices.BinarySearchFunc (mostly because I completely forgot about sort.Find and personally prefer the closure way of doing things)
• switch BinarySearchFunc to be similar to sort.Find with an index and no target -- the current form seems tailored for primitive types, not large structs

[crisman]

Example of how I want to write slices.BinarySearchFunc using sort.Find, following with how I always actually do write a buggy comparison function and then spend too much time thinking about conditionals: https://go.dev/play/p/4v5SyTKnoMu.

I am confused on what this example is trying to show.

Why do both examples ignore the possible 0 return out of cmp?

And in what I think is on the same topic given:

I would most likely implement this as general less function: given left and right, return whether left is less than right.

With a three output cmp why reduce that to a two output "whether left is less than right"?

[twmb]

@crisman the proposal isn't about the three way comparison aspect -- I'm +1 to keeping a three way comparison. My example was ripped last night from code I was writing where I only needed two way comparison -- I always want to write my logic with the target on the left, and returning comparisons based on the target being less than the other value. With the current E, T, then the target is on the right and the closure implementation is based on the target being greater than the other value.

[ianlancetaylor]

CC @eliben

[ianlancetaylor]

According to the man page, C's bsearch function passes target first to the comparator function.

[eliben]

Thanks for the detailed proposal, @twmb - this is indeed interesting to consider.

@Merovius who proposed #57348

[Merovius]

I don't understand the argument TBH. You are passing a three-way comparison function, with IMO pretty standard and clear definition of in what order the arguments should be compared. So I don't get why you'd have to "think in terms of greater-than". You return different things for "greater-than" and "less-than", so you always think in terms of both.

My example was ripped last night from code I was writing where I only needed two way comparison

Did you "only need two way comparison", or did you "need two way comparison only"? i.e. why couldn't you still return 0 in the equality case?

This is a compelling argument to leave the order as is, in my opinion.

[eliben]

I've just been running some tests and seem to have been thinking in a similar direction as @Merovius

Consider this playground link: https://gotipplay.golang.org/p/I0MHhBKveLI
If we flip the order of passing T, E to the comparator, existing comparators like strings.Compare will not work properly.

[crisman]

The doc for exp/slices says

The slice must be sorted in increasing order, where "increasing" is defined by cmp.

If that's true then something like a perl sort {$a cmp $b} @items would have either the negative and positive outputs of cmp backwards or the list sorted the wrong way.

[crisman]

I also like the current usage of cmp() as when mapped over the whole range of the input slice the outputs will be a set of -1s,0s, and finally 1s.

[Merovius]

I guess if we flipped the order of the argument we'd flip the order of the logic as well, which makes string.Compare work fine? Or I might be confused.

I think as long as we can still pass the natural strings.Compare functions to it, I don't have a strong opinion. But then, if we can do that, I don't really get the problem. Because ISTM it wouldn't solve any confusion about the order of arguments, if the function would look the same?

[twmb]

The equality case is not a factor in this proposal. My point is that if you use a different type, the current argument ordering primes you to think in terms of greater than. I've edited my example above to emphasize that the equality case is not a factor -- the equality case was never mentioned in my first comment, and this is my second comment clarifying that equality is not the confusion.

@Merovius your order-of-the-logic flipping comment is exactly my proposal. I should've led with the full implementation rather than just the type signature.

This is a clearer example using two different types, showing sort.Find, a bugged slices.BinarySearchFunc, a correct slices.BinarySearchFunc, and my commented out preference: https://go.dev/play/p/RLsTqohcXcA
(I've updated the proposal link to this example)