-
Notifications
You must be signed in to change notification settings - Fork 17.4k
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
slices: new package to provide generic slice functions #45955
Comments
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
In general I think a I have two concerns about the list of functions here:
With these ideas in mind, I'd divide this list of functions into three groups. Clearly worthwhile in a v1 of
Borderline:
Not worth it:
|
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
Why not Anyways this package would be a welcome addition because its a pain (boilerplate wise) to implement common data structures in Go compared to C++ and this would slightly reduce that boilerplate |
Should this new package mention https://github.com/golang/go/wiki/SliceTricks in its documentation? Should SliceTricks document the new package? How does this wiki page fit into the revised ecosystem? |
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
One think to point out is that the Personally, I'm a bit concerned about I'd be less concerned if there was the equivalent thing for sorted slices as well, so that people at least be made to think about it. Though that would probably live in |
Would flatten and flatMap also be included? I can think of cases where a map would produce a slice of slices and that might need flattening |
I think this is a good idea, and it opens the door to including more functions by default in the future. Functions like these are going to either be provided by the standard library, or we'll end up with multiple "third party" libraries which do these things all in their own way, which will be used by a ton of projects anyway. Especially when people migrate from other languages (Java, C#, ..) they will look for such functions. Providing this out of the box would be in-line with how Go provides other frequently used constructs natively (like handling json data). |
Not obvious what would be the behavior in case where
I wonder it's might worth to provide some interface that would return a lazily-evaluated value here? As the chaining of Map and Filter is very common in Java Stream API.
I don't agree with usage of panic here. |
These seem like they would make our lives slightly easier, but I thought one of the philosophies of Go was that operations not in |
One slice operation I've found myself writing frequently is “return the same slice with its cap reduced to length”. #38081 was declined partially on the grounds that it could be written more clearly as a generic function (#38081 (comment)). I think such a function belongs in the |
I agree with @cespare that some of the functional APIs here seem premature, especially given the lack of a concise lambda. I would add that functional languages tend to rely heavily on covariance, which Go lacks. That makes functions like On the other hand, |
If you're going to do map/filter/reduce doesn't it make more sense to design a more generic interface first, and then implement it for slices? There are a lot more datastructures than slices that could benefit from such a thing. |
I agree with @sluongng that the behavior of I think a For increasing a length, I wonder if it would be clearer to provide a function that increases the capacity instead, analogous to // Grow returns s with capacity at least c.
// If cap(s) >= c already, Grow returns s as-is.
func Grow[T any](s []T, c int) []T Then, increasing the length of the slice is trivial: s := slices.Grow(s, n)[:n] That might also address @mdempsky's use case in proposal #24204 (see #24204 (comment)), since “allocate a new s := slices.Grow([]T{}, c) |
The code I was writing yesterday would have benefited from the existence of slices.Grow. I am also strongly in favor of the Append idiom rather than InPlace. Append is already used throughout the standard library, whereas InPlace has no current uses. |
one thing I have found useful on more than one occasion from JS's
|
The If we make func Insert[T any](s []T, i int, v ...T) []T which seems like it handily covers the use-cases for both the proposed |
I think the signature for That being the case, I think a function named // RemoveN removes n elements from s starting at index i, returning the modified slice.
// This panics if i < 0 || n < 0 || i+n > len(s).
// This modifies the contents of the slice s; it does not create a new slice.
func RemoveN[T any][s []T, i, n int) []T (The |
It appears the generic Sort function uses the QuickSort algorithm, which is O(n^2). Are there plans for moving to an O(nlogn) algorithm, like Merge Sort or IntroSort? |
Despite the function name, it actually uses a hybrid sort that looks pretty similar to introsort at a glance, though I'm not too familiar with introsort. And while quick sort is worst case |
Just to confirm, is the time complexity of the generic sort still O(nlogn)? |
This may have been discussed before, but I'm wondering why the var slice []T
i := slices.IndexFunc(slice, func(t T) bool {
// a predicate
})
if i == -1 {
// not found
return
}
// found, do whatever
elem := slice[i] I believe it would be useful to have a func Find[E any](s []E, f func(E) bool) (E, bool) The boolean value indicates whether the element was found or not. |
|
I think the https://github.com/luraim/fun#map library has a good Map implementation. |
A search of go/src/cmd/compile/internal/syntax/testdata/slices.go Lines 9 to 35 in 83e9a97
|
I think this is a prime usecase for a generic iterator API. Because you ~never want to actually do that conversion, you want to pass a If I'm wrong and there are significant use-cases beyond that, I would retract that concern. Otherwise, I'd prefer if we solved generic iteration for the stdlib and made it easy to use that instead. |
I have had need of both map and filter functions a number of times in the last week. Its easy enough to write your own, but I would like to voice my support of adding map and filter to the slices package. |
Map and filter functions will be much, much more useful on more general iterators. I think that it's worth waiting for #54245 rather than adding only semi-useful functions to the That being said, this package is in |
Compare #54768 (slices.DeleteFunc) which I think would be useful even without having iterator support. |
|
I think there's a lot to be said for just counting lines/tokens/characters saved when evaluating a potential abstraction: ns = slices.Map(ns, func(n int) int {
return n * n
}) 3 lines, 22 tokens, 56 characters for i, n := range ns {
ns[i] = n * n
} 3 lines, 17 tokens, 41 characters An in-place map just doesn't pay for itself. You do get a savings of characters when you compare to making a new map, but then the question of efficiency vs an iterator comes into play. |
@carlmjohnson Not that I think these are useful metrics, but strs := slices.Map(ints, strconv.Itoa) 1 line, 12 tokens, 38 characters strs := make([]string, len(ints))
for i, n := range ns {
strs[i] = strconv.Itoa(n)
} 4 lines, 32 tokens, 89 characters. We can always cherry-pick examples that make our favorites look favorable. [edit] I just realized that you specifically tried to talk about an in-place |
I have opened a new proposal #57433 to move golang.org/x/exp/slices into the standard library. Closing this proposal as completed. Thanks for all the discussion. |
Note: Discussion is now at #47203.
This proposal is for use with #43651. We propose defining a new package,
slices
, that will provide functions that may be used with slices of any type. If this proposal is accepted, the new package will be included with the first release of Go that implements #43651 (we currently expect that that will be Go 1.18).This description below is focused on the API, not the implementation. In general the implementation will be straightforward. The description has been updated from the original proposal several times based on the discussion.
The text was updated successfully, but these errors were encountered: