Go: proposal: sort: add InvertSlice

[codic12]

Golang should have an InvertSlice() function in some module (preferably sort), which essentially reverses all slice elements. This would allow some neat features like string reversal.

This is easy to implement and will not break code. Please consider the proposal.

[networkimprov]

I agree that it should be in the stdlib, both for strings and slices, e.g. sort.InvertSlice(slice)

Note the comparison in the loop can be simpler than i < len(r)/2:

   for a1, a2 := 0, len(S)-1; a1 < a2; a1, a2 = a1+1, a2-1 {
      S[a1], S[a2] = S[a2], S[a1]
   }

[ALTree]

This was rejected in the past: #14777. A few comments:

Even C and C++ have this

This is usually not considered a valid argument for inclusion of a new feature in the standard library. There are many things that other languages have, and Go has not.

This is easy to implement and will not break code.

This is not enough: the addition also needs to be useful enough to a great number of Go programmer to justify its inclusion in the standard library. As noted in #14777, how often would the typical Go programmer use Reverse (except when implementing it as a programming exercise)?

I'm closing here as a dup of #14777.

[networkimprov]

Pls reopen. #14777 was closed after 2.5h and a single comment by a Go team member, without hearing the author's use case. Proposals like this are now reviewed by committee.

Even if strings.Reverse() isn't accepted, the widely applicable sort.InvertSlice() should be considered, and that would allow string(sort.InvertSlice([]rune(s))).

[ianlancetaylor]

I'm not aware of a standard C function that reverses a string. Do you have a pointer? C++ has reverse iterators, but again I'm not aware of a function or method that reverses a string, unless you mean std::reverse which is a generic operation.

In Go, strings are a sequence of bytes but many of the functions in the strings package treat them as a sequence of characters. A reverse operation is inherently ambiguous: does it reverse bytes or characters?

[ianlancetaylor]

It's fine to make this a proposal, but it should be specific about exactly what strings.Reverse should do, and why that is better than the other choice.

[networkimprov]

@ianlancetaylor could you reopen the issue, as it's under discussion?

[codic12]

@ianlancetaylor for C++, std::reverse (from iostream.h or string.h, not sure). For C, I'm talking about strrev from string.h.
I am talking about reversing runes, aka characters.

[codic12]

and why that is better than the other choice.

which other choice?

This is not enough: the addition also needs to be useful enough to a great number of Go programmer to justify its inclusion in the standard library. As noted in #14777, how often would the typical Go programmer use Reverse (except when implementing it as a programming exercise)?

This is a useful core language feature, cryptography programs could benefit from it.

[networkimprov]

@gsbhasin123, a crypto algorithm would use []byte, not string. So I think you have a stronger case by proposing for package sort:

func InvertSlice(s interface{}) interface{} // returns its argument ('Reverse' is taken)

That enables a string inversion via string(sort.InvertSlice([]rune(str)).([]rune))

[codic12]

@networkimprov "package sort" meaning?
sorry, I'm new to Golang

[networkimprov]

https://golang.org/pkg/sort/

[codic12]

Ah.

[codic12]

I see, I thought you were talking about sorting packages lol.
An InvertSlice function would make this easy, yes

[diamondburned]

I'd say add strings.Reverse and bytes.Reverse. A lot of functions from the bytes package are similar to strings, so why not?

[codic12]

True, but then sort.InvertSlice would also be useful

[codic12]

Where is the strings package located? I'm gonna do a PR.

[codic12]

Nvm, found it: https://github.com/golang/go/tree/master/src/strings

[networkimprov]

How to contribute: https://golang.org/doc/contribute.html

I'd wait on the PR until the proposal is accepted; not many proposals are...

[codic12]

Oops, didn't see that, already made it :(

[jimmyfrasche]

With generics, there could be a Reverse function in the hinted-at slices package that would allow

• string(slices.Reverse([]byte(s)))
• string(slices.Reverse([]rune(s)))
• whatever the equivalent with grapheme clusters is/would be

It would also work directly on []byte which seems to be the intended use case. I've never had to reverse a string in real code though I have reversed many lists.

As far as I can tell, strrev is MS only and deprecated and there are multiple versions of it for the various unicode-aware cases listed above.

[gopherbot]

Change https://golang.org/cl/217120 mentions this issue: Addstrings.Reverse()``

[ianlancetaylor]

@gsbhasin123 The strrev function is non-standard, and as far as I know is only available in old versions of the Microsoft C library.

The C++ generic algorithm std::reverse could in Go be implemented using generics, if we had generics. It would apply to a slice or array, not a string. In C++ it applies to std::string because C++ std::string is equivalent to Go []byte, not to Go string.

[codic12]

@ianlancetaylor I did not know that, ah.

Change https://golang.org/cl/217120 mentions this issue: Add strings.Reverse()``

I just opened that. I didn't read the thing though, so I edited the title and name, but it didn't change on gerrit

[codic12]

Wait
That was a bot

[codic12]

https://go-review.googlesource.com/c/go/+/217120 new link

[ianlancetaylor]

I still haven't seen an explanation of whether strings.Reverse should reverse bytes or reverse characters, and why.

[codic12]

Runes (same as characters iirc)

[diamondburned]

RE: generics, why not implement a reflectlite-using function similar to sort.Slice?

[codic12]

Use https://go-review.googlesource.com/c/go/+/217120 for further tracking.

RE: generics, why not implement a reflectlite-using function similar to sort.Slice?

Might want to open a new issue for this.

[diamondburned]

Why? reflectlite is what sort.Slice uses, which you'd need for sort.ReverseSlice.

[codic12]

Yes you said that on the discord :P

[jimmyfrasche]

A reflect version would either be in-place or you'd have to use it like Reverse(s).([]T). Also, there's not really a natural place to put a "reverses any slice" function now, but generics would probably come with a slices package containing generic operations on slices where it could go.

@gsbhasin123 Runes are not characters. They are unicode code points. Those may be characters in some languages (or at least could be after the appropriate normalization is performed). The general notion of "character" is captured by the idea of the grapheme cluster.

What is the use case for reversing a string?

[codic12]

@jimmyfrasche I see.

What is the use case for reversing a string?

Could be many things. For example, you may want to reverse ciphertext for a thin additional layer of security.

[networkimprov]

@jimmyfrasche re "a natural place to put a 'reverses any slice' function..." It's a special case of sort.Slice(), which is why I suggested sort.InvertSlice().

@gsbhasin123 as I mentioned above, crypto "strings" use []byte not string. We should set aside strings.Reverse(), as the real problem here is slices.

Also note that the Go team sets a very high bar for new stdlib APIs. They only want to add things that a significant fraction of Go users need. sort.InvertSlice() probably qualifies, strings.Reverse() doesn't.

[codenoid]

hi @networkimprov is https://play.golang.org/p/UkAqDfSfzHh qualified to be in stdlib ?

[ALTree]

This thread is 35 comments long and not a single person has yet answered these three questions:

• What was the last time you used a string.Reverse function in a Go program?
• What was the program doing? Why did it need to rune-reverse a string?

This is a useful core language feature, cryptography programs could benefit from it.

Can you provide an example of a "cryptography program" that would use a rune-reversing function like the one that you proposed in CL 217120?

[networkimprov]

@ALTree, since the first comment, I've tried to focus this on an addition to package "sort" to reverse any slice, which no one disputes the utility of.

[randall77]

@networkimprov This proposal was originally about strings.Reverse. If you think that's a bad idea and want to propose sort.InvertSlice instead, open a new proposal or convince the OP to repurpose this one.

I agree with @ALTree 's questions about strings.Reverse.

I think a slice reverser would be a reasonably useful function to have.
It's not a hard function to write yourself. Show us cases where people have written and used it.
I'll start, sort of. See where we reverse-and-copy a slice. We could do that loop with a reverse function pluscopy.
I don't understand why this function would live in package sort. It has nothing to do with sorting.

[codic12]

I have already rephrased the question to include Sort.InvertSlice().
I will also be making a PR using my own code for inverting a slice soon.

[ALTree]

If you are retracting the strings.Reverse proposal, I suggest you edit it out from the title and close the gerrit CL you sent.

[codic12]

Actually I'm not, I'll leave it open for further discussion unless you want to close it

[ALTree]

@gsbhasin123 That can you answer the questions I asked above?

[as]

This thread is 35 comments long and not a single person has yet answered these three questions:

What was the last time you used a string.Reverse function in a Go program?

2011-2012

What was the program doing? Why did it need to rune-reverse a string?

I was learning about defer with my _beautiful_ Reverse function

func rev(s string) (t string) {
    for _, c := range s {
        defer func(c rune) { t += string(c) }(c)
    }
    return t
}

Excluding programming interviews, I have not reversed a string since.

[codenoid]

This thread is 35 comments long and not a single person has yet answered these three questions:

* What was the last time you used a string.Reverse function in a Go program?

I had forgotten

* What was the program doing? Why did it need to rune-reverse a string?

reverse "Hello World!" to "!dlroW olleH" using javascript (browser).

here's the code : "Hello World!".split("").reverse().join("")

[codic12]

@ALTree I really can't - i've written many string reversing programs, but they were all to learn a new language.Proves your point ig

[networkimprov]

@gsbhasin123 so please close the CL and revise the issue text/title.

@randall77 slice inversion is sorting a slice by the ~original~ initial index of each item.

Re use cases, I use slice inversion to produce a list of messages in reverse chronological order from a data source which stores them in received order.

[as]

@randall77 slice inversion is sorting a slice by the original index of each item.

What is an _original_ index?

[codic12]

@as That actually seems like a more efficient way to do it!

[networkimprov]

@gsbhasin123 you missed my previous comment.

[codic12]

@networkimprov a bot auto created it. I don't know to close the gerrit CL, but PR is closed.

[codic12]

Assuming InvertSlice existed, would this be a good strings.Reverse implementation?

func Reverse(s string) string {
    return string(sort.InvertSlice([]rune(s)))
}

Or, if someone didn't want to create a function:
```go
string(sort.InvertSlice([]rune("some string")))

[networkimprov]

See https://github.com/golang/go/issues/36887#issuecomment-580514147

[codic12]

string(sort.InvertSlice([]rune(str)).([]rune))
Looks like mine, but why .([]rune)?

[networkimprov]

This thread has a lot of noise unrelated to the proposal, making it hard to digest. For questions about Go see the docs, or post to https://groups.google.com/forum/#!forum/golang-nuts

[rsc]

I still can't tell whether this issue is about strings.Reverse or slices.Reverse (meaning reverse the slice from its current order) or sort.ReverseSlice (meaning sort the slice in reverse order).

strings.Reverse is a duplicate of #14777. It remains not needed often enough to merit inclusion in the standard library. The existence of the proposal process does not require revisiting every decision we have made in the past.

slices.Reverse and slices.Copy are both likely candidates for a slices package once we have generics. We don't need an issue tracking those - wait until the package exists and doesn't have what you want.

sort.Slice is a helper that essentially requires writing an inline func to work. If you want to sort in the reverse order, you replace \< with > in the func you write. We don't need a general reverser for that API.

Even though I can't tell which one of these three is being proposed, none of them seems to need an open issue.

[rsc]

Based on the discussion above, this seems like a likely decline (even though I still don't know exactly what is being proposed).

[rsc]

No change in consensus, so declined.