Skip to content

proposal: slices: new package to provide generic slice functions (discussion) #47203

rsc announced in Discussions
proposal: slices: new package to provide generic slice functions (discussion) #47203
Jul 14, 2021 · 21 comments · 163 replies

rsc
Jul 14, 2021
Maintainer

This discussion is meant to be for collecting feedback about #45955 in a more structured way.
Please comment here, and when things seem resolved, we'll move back to the issue.

Update: The proposal has been accepted. I've locked the discussion since it is done. Thanks everyone!

Replies

21 comments
·
163 replies

[Resolved: Left as Compact -rsc, July 21 2021]


I suggest we rename Uniq/UniqFunc to Compact/CompactFunc.

I had proposed UniqueAdjacent (I think some others did too). I still like the specificity of UniqueAdjacent, even if I'm not attached to that specific name. It's true that UniqueAdjacentFunc is not a short name, but with autocomplete I wouldn't care. Something that indicates adjacency in the name would be good.

I think I'd prefer to leave those functions out entirely. It seems clear from the debate over the naming and functionality that there isn't really a canonical definition of uniqueness that everyone can agree belongs in the package.

13 replies
@rsc

rsc Jul 14, 2021
Maintainer Author

Compact should not be bundled with sort. Sometimes you only want one.

@ianlancetaylor

I've changed the proposal to use Compact and CompactFunc.

@colin-sitehost

not to bikeshed, but I think rust had a good idea with dedupe: #47203 (reply in thread)

@Merovius

@colin-sitehost dedup was suggested before Russ called off the bike-shedding. There's also a bunch of specific replies to that suggestion in-between the two comments. Basically "Dedupe has exactly the same problems Uniq has, there is no indication that it only removes successive duplicates".

@rsc

rsc Jul 21, 2021
Maintainer Author

Resolved as Compact. Part of the point of using Compact is that it's not in other language's APIs, so we get to define the word without preexisting connotations.

[Resolved as Grow(n) and Clip. -rsc, July 21 2021]


Copying over my last comment to track discussion on the Reserve function (and possible elimination of Resize)

I wrote a comment about how unintuitive Resize (or Grow) would be for common use cases and how I think we should have a Reserve function in the API.

That comment remains largely unaddressed, possibly because a number of comments were rapidly added after mine, burying that part of the conversation.

I think @carlmjohnson had a good follow up comment about an Unreserve function.

Does anyone have a counterargument that Resize is actually a commonly useful function? As currently defined, it seems very error prone to use and unintuitive. Reserve is a very simple function that covers the primary use case for Resize that I’ve seen in practice… I would love to hear how other people’s experiences differ there, or to see Resize replaced with Reserve in the API.

17 replies
@mikeschinkel

Consistency within Go, vs. occasional consistency with Rust seems the better way to go? So if Grow() is used elsewhere for similar purposes in Go, and Go has yet(?) to use Reserve() for similar purposes then Grow() would seem preferable, at least to me. #fwiw

@coder543

I never said we should choose names to be consistent with Rust, just that I think Reserve is a strictly better name for this function.

I don't like the name Grow for this function, since it doesn't actually Grow the slice by the amount specified. A developer reads the word "Grow" and they think they know what is happening, but that isn't what is happening. However, using the name Grow to be consistent with prior implementations in Go is probably the right choice, which was my conclusion.

@Merovius

FWIW I also think Reserve is a better name and I think consistency like this is broken in a couple of places already¹. I'm not sure I feel that *bytes.Buffer.Grow is a prominent enough precedent to justify choosing the worse name. I could go either way on this.

[1] For example, I regularly want to call *bufio.Scanner.Scan() as Next().

@carlmjohnson

I have no strong feelings about the name Grow vs Reserve, but I do think Unreserve is useful, and I’m not sure of another good name for it. Maybe LimitGrowth?

@rsc

rsc Jul 21, 2021
Maintainer Author

Resolved as Grow(n) in latest API. Unreserve/Shrink is Clip.

bcmills
Jul 14, 2021
Maintainer

[Resolved: Removed from API. -rsc, July 21 2021]


(From #45955 (comment).)

I still think that the functional parts of the API (Map, Filter, and Reduce) are extremely premature at this juncture (#45955 (comment)). The justification that @ianlancetaylor gave for including them (in #45955 (comment)) is:

It seems to me that Map/Filter/Reduce come up a lot in discussions of generic code. And for real Go programs I think that covariance is a minor issue. But I'm open to discussion.

In #45955 (comment), I pointed out that coming up a lot in discussions is not the usual bar that we apply for additions to the Go standard library. I don't think that concern has been addressed, but again I may have missed it in the long discussion threads.

I would really like to see examples of proposed usage of these functions — especially as compared to equivalent for-loops — before those parts are accepted as part of the API. My hypothesis is that they will be extremely awkward in practice, and in the rest of the Go proposal project we bias toward leaving out unproven APIs, especially in the absence of detailed examples of how we expect those APIs to be used.

11 replies
@ajlive

Frankly I like upsetting Hacker News commenters.

@carlmjohnson

More serious comment: having an easy to use Clone and a Grow function for setting capacity makes Map less useful. I do sort of want a better Filter though because the current idioms are a bit verbose and there are more than one way to do it.

@colin-sitehost

yeah, I would much rather see a "proper iterator system", and I assume that would be a thing to investigate once we see how generics land?

@urandom

Like @DeedleFake I agree that these fumctions should not be added at all, but not because they are functional. In the long run, I think Go will benefit from an official package like Java's streams or C# LINQ. How such a package evolves is another discussion altogether. Perhaps a community package will arise that's good and stable, or one can be created in /x where it can marinate for a bit and mature.

@rsc

rsc Jul 21, 2021
Maintainer Author

Removed Map/Filter/Reduce from latest API.

bcmills
Jul 14, 2021
Maintainer

[Resolved: Added Clip to API. -rsc, July 21 2021]


I think the discussion from #45955 (comment) was also lost in the noise.

My original comment:

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.

@ianlancetaylor in #45955 (comment):

What should we call the "reduce cap to len" function?

My reply in #45955 (comment):

Perhaps TrimCap? It's vaguely related to the bytes.Trim functions but operates on capacity rather than length.

11 replies
@bcmills

bcmills Jul 14, 2021
Maintainer

s[:len(s):len(s)] is clear, really very easy to type, and hard to get wrong.

That's true, but less true as the variable name gets even marginally longer (because the expression increases at 3x the rate of the name).

It is of course possible to factor out a variable, but then you have to pick another (short, unused) variable name, which can add a lot of cognitive overhead in and of itself.

To use some real examples:


Today, with a per-package copy of this function:

rootModules: capVersionSlice(rootModules),

As an explicit expression:

		rootModules: rootModules[:len(rootModules):len(rootModules)],

(I find that one frankly hard to even parse.)

As slices.Shrink:

		rootModules: slices.Shrink(rootModules),

Today:

mg.buildListOnce.Do(func() {
mg.buildList = capVersionSlice(mg.g.BuildList())
})

Expression:

	mg.buildListOnce.Do(func() {
		bl := mg.g.BuildList()
		mg.buildList = capVersionSlice(bl[:len(bl):len(bl)])
	})

slices.Shrink:

	mg.buildListOnce.Do(func() {
		mg.buildList = slices.Shrink(mg.g.BuildList())
	})
@bcmills

It can always be added later if we can make the case that it's very important.

That's true, but putting it off makes #38081 (comment) feel like a bit of a bait-and-switch. 😒

@rsc

rsc Jul 14, 2021
Maintainer Author

"We should wait for generics before deciding to make it a language change" and
"we should wait for generics to settle more before deciding this is important enough to put in package slices"
can both be true.
It's not really a bait-and-switch, just taking new APIs slowly.

@carlmjohnson

This was on the wrong thread: #47203 (reply in thread)

I’m happy with the pair of names Grow([]T, int) and Shrink([]T).

I feel like I don’t know if I would use Map or not, but I’m 100% sure I’d use Grow and Shrink if they existed.

@rsc

rsc Jul 21, 2021
Maintainer Author

Talked to @ianlancetaylor who had a strong reaction against Shrink. We ended up with Clip instead, although "Pollard" was a fascinating alternative.

jimmyfrasche
Jul 14, 2021
Collaborator

[Resolved: Decided to leave this out - IndexFunc suffices for now. -rsc, July 21 2021]


This got lost in the original thread but I've often found these useful:

func Any[T any](vs []T, p func(T) bool) bool {
  for _, v := range vs {
    if p(v) {
      return true
    }
  }
  return false
}

func All[T any](vs []T, p func(T) bool) bool {
  for _, v := range vs {
   if !p(v) {
     return false
   }
  }
  return true
}

Any(vs, p) is p(vs[0]) || p(vs[1]) || ··· || p(vs[len(vs)-1]) and All(vs, p) is p(vs[0]) && p(vs[1]) && ··· && p(vs[len(vs)-1])

js calls them some/every but I want to say that any/all are the more common names, though I haven't done a survey.

14 replies
@colin-sitehost

yeah, sorry for the double post; but the Any caught me off guard too

@ajlive

I agree, but personally think that's a reason to have neither.

Fine with me too. For some reason I think Index is harder to screw up than is Any/Contains vs. All/ContainsOnly.

@carlmjohnson

I'm tempted to publish a package called truthy with Any/All funcs and maybe some sort of First function so you could write if truthy.Any(myStrings) { return truthy.First(myStrings) } etc. ISTM that Any/All don't really need to be in the slices package per se, and in languages like Python/JavaScript any and all benefit greatly from a concept of truthiness.

@rsc

rsc Jul 21, 2021
Maintainer Author

FWIW @carlmjohnson if you write if Any { return First } then you end up doing 2X the work you really need.

@rsc

rsc Jul 21, 2021
Maintainer Author

Resolved to leave these out. We already have IndexFunc. We dropped ContainsFunc as not common enough, but it can always be added later.

[Resolved: Deleted ContainsFunc for now. -rsc, July 21 2021]


credit to @Merovius
#45955 (comment)

I would rather see the more generic form of ContainsFunc that matches IndexFunc:

// ContainsFunc is like Contains, but it uses a comparison function.
func ContainsFunc[T any](s []T, f func(T) bool) bool

And still reads well at call sites:

var t []time.Time
ok := slices.ContainsFunc(t, time.Unix(1626299610).Equals)
ok = slices.ContainsFunc(t, time.Time.IsZero)
4 replies
@colin-sitehost

If this is unacceptable, I think we must use two Ts:

// ContainsFunc is like Contains, but it uses a comparison function.
func ContainsFunc[T1,T2 any](s []T1, v T2, cmp func(T1, T2) bool) bool

Since being able to express this is also important:

ok := slices.ContainsFunc([]string{"one", "two"}, 'o', strings.ContainsRune)

And yeah, we can still do this pretty well:

ok := slices.ContainsFunc([]time.Time{time.Now()} time.Unix(1626299610), time.Time.Equals)

EDIT: though as @Merovius called out, this is nearly impossible to express clearly:

ok := slices.ContainsFunc([]time.Time{time.Now()}, struct{}, func(t time.Time, _ struct{}) bool { return t.IsZero() } )
@Merovius

ok := slices.ContainsFunc([]string{"one", "two"}, 'o', strings.ContainsRune)

What if the arguments in ContainsRune where swapped? You'd still need a closure. I'm not sure why we should assume that the order of arguments for the comparison-function is the one that is beneficial for this form of ContainsFunc, for the operations people want to use it.

And yeah, we can still do this pretty well:

Yes, but you are basing that argument on an actual equality function. The argument is that it's easy to express a boolean predicate using an equality-function (and even easier using a method, as you demonstrate), but hard to do it the other way around.

Try using something like time.Time.IsZero instead.

@colin-sitehost

agreed, I strongly prefer the predicate form that matches IndexFunc, but if that is unacceptable for some reason, I think we must not require a single T any for both the s and v. sorry to muddy the waters.

EDIT: after working through an example, if we have T1,T2, you can use struct{} to obviate which parameter is ignored, but yeah it is not good.

@rsc

rsc Jul 21, 2021
Maintainer Author

We resolved this by deleting ContainsFunc at least for now. I agree with you that it should match IndexFunc, but it probably doesn't provide enough beyond IndexFunc to add. We can always add it later.

Linking again to my Google Sheet comparing names of Python/JavaScript slice methods: https://docs.google.com/spreadsheets/u/0/d/1SFHxz7u8ufnORtBpu63vRGCQSbyA3dqYHgz4eX6osas/htmlview

9 replies
@Merovius

FWIW, IMO consistency with other languages is a low priority. Sure, if we have multiple good options for names, might as well choose the more common one. But if we think a name is better, "other languages are using a different one" shouldn't dissuade us.

PartialOrd not Compare (and language primitive not func)

Compare imposes a total order, so this seems wrong. (Also, is PartialOrd a language primitive? Isn't it a trait?)

Index is implemented as binary_search

That's not the same function then. It's strictly less powerful, as it makes strictly more assumptions about the input.

@colin-sitehost

FWIW, IMO consistency with other languages is a low priority. Sure, if we have multiple good options for names, might as well choose the more common one. But if we think a name is better, "other languages are using a different one" shouldn't dissuade us.

yep, just calling out differences as a summary; no pressure to change anything. (well maybe dedupe)

Compare imposes a total order, so this seems wrong. (Also, is PartialOrd a language primitive? Isn't it a trait?)

I am simplifying things, but yeah; and i think std::cmp::Ord is what i should have said.

That's not the same function then. It's strictly less powerful, as it makes strictly more assumptions about the input.

fair, feel free to leave it off; it felt like it met the spirit, but there is probably something in std::iter::Iterator that fits better.

@carlmjohnson

I think the main input of other languages is if N languages use some name for some function, if Go uses the same name it should be equivalent, not different, because it causes confusion. So “Uniq” is not great because it might mean compact or it might mean toSet.

@carlmjohnson

The other thing to take away from other languages are that people like/use these functions, but I suppose they can be saved for 1.19+.

@rsc

rsc Jul 21, 2021
Maintainer Author

FWIW, Index/IndexFunc is not binary search.

cespare
Jul 15, 2021
Collaborator

[Resolved: Added Clone. -rsc, July 28 2021]


One function that seems natural to include is

// Copy creates a new slice that is a copy of s.
func Copy[T any](s []T) []T

(or it could be called Clone).

What I would usually write today is

copied := append([]T(nil), s...)

which isn't too bad, but is still a rather dense and busy line for such a basic operation.

5 replies
@carlmjohnson

This has been proposed under the name Clone. strings/bytes.Clone is coming in 1.17, so it’s a pretty sure bet for slices too.

@cespare

Thanks, I had missed that.

Looks like #45038 was indeed accepted, but never implemented, so I guess it will be in 1.18.

@rsc

rsc Jul 21, 2021
Maintainer Author

I forgot to bring this up at the proposal review but I have it noted for next week.

@ianlancetaylor

Given that we will soon have strings.Clone and bytes.Clone, I am also in favor of

// Clone returns a shallow copy of s.
func Clone[T any](s []T) []T
@rsc

rsc Jul 28, 2021
Maintainer Author

Resolved by adding Clone.

[Resolved: We agree. -rsc, July 28 2021]


Proposal: 1.18 should have a slices package that contains only a subset of functionality that has strong consensus for being useful. At the same time golang.org/x/exp/slices is released with all the same functions plus the more controversial ones (definitely Map and Filter, maybe others?). After a year or so, the controversial functions can get an up or down decision on inclusion in the standard library.

3 replies
@carlmjohnson

Is Reduce still in the proposal? That definitely shouldn’t be in the 1.18 standard library. :-P

@rsc

rsc Jul 15, 2021
Maintainer Author

I've already commented multiple times that this is the approach - just the parts that clearly belong because they are obviously the right API and have widespread applicability. We are not going to make an x/exp/slices though. Other people can experiment with APIs in their own libraries.

@rsc

rsc Jul 28, 2021
Maintainer Author

Resolved: we agree.

[Resolved: Decided not to add in the initial set. -rsc, July 28 2021]


I’d like to see Concat(dest []T, ss ...[]T) []T.

12 replies
@carlmjohnson

I also think this is probably below the bar because while obviously, I use strings.Join all the time, I can't think of the last time I needed a non-string/bytes join. I think if we didn't have Insert and Delete, you could just have Concat and tell people to use that instead, but this doesn't seem to be a popular idea.

But maybe @go101 wants to argue for Concat, on the grounds that it could use some unsafe trickery to be faster than manually appending.

@neild

I see uses of append that inappropriately reuse the target slice semi-regularly, along the lines of:

return SomeType{
  A: append(s, v1...),
  B: append(s, v2...),
}

While this isn't difficult to write correctly, a slices.Concat that creates a new slice would be useful for this case.

@carlmjohnson

The bug could also be addressed with:

return SomeType{
  A: append(slices.Clip(s), v1...),
  B: append(slices.Clip(s), v2...),
}

😄

@randall77

Well, not quite. If v1 or v2 might be empty, then A and B might still alias s (or each other), which may not be what is intended.

@rsc

rsc Jul 28, 2021
Maintainer Author

Resolved: decided not to add Concat in the initial set. We can always reconsider if there is significant evidence.

rsc
Jul 21, 2021
Maintainer Author

Update, July 21 2021

GitHub Discussions seem to be working much better than regular issues.
Thanks everyone for being thoughtful in posting and being careful about replying and duplicates.

Based on the discussion, we have made the following changes to the proposed API:

  • Deleted ContainsFunc (too rarely needed, arguably wrong API, can always use IndexFunc instead)
  • Deleted Map, Filter, Reduce (probably better as part of a more comprehensive streams API somewhere else)
  • Changed Resize(newLen) to Grow(n), following bytes.Buffer.Grow's semantics: arranges for cap to be at least len+n.
  • Added Clip as the opposite of Grow: drops all the unused capacity.
  • Merged DeleteSlice(s,i,j) and Delete(s,i) into just Delete(s, i, j) (less likely to encourage accidentally quadratic behavior)

I have also added [Resolved] notes at the top of comments that we consider resolved, in addition to replying with text like "Resolved as/by ...". (I hope GitHub will introduce the concept of a resolved comment at some point.)

The suggestions about Clone and Concat are not resolved: we will do those next week. My guess is Clone will be added and Concat will not.

1 reply
@cespare

cespare Jul 21, 2021
Collaborator

You can hide a comment (or the whole thread? haven't tried it) with the reason being "Resolved".

Edit: It just hides that comment, not the thread underneath, so maybe it's not that useful. Shame.

[Resolved: Decided not to add sequence operations. -rsc, July 28 2021]


The new reduced API looks great!

This may have gotten lost in the discussion in the original issue, so I'll risk repeating it:

Should Index and Contains accept a subslice instead of a single value? IndexFunc would continue to operate on func(T) bool.

package slices

func Index[T comparable](s, subslice []T) int
func IndexFunc[T any](s []T, f func(T) bool) int
func Contains[T comparable](s, subslice []T) bool

Besides satisfying more use cases, this also maps more closley to what the strings and bytes packages already offer:

package bytes

func Index(s, sep []byte) int
func IndexFunc(s []byte, f func(r rune) bool) int
func Contains(b, subslice []byte) bool
package strings

func Index(s, substr string) int
func IndexFunc(s string, f func(rune) bool) int
func Contains(s, substr string) bool
7 replies
@colin-sitehost

I mean, you could want something or implement something "more sophisticated", but if all you are asking for is yes/no Contains or Index as it is defined in bytes, strings, and the draft proposal, it should just be a linear order search.

@Merovius

I don't like the varargs form - to me, that strongly suggests ContainsAny semantics, not searching for a sequence of elements.
I agree that wrapping a single element is inconvenient, though. But maybe that just means we should have separate functions.

@carlmjohnson

strings.Index and bytes.Index switch to internal/bytealg.IndexRabinKarp when the slice and subslice lengths are longer than some system specific MaxLen. I don't see why that same logic wouldn't apply to slices in general.

@rsc

rsc Jul 23, 2021
Maintainer Author

General arrays and strings are different things.
You are almost always looking for one element of an array, not a subsequence.
The subsequence is too much complexity for not enough benefit.

@rsc

rsc Jul 28, 2021
Maintainer Author

Resolved: decided not to add sequence operations here, leaving API about elements.

[Resolved: Panics are OK when the corresponding language operations would panic. -rsc, July 28 2021]


I prefer panics to be reserved for situations where it is not safe to continue. Are these functions using panics for optimising for performance and so we will have to wrap the stdlib functions (like I do for the errors package with a null checking version) where personally I believe panic handling to be itself, more of a risk than additional checks and error handling, considering the panic could be anything from the world and not just the path that you are expecting.

Could panic free e.g. length checking alternatives be considered to be part of the package?

30 replies
@Merovius

@mikeschinkel You are correct that I was just stating opinions, not providing evidence or proof. That's, as far as I'm concerned, all we can do here - though I would certainly accept evidence or proof that what I say is wrong. Meanwhile, I don't think being an opinion disqualifies my comments or that it's reasonable to dismiss them on purely formal grounds (i.e. calling every sentence of it a fallacy), instead of taking its content into consideration.

You are also correct that I phrase my opinion as absolute statements. I do that, to emphasize that my opinion is that there really are things which are not in any sort of gray area and that my opinion is, that the functions in this proposal are such things. That is, I'm trying to say "I have an opinion about something being absolute", not "my opinion is absolute truth". It's a subtle difference and I apologize for not making it more clear.

I don't really know how to address the rest of your response, except as by pointing out that there is also a fallacy fallacy: Assuming that because someone commits a logical fallacy, they must be wrong. Saying someone commits a logical fallacy is not, in itself, an argument that they are wrong.

Apart from that, I tried to explain why I think panicing is appropriate above and I'll just leave the thread at this point.

@mikeschinkel

@Merovius — 

"I don't really know how to address the rest of your response, except as by pointing out that there is also a fallacy fallacy: Assuming that because someone commits a logical fallacy, they must be wrong.""

I was not necessarily stating that you were wrong in specific cases, instead I was calling out your frequent use of fallacious arguments in reply to me as well as many others. I wouldn't have called it out except that you repeatedly misrepresented my argument about Go being pragmatic.

That said, @ianlancetaylor had a good point in his comment just before your most recent reply.

@rsc

rsc Jul 28, 2021
Maintainer Author

Resolved: panics are OK where the analogous language operations would panic.

@kevlar700

I guess I will agree to disagree. I don't believe the underlying language should panic either, actually. If it has a trustable length, then it should use it to avoid panics that may have an immeasurable detrimental affect.

@beoran

This is open source. We can always make a non panicking version of this package once it is done.

Do we want a maps package? A sets package? If so, is now the time to propose them, so they can be harmonized with slices?

Edit: Resolved below.

1 reply
@rsc

rsc Jul 23, 2021
Maintainer Author

ianlancetaylor
Jul 23, 2021
Maintainer

[Resolved: Yes, we will allow named slice types. -rsc, July 28 2021]


One thing we need to consider is whether to handle defined slice types. Specifically, if a function like Insert is passed a defined type, should it return the same type? Right now the proposal is for

func Insert[T any](s []T, i int, v ...T) []T

Now consider:

type Durations []time.Duration
func (s Durations) String() string { ... }
func PushAndPrint(s Durations, v time.Duration) {
    // Insert will return []time.Duration, not Durations,
    // so fmt.Println will not invoke the Durations.String method.
    fmt.Println(slices.Insert(s, 0, v))
}

The other approach is to use constraint type inference, which looks like this:

func Insert[T any, S interface { []T }](s S, i int, v ...T) S

This will do the right thing for the Durations example. Normally function and constraint type inference will apply so that nobody needs to write out the type arguments. But the downside is that the function signature is harder to read.

In the current proposal this applies to Insert, Delete, Compact, CompactFunc, Grow, and Clip.

Thoughts?

CC @griesemer

8 replies
@ianlancetaylor

Yes, we should be able to do it in either order.

I don't know that the Slice constraint should be part of the exported API of this package.

@jimmyfrasche

constraints.Slice[T]

@rsc

rsc Jul 23, 2021
Maintainer Author

Accidentally created a new comment thread for constraints.Slice[T], although perhaps that's for the best: #47203 (comment).

(The two reply boxes are right next to each other!)

@griesemer

Constraint type inference does work on the playground, but the implementation there hasn't changed for 1/2 year or so. So one has to use the old syntax and perhaps not all refinements are available.

Still this specific example of a possible Insert actually works and does what is expected.

(Sometimes it times out, but every once in a while it makes it through.)

@rsc

rsc Jul 28, 2021
Maintainer Author

Resolved: yes, we will add support for named slice operations.
Also tentatively adding constraints.Slice to the constraints proposal.
It is true that we can write interface{~[]Elem} instead of constraints.Slice[Elem],
but the latter may be much readable for consumers of APIs
(reading the type signature to understand the function -
consumers of generic code, not authors of generic code).

rsc
Jul 23, 2021
Maintainer Author

[Resolved: Will add to constraints proposal. -rsc, July 28 2021]


I don't know that the Slice constraint should be part of the exported API of this package.

I definitely don't want people writing slices.Slice[T] instead of []T.
But it doesn't do that (phew),
and I wonder if people will naturally want to write similar constraints for their own code that is generic over slices.
It seems like maybe it would make sense to provide somewhere?
constraints.Slice[Elem] and constraints.Map[Key,Value]?

func Insert[Slice constraints.Slice[Elem], Elem any](s Slice, i int, v ...Elem) Slice

?

9 replies
@tooolbox

What about func Insert[Slice ~[]Elem, Elem any](s Slice, i int, v ...Elem) Slice? Concise and clear.

@griesemer

You still need an interface, though:

func Insert[Slice interface{~[]Elem}, Elem any](s Slice, i int, v ...Elem) Slice

(https://go2goplay.golang.org/p/_DGAo_m5sh5)

(Maybe at some point in the future we can show that ~[]Elem is equivalent to interface{~[]Elem} but we're not there yet (and won't be for Go 1.18).

@tooolbox

You still need an interface, though. Maybe at some point in the future we can show that ~[]Elem is equivalent to interface{~[]Elem} but we're not there yet (and won't be for Go 1.18).

I'm curious what you see as the barrier exactly? Is it conceptual, lack of formal proof, implementation work?

I'm trying to think how, in the context of type parameters, ~T is not equivalent to interface{ ~T } but I'm drawing a blank.

It should be true that type parameter T always has the same type set (as per #45346) as interface{ T }. For example the type set of int and interface{ int } are the same, just like fmt.Stringer and interface{ fmt.Stringer }.

Print[T fmt.Stringer](t T)              // Legal.
Print[T interface{ fmt.Stringer }](t T) // Legal, unnecessary.
Print[T interface{ int }](t T)          // Legal, but silly.
Print[T int](t T)                       // Not legal.  Also, silly.
Print[T interface{ ~int }](t T)         // Legal.
Print[T ~int](t T)                      // Not legal, but why shouldn't it be?

Why should I be able to use interface{ int } as a meta type, but not ~int? The former is nonsensical, the latter is useful. Perhaps instead of "meta types must be interfaces", we can adopt "meta types must have a type set comprising more than one type". I'd rather the compiler errored because "interface{ int } matches a single type" rather than "approximation element ~int is not allowed outside an interface".

@griesemer

We've considered the possible equivalence of interface{~T} and ~T when working on the type set approach. The "obvious" difference at the moment is that T and A | B (for types) is simply not syntactically permitted outside an interface.

But there's a more subtle issue. One of the goals of the type set approach is that eventually we might be able to use "constraint" interfaces as ordinary (non-constraint) types; as in: var x interface{~int}. If that were permitted, there seems to be a difference between var x interface{~int} and var x ~int: For the former, the zero value would be nil (that's the zero values for interfaces), but for the latter it probably should be 0. (This is even more obvious when choosing the non-sensical interface{int} type.)

For constraints, the interface zero value doesn't matter - a type parameter is not an interface, the interface is simply describing the properties of the type parameter. So perhaps one should be able to just write [T ~int] - it certainly would be nice. But for now we decided to err on the side of caution and stick with always requiring an interface, albeit with the extended mechanism for embedding of elements.

But let's keep discussing this elsewhere, it's not directly related to the slices proposal. Thanks.

@rsc

rsc Jul 28, 2021
Maintainer Author

Resolved: will add constraints.Slice to the constraints proposal.

[Resolved: Will make EqualFunc take two different slice type parameters. -rsc, July 28 2021]


I'll advocate for this one more time, since it's a bit hard to tell whether it was missed or decided against:

The kinds of comparison loops that I often end up writing (or, at least, the ones that I notice) are often comparing a slice of keys against a slice of a compound type using a specific field (e.g. a list of IDs with a list of users) or primitive types against some kind of named type (e.g. strings and thrift-generated named strings). In tests, there are also cases where cmp and a Transformer is used to run these kinds of equality checks that could be simplified using a dual-typed EqualFunc. For these cases, I think that the Func varieties should accept two type parameters.

I think this holds true for EqualFunc, and by analogy also to CompareFunc. I think that's it at the moment, but I think it will apply any time there are two slice parameters.

I don't think it's all wins, but I think the pros of making this change outweigh the cons:

  • Pro: In all cases I was able to construct in go2goplay, the types were inferred, so the call-site is identical to a single parameter
  • Pro: Can write more flexible equality functions without loss of clarity for simple cases
  • Pro: The required func type be will be understood from the types of the slices, so the error messages are already helpful
  • Con: If the type is not inferred somehow, then you have to specify two types, which is probably annoying if they're the same
  • Con: Most non-identically typed EqualFunc params are likely to be closures, so it's not saving many lines vs a for loop

Also, I suppose:

  • Con: I can write this myself in my own package if I want to
  • Pro: I suspect that this is one of the helpers that will come up a lot in people's local helper libraries, so having it in one place is nice

https://go2goplay.golang.org/p/82l-NfVxPui (includes naive implementation)

type User struct{ ID int64 }

func main() {
	// Different Types
	t1 := []int64{1, 2, 3, 4}
	t2 := []int{1, 2, 3, 4}
	fmt.Println(EqualFunc(t1, t2, func(a int64, b int) bool { return a == int64(b) }))

	// Same Type
	t3 := []string{"pod1", "pod2"}
	t4 := []string{"POD1", "POD2"}
	fmt.Println(EqualFunc(t3, t4, strings.EqualFold))

	// Field
	t5 := []User{{1}, {2}, {3}}
	t6 := []int64{1, 2, 3}
	fmt.Println(EqualFunc(t5, t6, func(a User, b int64) bool { return a.ID == b }))
}

// Output:
//   true
//   true
//   true

Original comments for more detail:

2 replies
@kylelemons

Oh, also, the proposed maps package takes two value types for its EqualFunc so it seems like that would carry over here.

#47330

@rsc

rsc Jul 28, 2021
Maintainer Author

Resolved: will change EqualFunc to take two different kinds of slices.

rsc
Jul 28, 2021
Maintainer Author

Update, July 28 2021

Based on the discussion, we will make the following changes to the proposed API:

  • Added Clone (matching bytes.Clone, strings.Clone).
  • Decided against Concat (not enough evidence of need)
  • Changed EqualFunc to accept two different slice types.
  • Changed all functions to accept named slice types
    • Added constraints.Slice to support more readable slice type parameters.
  • Decided that panics in the API are OK where the analogous language operations would panic.
  • Decided against sequence-based Index/Contains.

I have also added [Resolved] notes at the top of comments that we consider resolved, in addition to replying with text like "Resolved...".

@ianlancetaylor is going to update the proposal text.

At this point I believe all the suggestions to date have been resolved and that we could potentially move the proposal to likely accept next week.

0 replies

[Resolved: Will leave IndexFunc as is -rsc, August 4 2021]


About IndexFunc: Can we inform the function f regarding the element index in the array? It would be more useful for the IndexFunc because we might also interested in the location of the element of the slice.

-func IndexFunc[T any](s []T, f func(T) bool) int
+func IndexFunc[T any](s []T, f func(T, int) bool) int
6 replies
@rsc

rsc Aug 2, 2021
Maintainer Author

Yes, just like strings.IndexFunc and bytes.IndexFunc do today.

@changkun

The IndexFunc of strings, bytes are as-is today for sure, but - as a generic package - shouldn't it be handier if it covers more use cases? Pass one more index seems does not hurt anything, does it?

We may argue it has more effort in writing the body, but since we have autocompletion today and users don't even have to worry about the callback signature by just typing fun then hit the enter key.

@Merovius

@changkun

Pass one more index seems does not hurt anything, does it?

Yes, because it means you can no longer pass predicate functions (e.g. (time.Time).IsZero, (*net.URL).IsValid,…) directly, but have to wrap them.

@beoran

@changkun
While an index might be handy here, It is not consistent with existing standard library fuctions. I also disagree with your code completion argument.

Not everyone uses an IDE with code completion. I use old or minimally powered Linux computers and develop in a terminal with a text mode editor. Please consider that there are people who cannot afford high performance systems and expensive commercial IDEs.

@rsc

rsc Aug 4, 2021
Maintainer Author

Resolved: will leave the current, index-free IndexFunc callback.

rsc
Aug 4, 2021
Maintainer Author

Update, August 4 2021

There are no changes this week. One comment (about IndexFunc) was resolved in favor of the status quo.
The proposal itself has moved to likely accept.

0 replies

rsc
Aug 11, 2021
Maintainer Author

Update, August 11 2021

The proposal #45955 has been accepted.
This discussion worked very nicely.
Thanks everyone!

0 replies
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Category
Discussions