slices: Use ~[]E throughout #60546

Merovius · 2023-06-01T05:24:47Z

Proposal

I propose to change the slices function signatures to always add an extra type parameter S ~[]E, even when the slice type does not appear as a return type. When a function has multiple slice arguments, it should have multiple type parameters, for full generality.

Notably, this should happen before Go 1.21 is released, if at all, as I think it would be a breaking change otherwise.

Concretely, I propose to change these function signatures:

func BinarySearch[S ~[]E, E cmp.Ordered](x S, target E) (int, bool)
func BinarySearchFunc[S ~[]E, E, T any](x S, target T, cmp func(E, T) int) (int, bool)
func Compare[S1, S2 ~[]E, E cmp.Ordered](s1 S1, s2 S2) int
func CompareFunc[S1 ~[]E1, S2 ~[]E2, E1, E2 any](s1 S1, s2 S2, cmp func(E1, E2) int) int
func Contains[S ~[]E, E comparable](s S, v E) bool
func ContainsFunc[S ~[]E, E any](s S, f func(E) bool) bool
func Equal[S1, S2 ~[]E, E comparable](s1 S1, s2 S2) bool
func EqualFunc[S1 ~[]E1, S2 ~[]E2, E1, E2 any](s1 S1, s2 S2, eq func(E1, E2) bool) bool
func Index[S ~[]E, E comparable](s S, v E) int
func IndexFunc[S ~[]E, E any](s S, f func(E) bool) int
func IsSorted[S ~[]E, E cmp.Ordered](x S) bool
func IsSortedFunc[S ~[]E, E any](x S, cmp func(a, b E) int) bool
func Max[S ~[]E, E cmp.Ordered](x S) E
func MaxFunc[S ~[]E, E any](x S, cmp func(a, b E) int) E
func Min[S ~[]E, E cmp.Ordered](x S) E
func MinFunc[S ~[]E, E any](x S, cmp func(a, b E) int) E
func Reverse[S ~[]E, E any](s S)
func Sort[S ~[]E, E cmp.Ordered](x S)
func SortFunc[S ~[]E, E any](x S, cmp func(a, b E) int)
func SortStableFunc[S ~[]E, E any](x S, cmp func(a, b E) int)

Rationale

On Twitter, @joncalhoun asked why the proposal for slices.Reverse uses the ~[]E trick. Though notably the commited version does not. That conversation prompted this proposal, that maybe it should.

The current approach is for the slices package to use the extra S ~[]E whenever the slice appears in a return type. This allows a statement like s = slices.Compact(s) to work with defined slice types. Functions where it does not appear in a return type use []E directly, as a value of a defined slice type is assignable to []E. So slices.Reverse(s) works fine, even if s is a defined slice type.

However, there is still a case where it makes a difference: When instantiating slices.Reverse you can only get a func([]int), not a func(MySliceType). This matters when passing them to higher level functions:

package main

func main() {
	type NumberList []int
	nl := NumberList{4, 5, 6}

	ApplyAll(nl, ReverseV1) // Compiles fine
	ApplyAll(nl, ReverseV2) // Does not compile
}

func ReverseV1[S ~[]E, E any](s S) {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	}
}

func ReverseV2[E any](s []E) {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	}
}

func ApplyAll[T any](v T, fs ...func(T)) {
	for _, f := range fs {
		f(v)
	}
}

I'm not entirely certain the difference is important to cover, but I thought it's probably useful to talk about this while we could still change it (even though it's past the freeze).

Cost

The main cost of this proposal is visual clutter and complexity of the function signatures. When looking at them the first time, it might not be obvious if and why this is needed (as demonstrated by @joncalhoun asking that question, even though he is a Go veteran).

A secondary cost is that explicit instantiation of these functions becomes a tiny bit more cumbersome. Currently, you write slices.Reverse[T], in the future you might have to write slices.Reverse[[]T]. The element type itself can always be infered, I think. But I might be missing a corner case, in which case the instantiation will be slices.Reverse[[]T, T]. Either way, functions like Equal would definitely become more cumbersome, with slices.Equal[T] vs. slices.Equal[[]T, []T].

Notably #59338 specifically mitigated this second cost a lot, by at least applying better type-inference when passing them directly to higher-level functions. Further improvements to type-inference can reduce this cost further, by reducing the number of cases where explicit instantiation is necessary.

Alternatives considered

Do nothing. This requires people who need higher-level functions with custom slice types to write wrappers in those cases. Wouldn't be the end of the world. I consider this a corner case anyways and keeping that corner case more cumbersome is maybe okay.
Solve it in the future, with better type-inference. I don't think this works, as this is not about a failure of type-inference. A func([]int) is not a func(IntSlice), no matter what we infer. That is, given that you can't instantiate slices.Reverse to get a func(IntSlice), inference obviously can't help you.
Solve it in the future with co/contravariance. If Go had co/contravariance for func, a func([]int) could be made assignable to func(IntSlice) (as IntSlice is assignable to []int (and vice-versa)). Type-inference could then solve whatever friction is left. Personally, I'd honestly prefer this, but I'm not optimistic it would ever happen. And even if, that seems like a far more significant change.

The text was updated successfully, but these errors were encountered:

bitfield · 2023-06-01T12:59:02Z

If I'm understanding your argument correctly, this sounds like one of those "make it a little bit complicated for everybody" versus "make it simple for most, but quite complicated for some rare cases" tradeoffs.

And if that's the case, then put me down as an enthusiast of "simple for most" (that is, 👎 ). Go seems to be generally biased in this direction, doesn't it? I certainly prefer, for example, just Equal[E [comparable] to Equal[S1, S2 ~[]E, E comparable], if they're equivalent, and I assume we all feel the same.

For such a big up-front cost, I think we'd want to see a correspondingly big benefit, and I'm not seeing that in this proposal (but if you think there is one, then laying it out in more detail may be the most persuasive way to make the case).

Merovius · 2023-06-01T13:33:24Z

@bitfield Everything you say is basically correct. Note that anything you say applies to Clone[S ~[]E, E any](s S) S as well - at least qualitatively. It's a tradeoff and I'm not sure what to base that tradeoff on, objectively.

I think there is a case to be made that the standard library really should provide the most general version of these functions we can. For example, we also have CompareFunc[E1, E2 any](s1 []E1, s2 []E2, cmp func(E1, E2) int) int, which is certainly more complex than CompareFunc[E any](s1, s2 []E, cmp func(E, E) int) int. We are paying that, to be more general. How often will we need to compare two slices of different element types? I don't know.

I also don't feel the cost is that high TBH. I'd expect the types in pretty much every usage to be fully inferable. So this is really just a documentation issue and we can get used to that.

But ultimately, I don't have very strong feelings about this.

earthboundkid · 2023-06-01T16:28:56Z

How does this interact with the new type inference in Go 1.21?

ianlancetaylor · 2023-06-01T16:49:36Z

CC @griesemer

griesemer · 2023-06-01T18:03:00Z

@carlmjohnson I don't see an immediate issue with the improved type inference. As @Merovius already pointed out, this is not so much about type inference but about the existing Go type system: if a function is passed/assigned to another function, the argument types must be identical. func([]byte) is not identical with func(byteslice) even if type byteslice []byte.

By changing the signatures as suggested, after instantiation we get (using the above example) func([]byte) or func(byteslice) depending on the type we actually have ([]byte or byteslice). If we leave things alone, we will always get func([]byte) even when we have a byteslice. This is fine unless we need the function type elsewhere.

neild · 2023-06-01T19:40:39Z

By my count, there are 20 functions in the slices package defined as F[E sometype], and 15 defined as F[S ~[]E, E sometype]. So about half the functions in slices are already defined using the more complicated two-parameter form, because they return a slice.

Leaving aside all consideration of passing slices functions to higher-order functions, I think that it's simpler to be consistent.

Right now, if you pass the type parameter explicitly you need to know which form the function you're calling is using. This seems confusing, even if it is a confusion few people will encounter. Again, consistency seems simpler.

idx := slices.Index[int](s, e) // parameterized with int
slices.Insert[[]int](s, 0, v)  // parameterized with []int

So my vote is to consistently use the two-type-parameter form throughout.

Merovius · 2023-06-01T19:42:13Z

@carlmjohnson I mention the new rules FWIW, in the last paragraph of "Cost". And note that the main example in the top post does not compile with Go 1.20, but only with tip, exactly because of that change. [edit] I mean, technically it compiles with neither, because of the "does not compile" line. But you get what I mean [/edit]

awagner-iq · 2023-06-13T09:02:26Z

I'm playing around with the package I wrote for my dayjob that I had in mind when filing this issue and thought it might be useful to make some observations. I published that package as well, now. Our main use for this is protobuf, which generates getters for all fields. This package can relatively conveniently (though inefficiently) compose those into chained comparators for complex message types.

Two relevant functions from that package are cmp.Slice (equivalent to slices.Compare after this proposal) and cmp.SliceFunc (not quite equivalent to slices.CompareFunc after this proposal, as it only allows a single slice type and it returns a function, as my package is all about composing comparators). We can also simulate a version of cmp.SliceFunc without this proposal:

func SliceFunc[T any](c cmp.Cmp[T]) cmp.Cmp[[]T] {
	return cmp.SliceFunc[[]T](c)
}

When trying this in the playground, with Go 1.21 we can observe:

The pure []int versions (lines 15 and 16) just can't be made to work with this. To me, this demonstrates that this issue isn't purely theoretical. And repeated proto fields are also fairly common, so we are going to want to use these helpers with slices.
The cmp.SliceFunc version (line 14) can not infer its type argument and requires explicit instantiation. I found this a bit surprising, as I assumed spec: infer type arguments from assignments of generic functions (reverse type inference) #59338 to help with a case like this. It seems even that isn't quite there. I think in theory this can be inferred (every relevant type appears in arguments), so in the future we might improve type inference to help here. But it demonstrates that the "instantiations might look more complex" argument is also not purely theoretical. I think that's particularly relevant as slices.CompareFunc allows for different slice types, so it requires two type arguments (though I think the same applies to the current form).

I believe this mostly confirms the arguments made above and makes them more concrete. It just stood out to me this morning when putting last touches on the API.

awagner-iq · 2023-06-13T13:37:32Z

After having a closer look, I think the inference fails because #59338 is about passing an identifier for a generic function directly, while the example has a function call. So I think what's missing is exactly the "Inferring based on assignment context" extension mentioned in #58650.

earthboundkid · 2023-06-13T13:55:37Z

Can someone with tagging ability label this release-blocker? It should be decided one way or the other before 1.21.

gopherbot · 2023-06-13T16:51:00Z

Change https://go.dev/cl/502955 mentions this issue: slices: consistently use S ~[]E

eliben · 2023-06-14T12:50:32Z

@prattmic should this be kept a blocker until https://go.dev/cl/502955 lands? We want to include that CL in the release for sure

ianlancetaylor · 2023-06-14T17:32:45Z

Reopening to complete proposal process.

rsc · 2023-06-14T18:10:19Z

Based on the discussion above, this proposal seems like a likely accept.
— rsc for the proposal review group

ianlancetaylor · 2023-06-14T22:01:11Z

CL is committed, removing release-blocker label.

rsc · 2023-06-21T19:50:09Z

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.
— rsc for the proposal review group

Make all functions use a constraint S ~[]E even if they don't return the slice type. This makes explicitly instantiating the functions more consistent: you don't have to remember which take ~[]E and which do not. It also permits inferring the type when passing one of these functions to some other function that is using a named slice type. Fixes golang#60546 Change-Id: Ib3435255d0177fdbf03455ae527d08599b1ce012 Reviewed-on: https://go-review.googlesource.com/c/go/+/502955 Reviewed-by: Ian Lance Taylor <iant@google.com> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Robert Griesemer <gri@google.com> Run-TryBot: Ian Lance Taylor <iant@golang.org> Reviewed-by: Axel Wagner <axel.wagner.hh@googlemail.com> Reviewed-by: Eli Bendersky <eliben@google.com> Run-TryBot: Ian Lance Taylor <iant@google.com> Auto-Submit: Ian Lance Taylor <iant@google.com>

Merovius added the Proposal label Jun 1, 2023

gopherbot added this to the Proposal milestone Jun 1, 2023

randall77 mentioned this issue Jun 1, 2023

slices: add Concat #56353

Closed

neild added the release-blocker label Jun 13, 2023

neild modified the milestones: Proposal, Go1.21 Jun 13, 2023

prattmic added the okay-after-rc1 Used by release team to mark a release-blocker issue as okay to resolve either before or after rc1 label Jun 13, 2023

prattmic removed the okay-after-rc1 Used by release team to mark a release-blocker issue as okay to resolve either before or after rc1 label Jun 14, 2023

gopherbot closed this as completed in 0a48e5c Jun 14, 2023

ianlancetaylor reopened this Jun 14, 2023

prattmic added the okay-after-rc1 Used by release team to mark a release-blocker issue as okay to resolve either before or after rc1 label Jun 14, 2023

rsc added the Proposal-FinalCommentPeriod label Jun 14, 2023

ianlancetaylor removed release-blocker okay-after-rc1 Used by release team to mark a release-blocker issue as okay to resolve either before or after rc1 labels Jun 14, 2023

rsc closed this as completed Jun 21, 2023

rsc changed the title ~~proposal: slices: Use ~[]E throughout~~ slices: Use ~[]E throughout Jun 21, 2023

rsc added Proposal-Accepted and removed Proposal-FinalCommentPeriod labels Jun 21, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

slices: Use ~[]E throughout #60546

slices: Use ~[]E throughout #60546

Merovius commented Jun 1, 2023 •

edited

bitfield commented Jun 1, 2023

Merovius commented Jun 1, 2023

earthboundkid commented Jun 1, 2023

ianlancetaylor commented Jun 1, 2023

griesemer commented Jun 1, 2023 •

edited

neild commented Jun 1, 2023

Merovius commented Jun 1, 2023 •

edited

awagner-iq commented Jun 13, 2023 •

edited

awagner-iq commented Jun 13, 2023

earthboundkid commented Jun 13, 2023

gopherbot commented Jun 13, 2023

eliben commented Jun 14, 2023

ianlancetaylor commented Jun 14, 2023

rsc commented Jun 14, 2023

ianlancetaylor commented Jun 14, 2023

rsc commented Jun 21, 2023

slices: Use ~[]E throughout #60546

slices: Use ~[]E throughout #60546

Comments

Merovius commented Jun 1, 2023 • edited

Proposal

Rationale

Cost

Alternatives considered

bitfield commented Jun 1, 2023

Merovius commented Jun 1, 2023

earthboundkid commented Jun 1, 2023

ianlancetaylor commented Jun 1, 2023

griesemer commented Jun 1, 2023 • edited

neild commented Jun 1, 2023

Merovius commented Jun 1, 2023 • edited

awagner-iq commented Jun 13, 2023 • edited

awagner-iq commented Jun 13, 2023

earthboundkid commented Jun 13, 2023

gopherbot commented Jun 13, 2023

eliben commented Jun 14, 2023

ianlancetaylor commented Jun 14, 2023

rsc commented Jun 14, 2023

ianlancetaylor commented Jun 14, 2023

rsc commented Jun 21, 2023

Merovius commented Jun 1, 2023 •

edited

griesemer commented Jun 1, 2023 •

edited

Merovius commented Jun 1, 2023 •

edited

awagner-iq commented Jun 13, 2023 •

edited