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.

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

proposal: sort: add InvertSlice #36887

Closed
codic12 opened this issue Jan 30, 2020 · 57 comments
Closed

proposal: sort: add InvertSlice #36887

codic12 opened this issue Jan 30, 2020 · 57 comments
Labels
Projects
Milestone

Comments

@codic12
Copy link

@codic12 codic12 commented Jan 30, 2020

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

@networkimprov networkimprov commented Jan 30, 2020

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

@ALTree ALTree commented Jan 30, 2020

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.

@ALTree ALTree closed this Jan 30, 2020
@networkimprov
Copy link

@networkimprov networkimprov commented Jan 30, 2020

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

@ianlancetaylor ianlancetaylor commented Jan 30, 2020

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

@ianlancetaylor ianlancetaylor commented Jan 30, 2020

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

@networkimprov networkimprov commented Jan 30, 2020

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

@codic12
Copy link
Author

@codic12 codic12 commented Jan 30, 2020

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

@codic12 codic12 commented Jan 30, 2020

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

@networkimprov networkimprov commented Jan 30, 2020

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

@codic12 codic12 commented Jan 30, 2020

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

@codic12
Copy link
Author

@codic12 codic12 commented Jan 30, 2020

Ah.

@codic12
Copy link
Author

@codic12 codic12 commented Jan 30, 2020

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

@codic12 codic12 changed the title Add `strings.Reverse()` Add `strings.Reverse()` and/or `sort.InvertSlice()` Jan 30, 2020
@diamondburned
Copy link

@diamondburned diamondburned commented Jan 30, 2020

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

@codic12 codic12 commented Jan 30, 2020

True, but then sort.InvertSlice would also be useful

@codic12
Copy link
Author

@codic12 codic12 commented Jan 30, 2020

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

@networkimprov
Copy link

@networkimprov networkimprov commented Jan 30, 2020

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 added a commit to codic12/go that referenced this issue Jan 30, 2020
Closes golang#36887
@codic12
Copy link
Author

@codic12 codic12 commented Jan 30, 2020

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

@jimmyfrasche
Copy link
Member

@jimmyfrasche jimmyfrasche commented Jan 30, 2020

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

@gopherbot gopherbot commented Jan 30, 2020

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

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Jan 30, 2020

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

@codic12 codic12 commented Jan 30, 2020

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

@codic12 codic12 commented Jan 30, 2020

Wait
That was a bot

@codic12
Copy link
Author

@codic12 codic12 commented Jan 31, 2020

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

@ALTree ALTree commented Jan 31, 2020

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

@codic12 codic12 commented Jan 31, 2020

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

@ALTree
Copy link
Member

@ALTree ALTree commented Jan 31, 2020

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

@as
Copy link
Contributor

@as as commented Jan 31, 2020

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

@codenoid codenoid commented Jan 31, 2020

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

@codic12 codic12 commented Jan 31, 2020

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

@networkimprov networkimprov commented Jan 31, 2020

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

@as as commented Jan 31, 2020

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

What is an original index?

@codic12
Copy link
Author

@codic12 codic12 commented Jan 31, 2020

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

@networkimprov
Copy link

@networkimprov networkimprov commented Feb 1, 2020

@gsbhasin123 you missed my previous comment.

@codic12 codic12 changed the title Add `strings.Reverse()` and/or `sort.InvertSlice()` Add `sort.InvertSlice()` Feb 1, 2020
@codic12
Copy link
Author

@codic12 codic12 commented Feb 1, 2020

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

@codic12
Copy link
Author

@codic12 codic12 commented Feb 1, 2020

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:

string(sort.InvertSlice([]rune("some string")))
	
@networkimprov
Copy link

@networkimprov networkimprov commented Feb 1, 2020

@codic12
Copy link
Author

@codic12 codic12 commented Feb 1, 2020

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

@ianlancetaylor ianlancetaylor changed the title Add `sort.InvertSlice()` proposal: sort: add InvertSlice Feb 1, 2020
@gopherbot gopherbot added this to the Proposal milestone Feb 1, 2020
@gopherbot gopherbot added the Proposal label Feb 1, 2020
@networkimprov
Copy link

@networkimprov networkimprov commented Feb 1, 2020

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

@rsc rsc commented Feb 26, 2020

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 rsc added this to Incoming in Proposals Feb 26, 2020
@rsc
Copy link
Contributor

@rsc rsc commented Mar 4, 2020

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

@rsc rsc moved this from Incoming to Likely Decline in Proposals Mar 4, 2020
@rsc rsc moved this from Likely Decline to Declined in Proposals Mar 11, 2020
@rsc
Copy link
Contributor

@rsc rsc commented Mar 11, 2020

No change in consensus, so declined.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Proposals
Declined
Linked pull requests

Successfully merging a pull request may close this issue.

You can’t perform that action at this time.