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

slices: new package to provide generic slice functions #45955

Open
ianlancetaylor opened this issue May 5, 2021 · 253 comments
Open

slices: new package to provide generic slice functions #45955

ianlancetaylor opened this issue May 5, 2021 · 253 comments

Comments

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented May 5, 2021

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.

// 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 "constraints" // See #45458 

// Equal reports whether two slices are equal: the same length and all
// elements equal. If the lengths are different, Equal returns false.
// Otherwise, the elements are compared in index order, and the
// comparison stops at the first unequal pair.
// Floating point NaNs are not considered equal.
func Equal[T comparable](s1, s2 []T) bool

// EqualFunc reports whether two slices are equal using a comparison
// function on each pair of elements. If the lengths are different,
// EqualFunc returns false. Otherwise, the elements are compared in
// index order, and the comparison stops at the first index for which
// eq returns false.
func EqualFunc[T1, T2 any](s1 []T1, s2 []T2, eq func(T1, T2) bool) bool

// Compare compares the elements 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
// considered 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 constraints.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 returns the index into s of the first element
// satisfying f(c), or -1 if none do.
func IndexFunc[T any](s []T, f func(T) bool) int

// Contains reports whether v is present in s.
func Contains[T comparable](s []T, v T) bool

// Insert inserts the values v... into s at index i, returning the modified slice.
// In the returned slice r, r[i] == the first v.  Insert panics if i is out of range.
// This function is O(len(s) + len(v)).
func Insert[S constraints.Slice[T], T any](s S, i int, v ...T) S

// Delete removes the elements s[i:j] from s, returning the modified slice.
// Delete panics if s[i:j] is not a valid slice of s.
// Delete modifies the contents of the slice s; it does not create a new slice.
// Delete is O(len(s)-(j-i)), so if many items must be deleted, it is better to
// make a single call deleting them all together than to delete one at a time.
func Delete[S constraints.Slice[T], T any](s S, i, j int) S

// Clone returns a copy of the slice.
// The elements are copied using assignment, so this is a shallow clone.
func Clone[S constraints.Slice[T], T any](s S) S

// Compact replaces consecutive runs of equal elements with a single copy.
// This is like the uniq command found on Unix.
// Compact modifies the contents of the slice s; it does not create a new slice.
func Compact[S constraints.Slice[T], T comparable](s S) S

// CompactFunc is like Compact, but uses a comparison function.
func CompactFunc[S constraints.Slice[T], T any](s S, cmp func(T, T) bool) S

// Grow grows the slice's capacity, if necessary, to guarantee space for
// another n elements. After Grow(n), at least n elements can be appended
// to the slice without another allocation. If n is negative or too large to
// allocate the memory, Grow will panic.
func Grow[S constraints.Slice[T], T any](s S, n int) S

// Clip removes unused capacity from the slice, returning s[:len(s):len(s)].
func Clip[S constraints.Slice[T], T any](s S) S
@gopherbot gopherbot added this to the Proposal milestone May 5, 2021
@ianlancetaylor ianlancetaylor added this to Incoming in Proposals May 5, 2021
@randall77

This comment has been hidden.

@cespare

This comment has been hidden.

@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

Loading

@ianlancetaylor

This comment has been hidden.

@ianlancetaylor

This comment has been hidden.

@mnasruul

This comment was marked as off-topic.

@IceWreck
Copy link

@IceWreck IceWreck commented May 5, 2021

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

Loading

@sfllaw
Copy link
Contributor

@sfllaw sfllaw commented May 5, 2021

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?

Loading

@sfllaw

This comment has been hidden.

@mvdan

This comment has been hidden.

@sfllaw

This comment has been hidden.

@fzipp

This comment has been hidden.

@komuw

This comment has been hidden.

@Merovius
Copy link

@Merovius Merovius commented May 5, 2021

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.

Loading

@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

Loading

@DylanMeeus
Copy link

@DylanMeeus DylanMeeus commented May 5, 2021

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).

Loading

@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.

Loading

@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...

Loading

@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.

Loading

@bcmills
Copy link
Member

@bcmills bcmills commented May 5, 2021

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.

Loading

@empath-75
Copy link

@empath-75 empath-75 commented May 5, 2021

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.

Loading

@bcmills
Copy link
Member

@bcmills bcmills commented May 5, 2021

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)

Loading

@carlmjohnson
Copy link
Contributor

@carlmjohnson carlmjohnson commented May 5, 2021

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.

Loading

@arroo
Copy link

@arroo arroo commented May 5, 2021

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

Loading

@bcmills
Copy link
Member

@bcmills bcmills commented May 5, 2021

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.

Loading

@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.)

Loading

@rsc rsc changed the title proposal: slices: new package to provide generic slice functions slices: new package to provide generic slice functions Aug 11, 2021
@rsc rsc removed this from the Proposal milestone Aug 11, 2021
@rsc rsc added this to the Backlog milestone Aug 11, 2021
@sbstp
Copy link

@sbstp sbstp commented Aug 22, 2021

// Equal reports whether two slices are equal: the same length and all
// elements equal. If the lengths are different, Equal returns false.
// Otherwise, the elements are compared in index order, and the
// comparison stops at the first unequal pair.
// Floating point NaNs are not considered equal.
func Equal[T comparable](s1, s2 []T) bool

A nil slice and an empty slice would be equal in this case? I'm asking because it's not the case if you use say reflect.DeepEqual, but since len(([]T)(nil)) == 0 I think slices.Equal(([]T)(nil), []T{}) should be true.

Loading

@andig
Copy link
Contributor

@andig andig commented Aug 22, 2021

Does it need a new proposal to add the clarification to the comment?

Loading

@ianlancetaylor
Copy link
Contributor Author

@ianlancetaylor ianlancetaylor commented Aug 22, 2021

@sbstp I think the existing comment is clear that an empty slice and a nil slice will cause Equal to return true. It is true that this is no how reflect.DeepEqual behaves; that's OK.

Loading

@DeedleFake
Copy link

@DeedleFake DeedleFake commented Aug 26, 2021

I wanted to comment about this in #47203, but it's been locked, unfortunately. I needed a reverse function for something so I did a manual loop with the intention of replacing it with a call to slices.Reverse() when Go 1.18 comes out, but to my surprise it doesn't seem to have even been proposed, at least not that I saw anywhere. The only equivalent in the standard library that I saw was sort.Reverse(), but that's really inefficient, and a lot more complicated to use, than just a simple reverse.

Any chance that this could get added into the proposal at the last second here?

package slices

func Reverse[T any](s []T) {
  for i := 0; i < len(s) / 2; i++ {
    r := len(s) - i - 1
    s[i], s[r] = s[r], s[i]
  }
}

Loading

@ChrisHines
Copy link
Contributor

@ChrisHines ChrisHines commented Sep 14, 2021

I just noticed that the code in the proposal text has import "constraint" but uses it as constraints. The import statement is missing a final s.

Loading

@ianlancetaylor
Copy link
Contributor Author

@ianlancetaylor ianlancetaylor commented Sep 15, 2021

@ChrisHines Fixed, thanks.

Loading

@matryer
Copy link

@matryer matryer commented Sep 23, 2021

Firstly, I am very excited that this is going to exist. I think it will go a long way to reducing Generics package overload.

Sorry for joining the conversation so late, but I did always assume a package like this would be called slice. I know it breaks with tradition in places (strings, bytes, etc), but;

  1. slice doesn't clash with types like string and byte
  2. slice, in Go, is already a collective term
  3. for me, it's hard to pronounce out loud (or is this just podcast driven design?)
  4. the code we write will read more naturally:
slice.Sort[Elem](x)
slice.SortFunc[Elem](x, func(a, b Elem) bool { /* ... */ })
slice.SortStable[Elem](x)
slice.SortStableFunc[Elem](x, func(a, b Elem) bool { /* ... */ })
slice.IsSorted[Elem](x)
slice.IsSortedFunc[Elem](x, func(a, b Elem) bool { /* ... */ })

slice.BinarySearch[Elem](x Slice, target Elem) int
slice.BinarySearchFunc[Elem](x, func(a, b Elem) bool { /* ... */ }) int

This could just be personal taste, what do others think?

Loading

@carlmjohnson
Copy link
Contributor

@carlmjohnson carlmjohnson commented Sep 23, 2021

Grow and Clip are extremely common operations on []byte. Is it worth adding them to bytes as well just for parity/readability? I already have private versions of these functions in my code.

At this point, bytes already has all but the 3 Func variants and Insert and Delete. I don't think the Funcs really make sense for bytes (they would transform the uint8 which seems unhelpful), but I could be talked into bytes.Insert and bytes.Delete. Grow and Clip make no sense for strings, but you could add strings.Insert and strings.Delete, although I'm not sure how useful they would be.

Loading

@ianlancetaylor
Copy link
Contributor Author

@ianlancetaylor ianlancetaylor commented Sep 23, 2021

@matryer There was some discussion of the general topic at #47319 (comment).

Loading

@ianlancetaylor
Copy link
Contributor Author

@ianlancetaylor ianlancetaylor commented Sep 23, 2021

@carlmjohnson Want to open a proposal for the bytes package?

Loading

@carlmjohnson
Copy link
Contributor

@carlmjohnson carlmjohnson commented Sep 24, 2021

Done #48594.

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Oct 12, 2021

Change https://golang.org/cl/355253 mentions this issue: slices: new package

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Nov 11, 2021

Change https://golang.org/cl/363434 mentions this issue: slices: new package

Loading

gopherbot pushed a commit to golang/exp that referenced this issue Nov 17, 2021
Update the go version in go.mod to go1.18 so that generics are permitted.

For golang/go#45955

Change-Id: Id5ab52d38c465313c27506008aece9356d34e3c9
Reviewed-on: https://go-review.googlesource.com/c/exp/+/363434
Trust: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
@ianlancetaylor
Copy link
Contributor Author

@ianlancetaylor ianlancetaylor commented Nov 17, 2021

This package is now available at golang.org/x/exp/slices. Per https://groups.google.com/g/golang-dev/c/iuB22_G9Kbo/m/7B1jd1I3BQAJ?utm_medium=email&utm_source=footer it will not be put into standard library until the 1.19 release. We may of course adjust it based on anything we learn about having it in x/exp.

Loading

@Skarlso
Copy link
Contributor

@Skarlso Skarlso commented Nov 18, 2021

This is fantastic! I can't wait to use these. No more Contains* in our code. :)

Also, I would like to thank everyone who's been involved in getting typed parameters out the door. Such amazing work and fantastic contribution to the language. Well done everyone! 🎉 All of you deserve several cookies of your choice. :)

Loading

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

Successfully merging a pull request may close this issue.

None yet