https://github.com/golang/go/issues/45955 Skip to content Sign up Sign up * Why GitHub? Features - + Mobile - + Actions - + Codespaces - + Packages - + Security - + Code review - + Project management - + Integrations - + GitHub Sponsors - + Customer stories- * Team * Enterprise * Explore + Explore GitHub - Learn and contribute + Topics - + Collections - + Trending - + Learning Lab - + Open source guides - Connect with others + The ReadME Project - + Events - + Community forum - + GitHub Education - + GitHub Stars program - * Marketplace * Pricing Plans - + Compare plans - + Contact Sales - + Education - [ ] [search-key] * # In this repository All GitHub | Jump to | * No suggested jump to results * # In this repository All GitHub | Jump to | * # In this organization All GitHub | Jump to | * # In this repository All GitHub | Jump to | Sign in Sign up Sign up {{ message }} golang / go * Notifications * Star 85.2k * Fork 12.4k * Code * Issues 5k+ * Pull requests 292 * Actions * Projects 3 * Wiki * Security * Insights More * Code * Issues * Pull requests * Actions * Projects * Wiki * Security * Insights 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. Pick a username [ ] Email Address [ ] Password [ ] [ ] Sign up for GitHub 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 Jump to bottom proposal: slices: new package to provide generic slice functions # 45955 Open ianlancetaylor opened this issue May 5, 2021 * 90 comments Open proposal: slices: new package to provide generic slice functions # 45955 ianlancetaylor opened this issue May 5, 2021 * 90 comments Labels Proposal generics Projects Proposals Milestone Proposal Comments @ianlancetaylor Copy link Contributor @ianlancetaylor ianlancetaylor commented May 5, 2021 * edited 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. // Package slices defines various functions useful with slices of any type. // Unless otherwise specified, these functions all apply to the elements // of a slice at index 0 <= i < len(s). package slices import "constraint" // See #45458 // Equal reports whether two slices are equal: the same length and all // elements equal. Floating point NaNs are not considered equal. // The elements are compared in index order, and the comparison // stops at the first unequal pair. func Equal[T comparable](s1, s2 []T) bool // EqualFunc reports whether two slices are equal using a comparison // function on each pair of elements. The elements are compared in // index order, and the comparison stops at the first index for which // eq returns false. func EqualFunc[T any](s1, s2 []T, eq func(T, T) bool) bool // Compare does a lexicographic comparison of s1 and s2. // The elements are compared sequentially starting at index 0, // until one element is not equal to the other. The result of comparing // the first non-matching elements is the result of the comparison. // If both slices are equal until one of them ends, the shorter slice is // lexicographically less than the longer one // The result will be 0 if s1==s2, -1 if s1 < s2, and +1 if s1 > s2. func Compare[T constraint.Ordered](s1, s2 []T) int // CompareFunc is like Compare, but uses a comparison function // on each pair of elements. The elements are compared in index order, // and the comparisons stop after the first time cmp returns non-zero. // The result will be the first non-zero result of cmp; if cmp always // returns 0 the result is 0 if len(s1) == len(s2), -1 if len(s1) < len(s2), // and +1 if len(s1) > len(s2). func CompareFunc[T any](s1, s2 []T, cmp func(T, T) int) int // Index returns the index of the first occurrence of v in s, or -1 if not present. func Index[T comparable](s []T, v T) int // IndexFunc is like Index but uses a comparison function. func IndexFunc[T any](s []T, v T, cmp func(T, T) bool) int // Contains reports whether v is present in s. func Contains[T comparable](s []T, v T) bool // ContainsFunc is like Contains, but it uses a comparison function. func ContainsFunc[T any](s []T, v T, cmp func(T, T) bool) bool // LastIndex? LastIndexFunc? // Map turns a []T1 to a []T2 using a mapping function. func Map[T1, T2 any](s []T1, f func(T1) T2) []T2 // Filter returns a new slice containing all elements e in s for which keep(e) is true. func Filter[T any](s []T, keep func(T) bool) []T // Reduce reduces a []T1 to a single value of type T2 using // a reduction function. This applies f cumulatively to the elements of s. // For example, if s a slice of int, the sum of the elements of s is // Reduce(s, 0, func(a, b int) int { return a + b }). func Reduce[T1, T2 any](s []T1, initializer T2, f func(T2, T1) T2) T2 // MapInPlace copies the elements in src to dst, using a mapping function // to convert their values. This panics if len(dst) < len(src). // (Or we could return min(len(dst), len(src)) if that seems better.) func MapInPlace[type D, S](dst []D, src []S, f func(S) D) // FilterInPlace modifies s to contain only elements for which keep(e) is true. // It returns the modified slice. func FilterInPlace[T any](s []T, keep func(T) bool) []T // Insert inserts v into s at index i, returning the modified slice. // In the returned slice r, r[i] == v. This panics if !(i >= 0 && i <= len(s)). // This function is O(len(s)). func Insert[T any](s []T, i int, v T) []T // InsertSlice inserts si into s at index i, returning the modified slice. // In the returned slice r, r[i] == si[0] (unless si is empty). // This panics if !(i >= 0 && i <= len(s)). func InsertSlice[T any](s, si []T, i int) []T // Remove removes the element at index i from s, returning the modified slice. // This panics if !(i >= 0 && i < len(s)). This function is O(len(s)). // This modifies the contents of the slice s; it does not create a new slice. func Remove[T any](s []T, i int) []T // RemoveSlice removes j-i elements from s starting at index i, returning the modified slice. // This can be thought of as a reverse slice expression: it removes a subslice. // This panics if i < 0 || j < i || j > len(s). // This modifies the contents of the slice s; it does not create a new slice. func RemoveSlice[T any](s []T, i, j int) []T // Resize returns s with length c. If the length increases, the new trailing // elements will be set to the zero value of T. The capacity of the returned // slice is not specified. func Resize[T any](s []T, c int) []T The text was updated successfully, but these errors were encountered: 493 8 53 [?] 40 43 7 @gopherbot gopherbot added this to the Proposal milestone May 5, 2021 @gopherbot gopherbot added the Proposal label May 5, 2021 @ianlancetaylor ianlancetaylor added the generics label May 5, 2021 @ianlancetaylor ianlancetaylor added this to Incoming in Proposals May 5, 2021 @randall77 This comment has been hidden. Sign in to view @cespare This comment has been hidden. Sign in to view @cespare Copy link Contributor @cespare cespare commented May 5, 2021 In general I think a slices package will be necessary. Functions like Equal, Insert, and Remove will be especially welcome improvements over the current boilerplate. I have two concerns about the list of functions here: 1. Too much bloat to start with. I think we should err on the side of being too minimal and add new functions in future releases as they prove worthwhile. For instance, I think that CompareFunc will be rarely used and doesn't obviously pull its weight here. 2. Too much emphasis on a functional programming style using higher-order functions. My experience with languages like JS and Java (and quite a few others which were more C-like in their initial incarnations and added a lot of higher-order function stuff later) is that there is an unfortunate dichotomy between writing for loops and using higher-order functions. Code which heavily uses the latter looks very different on the page from the former, impeding readability. The higher-order function style also tends to be much slower, so when writing a loop there's a decision burden every time between saving a line or two and writing fast code. (TIMTOWTDI is not really the Go ethos.) And programmers usually prefer concision, so the net result is often slow, HOF-heavy code. The HOF style of code is also a bit clunky with Go's current function literals; adding many more HOFs will create pressure to add new syntax (#21498). In summary, I feel like this nudges the language in a non-Go-like direction. A thing that I really like about Go is that, for many tasks, I just write a plain, clear for loop which gets compiled to the obvious machine code. I don't look forward to a future where the prevailing style is to replace each for loop with a sufficiently clever slices.Reduce. With these ideas in mind, I'd divide this list of functions into three groups. Clearly worthwhile in a v1 of slices: * Equal * Compare * Index * Contains * LastIndex * Insert * InsertSlice * Remove * RemoveSlice * Resize Borderline: * EqualFunc * ContainsFunc * Map * Filter * FilterInPlace Not worth it: * CompareFunc * IndexFunc * LastIndexFunc * Reduce * MapInPlace 132 84 3 [?] 13 @ianlancetaylor This comment has been hidden. Sign in to view @ianlancetaylor This comment has been hidden. Sign in to view @mnasruul This comment was marked as off-topic. Sign in to view @IceWreck Copy link @IceWreck IceWreck commented May 5, 2021 * edited Why not container/slices and later if needed container/maps ? 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 42 1 @sfllaw Copy link @sfllaw sfllaw commented May 5, 2021 * edited 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? 1 [?] 2 @sfllaw This comment has been hidden. Sign in to view @mvdan This comment has been hidden. Sign in to view @sfllaw This comment has been hidden. Sign in to view @fzipp Copy link Contributor @fzipp fzipp commented May 5, 2021 @ianlancetaylor MapInPlace[type D, S] uses the old syntax. It should be MapInPlace[D, S any]. 1 @komuw Copy link Contributor @komuw komuw commented May 5, 2021 @ianlancetaylor did you mean?; -func MapInPlace[type D, S](dst []D, src []S, f func(S) D) +func MapInPlace[D, S](dst []D, src []S, f func(S) D) 2 @Merovius Copy link @Merovius Merovius commented May 5, 2021 * edited One think to point out is that the Map and MapInPlace could be unified under MapAppend[D, S any](dst []D, src []S, f func(S) D), which appends to dst - Map would be equivalent to passing nil for dst and MapInPlace would be passing dst[:0]. Similar for Filter. Not saying we should, just that we could. And I find InPlace a slightly weird bikeshed color for Map, where D and S can be different, thus the mapping is never "in place". Personally, I'm a bit concerned about Index and especially Contains. IMO they suggest that unordered slices are a suitable data structure for sets. Anecdotally, using x in y for a Python list was the single most common mistake I had to deduct points for [edit] in an algorithms and datastructure class. Really need to hire a copy-editor [/edit] 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 sort. 6 @extrasalt Copy link @extrasalt extrasalt commented May 5, 2021 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 15 3 @DylanMeeus Copy link @DylanMeeus DylanMeeus commented May 5, 2021 * edited 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). 13 @sluongng Copy link @sluongng sluongng commented May 5, 2021 // Resize returns s with length c. If the length increases, the new trailing // elements will be set to the zero value of T. The capacity of the returned // slice is not specified. func Resize[T any](s []T, c int) []T Not obvious what would be the behavior in case where len(s) > c. Would the returning slice be a truncated s, taking the first c elements or will s be returned as-is? // Map turns a []T1 to a []T2 using a mapping function. func Map[T1, T2 any](s []T1, f func(T1) T2) []T2 // Filter returns a new slice containing all elements e in s for which keep(e) is true. func Filter[T any](s []T, keep func(T) bool) []T // MapInPlace copies the elements in src to dst, using a mapping function // to convert their values. This panics if len(dst) < len(src). // (Or we could return min(len(dst), len(src)) if that seems better.) func MapInPlace[type D, S](dst []D, src []S, f func(S) D) // FilterInPlace modifies s to contain only elements for which keep(e) is true. // It returns the modified slice. func FilterInPlace[T any](s []T, keep func(T) bool) []T 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. So I wonder if we gona need a separate CL for something like Promise [T any]. // Insert inserts v into s at index i, returning the modified slice. // In the returned slice r, r[i] == v. This panics if !(i >= 0 && i <= len(s)). // This function is O(len(s)). func Insert[T any](s []T, i int, v T) []T // InsertSlice inserts si into s at index i, returning the modified slice. // In the returned slice r, r[i] == si[0] (unless si is empty). // This panics if !(i >= 0 && i <= len(s)). func InsertSlice[T any](s, si []T, i int) []T // Remove removes the element at index i from s, returning the modified slice. // This panics if !(i >= 0 && i < len(s)). This function is O(len(s)). // This modifies the contents of the slice s; it does not create a new slice. func Remove[T any](s []T, i int) []T // RemoveSlice removes j-i elements from s starting at index i, returning the modified slice. // This can be thought of as a reverse slice expression: it removes a subslice. // This panics if i < 0 || j < i || j > len(s). // This modifies the contents of the slice s; it does not create a new slice. func RemoveSlice[T any](s []T, i, j int) []T I don't agree with usage of panic here. Perhaps returning an err or there should be an Optional type/struct that can be either a value or an error. Might be worth implementing these in a separate CL instead of the initial CL. 2 6 1 @sanggonlee Copy link @sanggonlee sanggonlee commented May 5, 2021 These seem like they would make our lives slightly easier, but I thought one of the philosophies of Go was that operations not in O(1) runtime shouldn't hide their complexity? I thought that was the main reason there were no simple commonly used abstractions like map, filter, etc in Go. Although I suppose the runtime of these functions are quite universally understood by most developers... 9 7 @bcmills Copy link Member @bcmills bcmills commented May 5, 2021 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 slices package. 10 1 @bcmills Copy link Member @bcmills bcmills commented May 5, 2021 * edited 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 Reduce and even Map much less useful than the corresponding functions in functional programming languages, especially when compared to the for loops we can already write. (I looked at Map in particular https://github.com/ bcmills/go2go/blob/master/map.go2, but found it quite awkward compared to the typical functional map.) On the other hand, Map and Reduce would be much more clearly useful if we had some way to express "assignable to" as a constraint, which I believe would be a coherent addition to the existing design. It's not obvious to me changing those functions to use such a constraint would be backward-compatible, so I think they should be omitted until we have more hands-on experience with generic functional programming in Go. 15 @empath-75 Copy link @empath-75 empath-75 commented May 5, 2021 * edited 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. 4 @bcmills Copy link Member @bcmills bcmills commented May 5, 2021 * edited I agree with @sluongng that the behavior of Resize seems unclear. I also don't really understand its purpose -- can't we already resize a slice using the built-in slice operator? I think a Clone method that returns a copy of a slice (up to its length) without accepting a length parameter -- analogous to the bytes.Clone proposed in #45038 -- would be much clearer for decreasing a length. For increasing a length, I wonder if it would be clearer to provide a function that increases the capacity instead, analogous to (*bytes.Buffer).Grow: // 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 []T with capacity at least c" could be written as: s := slices.Grow([]T{}, c) 8 @carlmjohnson Copy link Contributor @carlmjohnson carlmjohnson commented May 5, 2021 * edited 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. 2 @arroo Copy link @arroo arroo commented May 5, 2021 * edited one thing I have found useful on more than one occasion from JS's Reduce implementation is including the index as an argument to the provided function. so it would be: func Reduce[T1, T2 any](s []T1, initializer T2, f func(T2, T1, int) T2) T2 1 1 @bcmills Copy link Member @bcmills bcmills commented May 5, 2021 * edited The Slice variant of Insert seems like too much duplication to me. We have only one append in the language, not separate append variants for one element and multiple elements -- why should Insert be any different? If we make Insert analogous to append, that gives the signature: func Insert[T any](s []T, i int, v ...T) []T which seems like it handily covers the use-cases for both the proposed Insert and InsertSlice. 10 @bcmills Copy link Member @bcmills bcmills commented May 5, 2021 I think the signature for RemoveSlice may be surprising. I would intuitively expect it to accept a length instead of a second index. That being the case, I think a function named RemoveN that explicitly accepts a length would be clearer -- it's a bit more awkward for the "two indices" case, but it would be much more natural for many cases and also a lot less likely to be misread: // 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 N suffix already has a precedent in the standard library in strings.SplitN.) 7 1 36 hidden items Load more... @carlmjohnson Copy link Contributor @carlmjohnson carlmjohnson commented May 5, 2021 I'm conflicted on the behavior of MapInPlace, because it sort of feels like it should act like copy(), which will just copy as many items as it can, but I think that implies that it should return the number of items copied. Map always returns a slice of the same length as the initial slice. Are you thinking of FlatMap? I have also sometimes wanted a thing which is like that, but can take an existing slice, and reuse it or grow it as necessary, but I think that's getting too complex. That's how AppendX works. It's quite a nice idiom when you get used to it! It can be used in place or for creating a new slice or for adding onto an existing slice. See https://pkg.go.dev/strconv# pkg-functions for existing examples. @jrockway Copy link @jrockway jrockway commented May 5, 2021 In the code that I write, these operations come up rarely. Something like slices.Equal comes up frequently in tests, but the output of cmp.Diff is better for debugging failing tests (and all the transformation plugins are nice). I feel like the cases where I most need library functions like this is when dealing with sets, typically implemented as operations on map[T]struct{}. I have definitely written union/intersection functions over these types before, again and again, and because it's not generic I end up writing tests for these each time, which is annoying. I fear that the easy availability of library functions for slices.Contains will encourage people to represent sets as slices, and write something like: for _, a := range as { if slices.Contains(bs, a) { return true } } return false; This will be speedy in their unit test where as and bs are a handful of elements, and then crash in production where the slices are longer and the O(n*m) complexity bites them. But, it's not really up to the language to make people write good code -- the code reviewer should catch this. Some comments mention that library functions shouldn't be O(n) complexity. strings.Contains and sort.Slice are counterexamples. Both are beneficial because strings.Contains delegates to strings.Index, which does a better job than what you would type into your code without thinking much. sort.Slice is similar -- nobody really wants to lookup quicksort/mergesort just so they can present their list of users in alphabetical order. (Digressing a little, I probably most use sort.* to make tests pass, which means I really want an unordered set instead of an ordered slice. I'm officially a set crazy person, sorry about that. I tell myself I'm being nice to API consumers by sorting the results of my function, but I know that the API consumer will never trust that they're getting a sorted list back, so every time I sort I'm burning O(n log n) operations twice ;) Anyway, my overall thought is that the majority of these functions are easy to implement in an efficient manner with for loops, which has the benefit of not hiding the O(n) nature from code reviewers. I have specific complaints about CompareFunc. Imagine you have a slice of URLs, and you want to see if the server returns the same Content-Type header for each. The signature forces you to share a global context.Context for the entire comparison (instead of for each comparison), and to panic on error (or otherwise hide the error from the caller): as := []string{"http://example.com/test.txt", "http://example.com/image.png"} bs := []string{"http://example.com/another-test.txt", "http://example.com/another-image.png"} result := slices.EqualFunc(as, bs, func(a, b string) bool { resA, err := http.Head(a) if err != nil { panic(err) // !!! } resB, err := http.Head(b) if err != nil { panic(err) } return resA.Header.Get("content-type") == resB.Header.Get("content-type") }) This sounds contrived, but doing I/O and encountering hangs/errors is fairly common. I think this API encourages people to write worse code than if they typed in the slice equality function manually. But, because the example is so contrived, it's hard to tell. My TL;DR is that I want sets.Union and sets.Intersection where type Set[T any] map[T]struct{} more than I want any slice function. But that is off topic for this discussion, so I apologize for the digression. 2 1 @rsc Copy link Contributor @rsc rsc commented May 5, 2021 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 @rsc rsc moved this from Incoming to Active in Proposals May 5, 2021 @nemith Copy link Contributor @nemith nemith commented May 5, 2021 This sounds contrived, but doing I/O and encountering hangs/ errors is fairly common. I think this API encourages people to write worse code than if they typed in the slice equality function manually. But, because the example is so contrived, it's hard to tell. Planning for I/O in a comparison function seems like a complete anti-pattern. I am happy with the existing function call to, at least, highlight abuse like this. This is much better served with a for loop. That being said it does bring up interesting questions around error handling in map/filter. 4 @jrockway Copy link @jrockway jrockway commented May 5, 2021 Planning for I/O in a comparison function seems like a complete anti-pattern. Yup, fair enough. (To some extent, it is hard to tell what is I/O and what isn't. Your chunk-o-memory could be in the processor's L1 cache, or it could be an mmap'd file on a fileserver on Mars. The API is the same but the expected error rate and latency are very different. That is not up to the slices library, however, so I'm happy not discussing poorly-chosen EqualFunc functions.) @rsc rsc mentioned this issue May 5, 2021 proposal: review meeting minutes #33502 Open @ulikunitz Copy link Contributor @ulikunitz ulikunitz commented May 5, 2021 EqualFunc appears to me unfortunately named because the eq function could be any boolean operator. f := slices.EqualFunc[int](a, b, func(x,y int) bool { return x < y }) would make sense and be useful code, but doesn't compute equality. BoolOp may be a better name. @bcmills Copy link Member @bcmills bcmills commented May 5, 2021 @ulikunitz, maybe slices.Pairwise, as in "are a and b pairwise-equal? " 1 @jimmyfrasche Copy link Member @jimmyfrasche jimmyfrasche commented May 5, 2021 Why not use constraint type inference so these work for any type S [] T? Not sure if it meets the bar, but I've found Any/All functions to be useful. (Take a slice and a predicate func and return true if any (resp. all) items in the slice cause the predicate to return true). I have definitely written Any at least a dozen times in Go. Those could be done in terms of Reduce but that can't short circuit. @lollipopman Copy link @lollipopman lollipopman commented May 5, 2021 Personally, I'm a bit concerned about Index and especially Contains. IMO they suggest that unordered slices are a suitable data structure for sets. Anecdotally, using x in y for a Python list was the single most common mistake I had to deduct points for [edit] in an algorithms and datastructure class. Really need to hire a copy-editor [/edit] Would using Find rather than Contains help to indicate to a user that the implementation is just a for loop over the elements? 2 2 @Merovius Copy link @Merovius Merovius commented May 5, 2021 @lollipopman I subjectively think Find would indeed be a better name than Contains. 3 3 @tandr Copy link @tandr tandr commented May 5, 2021 * edited Re: Find vs Contains Usually Find implies it will return an object that was matching the predicate, where is Contains traditionally just a check (returning bool) to see if container has an object matching a predicate. I would vote to keep it as is right now. 5 @klajdiruli93 Copy link @klajdiruli93 klajdiruli93 commented May 5, 2021 @lollipopman, @Merovius Find infers that is shuld return the postion of the find so it's the same as the proposed Index Although Contains too can be easily written in terms of Index. I don't agree however to not include it just because some people might mistake it to be a suitable datastructure for sets. Plenty of current code already returns slices of various types and often enough the size of these is small enough that the overhead of creating a proper set type to test for existence of an element alreday eliminates what benefit you get. @Merovius Copy link @Merovius Merovius commented May 5, 2021 I'd be good with leaving Index/Find in and dropping Contains. I don't think writing/reading Find(vs, v) >= 0 is that much worse than Contains(vs, v), but Index/Find is harder to mistake in terms of cost. And to be clear: I don't think the most obvious alternative to look for an element is to put the data in a set datastructure - I think the obvious alternative is to sort the slice once and use binary search from then on. The cost of sorting is quickly amortized, especially if the number of elements is small enough to make a linear search tolerable. Granted, sorting only works for ordered types. 1 @rogpeppe Copy link Contributor @rogpeppe rogpeppe commented May 5, 2021 One thing that's perhaps worth pointing out here is the close relationship of this proposed package with the bytes and strings packages. I think it's worth preserving that relationship where possible. 5 @lollipopman Copy link @lollipopman lollipopman commented May 5, 2021 One thing that's perhaps worth pointing out here is the close relationship of this proposed package with the bytes and strings packages. I think it's worth preserving that relationship where possible. good point @rauchenstein Copy link @rauchenstein rauchenstein commented May 5, 2021 Functional style at the level of slices isn't the right place, imo. If that's your desired style, go all the way with iterators and/or views that can be composed, then materialized back into a slice if needed. Basic slice utility like Equals, Compare, Index, Insert [Slice], Remove[Slice], Resize, are nice. If they are included, IndexFunc and ContainsFunc should probably take a predicate instead of a value and a comparator. Might (idx int, ok bool) be more idiomatic for Index's return value than returning -1 on "not found"? @hherman1 Copy link @hherman1 hherman1 commented May 5, 2021 * edited In support of @cespare's comment, I wanted to demonstrate a poor UX quality of some of the functional operators in this package. In java one might combine map/filter like so: list .stream() .map(e -> fetchMetadata(e)) .filter(Objects::nonNull) .map(m -> serialize(m)) .collect(Collectors.toList())); In the proposed api, this becomes: slices.Map(slices.Filter(slices.Map(list, func(l) {return fetchMetadata(l)}), func(o) { return o != nil }), func(m) { return serialize(m) }); What I don't like about this is that your eyes have to bounce back and forth between the list of operators (map, filter, map) and the list of actual functions, and figure out which function applies to which operator, because they are separated, increasingly as you add more operations, and flipped in order. I find this hard to read. 1 [?] 2 @colin-sitehost Copy link @colin-sitehost colin-sitehost commented May 5, 2021 * edited @hherman1: beat me to the draw; I too fully support the flow style, but it looks like the authors feel that implementing methods on interfaces (or generic parameters) is too confusing since there should only be "one way to do things": #39799. (This has some contradictions, since you can call sync.Map.Delete(sync.Map{}, "") or (&sync.Map{}).Delete(""), but they seem resolute.) I think the response you will get is either reformat: (which imo is more readable, but still reverses the order of operations because prefix operators, and violates the line of sight rule) slices.Map( slices.Filter( slices.Map( list, func(l) {return fetchMetadata(l)} ), func(o) { return o != nil }, ), func(m) { return serialize(m) }, ) but more likely, rewrite it with a bunch of temporary variables: (there are probably some perf implication, but I tend to prefer not making vars when not required) one := slices.Map(list, func(l) {return fetchMetadata(l)}) two := slices.Filter(one, func(o) { return o != nil }) three := slices.Map(two, func(m) { return serialize(m) }) and this completely ignores the inergonomic nature of having to write the full func (x Xxx, y, Yyy) Zzz { ... } every time? 1 @rauchenstein Copy link @rauchenstein rauchenstein commented May 5, 2021 @hherman1, to be fair, you're creating a bunch of unnecessary anonymous functions. slices.Map(slices.Filter(slices.Map(list, fetchMetadata), todo.NotNull[Metadata], serialize); Your point stands, though, that java's syntax would have supported other processing than just function calls. Your example also makes clear, if you are going to define these higher-order functions (which, again, I don't think should be done here), putting function first and container last tends to make them nest a little nicer: slices.Map(serialize, slices.Filter(todo.NotNull[Metadata], slices.Map(fetchMetadata, list))) @colin-sitehost Copy link @colin-sitehost colin-sitehost commented May 5, 2021 I have some concerns about not having a plan for custom comparability, considering the footgun that is time.Time (see 45961 and 22978) and other pseudo comparable types. If we implement Equal and EqualFunc, technically experienced operators may know that you should call slices.EqualFunc([]time.Time{...}, []time.Time{...}, time.Time.Equal), but many people do not now you can even reference the time.Time.Equal symbol directly and the other will still compile. Is it worth investigating a holistic solution to custom comparability before exposing these symbols? @colin-sitehost Copy link @colin-sitehost colin-sitehost commented May 5, 2021 * edited @hherman1, to be fair, you're creating a bunch of unnecessary anonymous functions. you are not wrong, but there are cases where this is required: (and I assume there are more) // type conversions, could be solved by other generic functions slices.Map([]int{...}, func(i int) int { return int(math.Abs(float64(i))) }) // currying, pretty sure this will never be ergonomic (also error handling, see above) slices.Map([]string{...}, func(s string) time.Time { t, _ := time.Parse(time.RFC3339, s); return t }) @Merovius Copy link @Merovius Merovius commented May 5, 2021 * edited @hherman1 @colin-sitehost FTR, Map, Reduce, [DEL:Filter:DEL] and more - i.e. the functions that seem to benefit most from being methods, in your arguments - can't be implemented as methods, because that would require extra type parameters on methods, which the generics design does not allow, for good reasons. So, the discussion "do we want methods or do we want functions" is moot for these functions. The question is just "do we want functions or do we want nothing". Some of the functions (like Equal, Compare, Index, Contains...) could be methods, though. @Jasonfran Copy link @Jasonfran Jasonfran commented May 5, 2021 I think this proposal is great for giving us the simplest solution to the problem of having to write tedious for loops for every basic slice operation. I don't think it needs to be any more complicated that this. This is most likely all that 90% of Go developers will need. Those 10% will develop their own solutions and some will share it with the community like they already do today. Anyone here hoping to get a chainable Java Streams/.NET LINQeqsue API should also temper their expectations. Unless I'm missing something then the current generics proposal wouldn't allow you to chain calls so freely. The proposal states that methods can't define their own type parameters. Methods may not take additional type arguments Although methods of a generic type may use the type's parameters, methods may not themselves have additional type parameters. Where it would be useful to add type arguments to a method, people will have to write a suitably parameterized top-level function. Look at this example Map(T1 -> T2).Filter(T2).Map(T2 -> T3) If you want to write this then T3 needs to be known at the point of Filter(T2) because Filter(T2) would need to return some generic type with a method capable of mapping T2 to T3. That type would have to look something like Stream[T2, T3]. We can get halfway there, but it's never going to be as fluent. @colin-sitehost Copy link @colin-sitehost colin-sitehost commented May 5, 2021 imo, I think we may finally have a compelling case for tuples (#32941 ), though I do not plan to hold my breath: /* var s [](int, error) */ s := slices.Map([]string{...}, strconv.Atoi) /* var s1 []int */ s1 := slices.Filter(s, func(i int, err error) (int, bool) { return i, err =! nil }) as I write this out, multi return looks more and more like a hack for error handling, because I really want an either/result, but I think the tuple usecase stands for cases where you really do want to return multiple meaningful values, like func xxx() (int, string, error). I could see the feedback, that you should do all this in one function, though this kills composability and forces the use of a closure, killing testability: var e error s := slices.Map([]string{...}, func(s string) int { i, err := strconv.Atoi(s) if err != nil { e = err // maybe e = append(e, error) is better } return i }) if e != nil { // uggh } @jrockway Copy link @jrockway jrockway commented May 5, 2021 I'm not sure I'm totally sold on the Java-style chaining. It's nice in Haskell (where lazy evaluation "does what you mean"), and Python folks do like their list comprehensions, but I think the boring old Go way is pretty readable and pretty writable. I.e. instead of: map(filter(map(xs, F), Select), G) A loop isn't the worst thing ever: var result []Z for _, x := range xs { y := F(x) if Select(y) { z := G(y) result = append(result, z) } } Plus, you aren't allocating a bunch of intermediate slices. For my own code post-generics, I'm going to be very careful about when I use generics. Like interfaces, the temptation is to overuse, and then have a program that is harder to read and debug. When you need them, you need them, but going out looking for a place to use a programming language feature is something that scares me. Writing things in terms of map/filter/reduce instead of for loops is something I will personally need a very good reason to do, and I haven't found that reason yet. (I do it in Python because it's the idomatic way, of course. Which way will be the One True Way in a Go that has the slices library? Does Go even want a One True Way?) @Jasonfran Copy link @Jasonfran Jasonfran commented May 5, 2021 @colin-sitehost I can see the appeal but I don't think it's very convincing argument here. It's not like using this package will be a necessity for all slice related operations in the future. We will still have our fine and dandy for loop, which seems like the best solution to your little problem there. strs := []string{...} var result []int for _, s := range strs { i, err := strconv.Atoi(s) if err != nil { // handle error as usual } result = append(result, i) } I think it's just the case of choosing the right tool for the job. If a Map function that handled errors was something you really wanted, then it's trivial to implement yourself. func MapErr[T1, T2 any](s []T1, f func(T1) (T2, error)) ([]T2, error) https://go2goplay.golang.org/p/r37CKojOS2T @colin-sitehost Copy link @colin-sitehost colin-sitehost commented May 5, 2021 * edited @Jasonfran I can see the appeal but I don't think it's very convincing argument here. It's not like using this package will be a necessity for all slice related operations in the future. We will still have our fine and dandy for loop, which seems like the best solution to your little problem there. take care, all these examples are toys [recte strawmen], so creating counter examples is usually pretty easy, but when I have four functions all with different return types (and more complex logic than call "function and append") this gets really painful. I think it's just the case of choosing the right tool for the job. If a Map function that handled errors was something you really wanted, then it's trivial to implement yourself. assuming that I only return a thing and an error, what about the case where length of the number of returns changes? now we are back to the state we are in today where I have to duplicate a bunch of code, simply because the return types are incompatible. @colin-sitehost Copy link @colin-sitehost colin-sitehost commented May 5, 2021 @jrockway Does Go even want a One True Way? apparently: #39799 (comment) Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment Assignees No one assigned Labels Proposal generics Projects Proposals Active Milestone Proposal Linked pull requests Successfully merging a pull request may close this issue. None yet 49 participants @jrockway @gaal @rogpeppe @rsc @ndeloof @sfllaw @acacio @seebs @carlmjohnson @titpetric @akavel @cespare @DeedleFake @nemith @cristaloleg @jimmyfrasche @fzipp @hherman1 @Merovius @EdSchouten and others * (c) 2021 GitHub, Inc. * Terms * Privacy * Security * Status * Docs * Contact GitHub * Pricing * API * Training * Blog * About You can't perform that action at this time. You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.