We propose to add the following functions to package slices, to provide good support for code using iterators. This is one of a collection of proposals updating the standard library for the new 'range over function' feature (#61405). It would only be accepted if that proposal is accepted. See #61897 for a list of related proposals.
All serves as a “source” for iterators.
// All returns an iterator over index-value pairs in the slice.
// The indexes range in the usual order, from 0 through len(s)-1.
func All[Slice ~[]Elem, Elem any](s Slice) iter.Seq2[int, Elem] {
return func(yield func(int, Elem)bool) bool {
for i, v := range s {
if !yield(i, v) {
return false
}
}
return true
}
}
Backward can be used to replace existing 3-clause loops that iterate backward over a slice manually. This happens fairly often in certain algorithms (for example it happens a lot in the compiler’s SSA code).
// Backward returns an iterator over index-value pairs in the slice,
// traversing it backward. The indexes range from len(s)-1 down to 0.
func Backward[Slice ~[]Elem, Elem any](s Slice) iter.Seq2[int, Elem] {
return func(yield func(int, Elem)bool) bool {
for i := len(v)-1; i >= 0; i-- {
if !yield(i, v[i]) {
return false
}
}
}
}
Values is like All: not terribly useful by itself but useful as a source for other code.
// Values returns an iterator over the values in the slice,
// starting with s[0].
func Values[Slice ~[]Elem, Elem any](s Slice) iter.Seq[Elem] {
return func(yield func(Elem)bool) bool {
for _, v := range s {
if !yield(v) {
return false
}
}
return true
}
}
Append and Collect serve as “sinks” for iterators.
// Append appends the values from seq to the slice and returns the extended slice.
func Append[Slice ~[]Elem, Elem any](x Slice, seq iter.Seq[Elem]) Slice {
for _, v := range seq {
x = append(x, v)
}
return x
}
// Collect collects values from seq into a new slice and returns it.
func Collect[Elem any](seq iter.Seq[Elem]) []Elem {
return Append([]Elem(nil), seq)
}
Sorted and SortedFunc collect an iterator and then sort the contents:
// Sorted collects values from seq into a new slice, sorts the slice, and returns it.
func Sorted[Elem comparable](seq iter.Seq[Elem]) []Elem {
slice := Collect(seq)
Sort(slice)
return slice
}
// SortedFunc collects values from seq into a new slice, sorts the slice, and returns it.
func SortedFunc[Elem any](seq iter.Seq[Elem], cmp func(Elem, Elem) int) []Elem {
slice := Collect(seq)
SortFunc(slice, cmp)
return slice
}
Comment From: seankhliao
Concat takes a a variadic second arg #56353 Should Append and Collect (and Values?) do the same?
Comment From: mohamedattahri
@rsc – Any reason why ~these~ some of these shouldn't live in an iterators package of their own? It seems inconsistent to have functions in slices where the first arg is not a slice.
Comment From: earthboundkid
@rsc – Any reason why ~these~ some of these shouldn't live in an
iteratorspackage of their own? It seems inconsistent to have functions insliceswhere the first arg is not aslice.
I think this makes sense here. The iters package would define the iter.Iter type and things like Map, Filter, TakeWhile, and Zip that don't deal with particular iterator sources. You import slices when you want to convert an iter.Iter to/from a slice, and e.g. maps.Keys when you want to iterate over a map.
Comment From: DeedleFake
Values() seems like it would be redundant, other than as a convenience, I suppose, if a hypothetical iter package provided something like
// Better name pending.
func SecondRet[T1, T2 any](iter Seq2[T1, T2]) Seq[T2] {
return func(yield func(T2) bool) {
for _, v := range iter {
if !yield(v) {
return false
}
}
}
}
Either that or All() yielding the index is redundant if an Enumerate() implementation is added, too.
Also, two more functions that I'd like to suggest:
// SortInto places the elements of iter into the already sorted slice dst, expanding as necessary, and returns the resulting slice, also sorted.
func SortInto[S ~[]E, E cmp.Ordered](dst S, seq Seq[E]) S
func SortIntoFunc[S ~[]E, E any](dst S, seq Seq, cmp func(E, E) int)
And Sorted() should have a cmp.Ordered constraint, not comparable.
Comment From: rsc
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
Comment From: hherman1
I’m a little nervous looking at this that someone is going to immediately release a fluent API for these which will be preferred by the community, and STL will be left with a less used package. E.g
stream.New(iter).
Filter(…).
Map(…).
and so on. Maybe it’s ok if that ends up happening, but seems a bit sad.
Comment From: zephyrtronium
@hherman1 If it's any comfort, Map in particular doesn't work as a method because of #49085, so it seems unlikely that such a package will grow especially popular.
Comment From: hherman1
That’s both comforting and distressing :) The ergonomics of composing iterators seem a bit rough without a fluent api, but maybe I’m thinking too much about Java streams.
Comment From: willfaught
Please add syntax highlighting to your code blocks. With it, you might have noticed that Sorted should be SortedFunc here:
// SortedFunc collects values from seq into a new slice, sorts the slice, and returns it.
func Sorted[Elem any](seq iter.Seq[Elem], cmp func(Elem, Elem) int) []Elem {
It seems like the functions that return iter types should be in the iter package, so they can be grouped under the Seq/Seq2 types in the generated documentation. These are technically "constructors" for those types in that sense. The functions that take iter types also seem like they belong in iter, as utility functions that work on iter types. I'm reminded of the io package, which declares Reader and various functions that produce and consume Readers.
Slices are built into the language, so it doesn't seem like a function producing or consuming a slice alone warrants it being in the slices package. The new go/token.File.Lines method returns a slice, yet I doubt it was ever considered whether it belonged in the slices package (being a method aside).
Comment From: hherman1
I dont mind the colorless code blocks. The tone there also seems a bit rude @willfaught
Comment From: willfaught
The tone there also seems a bit rude @willfaught
My apologies.
Comment From: leaxoy
In most language, the All function should be Enumerate, why provide a counter-intuitive function in go? And should provide a function turn slice to Seq, for example:
func Iter[E any](slice []E) iter.Seq[E] {
...
}
// and for enumerate
func Enumerate[E any](slice []E) iter.Seq2[int, E] {
// or if we had tuple type, return should be iter.Seq[(int, E)]
// Again, I personally think that Seq2 is a very unwise design
...
}
Comment From: DeedleFake
@leaxoy
I think you're forgetting the context. The function isn't All(); it's slices.All(). Enumerate() is the usual name for a function that takes an existing iterator and adds indices. For a function that takes a slice and iterated over it, I think All(), while not necessarily the best name, is more clear than Enumerate() would be.
Comment From: ChrisHines
I had not paid close attention to the names of the functions this proposal wants to add so far. In https://github.com/golang/go/issues/61626#issuecomment-1672096753, @rsc gives an example use as follows.
use(slices.Sorted(maps.Keys(m))
Somehow knowing that maps.Keys would return an iterator, but not having fully digested this proposal I was a bit disoriented. I wasn't expecting slices.Sorted to accept an iterator. The name just doesn't seem to convey that at first. The two concepts the name conveys are "slices" and "sorting".
I think that my initial confusion when reading the call site without having invested in already knowing the details of the slices.Sorted signature may be a sign that the name isn't quite right. How carefully chosen is that name? Can we do better?
Comment From: Merovius
@ChrisHines I think it's fairly common for a function to be named after what it returns and what it does, but less so after what it takes. slices.Sort sorts a slice (it's named after what it does) and slices.Sorted returns a sorted slice (it's named after what it returns).
There is also precedence: In python, sorted is a function taking an iterable and it returns a sorted list. And sort is a method on lists (and other containers) that sorts the list in-place.
To me, this seems fine.
Comment From: earthboundkid
Besides Python, JavaScript has Array.toSorted which returns a new Array that was sorted. So, two languages at least where "sort" means in place and "sorted" means "new slice/list/array".
Comment From: earthboundkid
Does Sorted need a stable variant? It does seem unfortunate to have so many sort variants:
- sort.Sort
- slices.Sort
- slices.SortFunc
- slices.SortStableFunc
- slices.Sorted
- slices.SortedFunc
- slices.SortedStableFunc
cc @eliben
Comment From: eliben
Python's sorted is guaranteed to be stable, so they only have one sorted (not sorted and sortedstable) but that one sorted is stable
Comment From: willfaught
func Sorted[Elem comparable](seq iter.Seq[Elem]) []Elem {
slice := Collect(seq)
Sort(slice)
return slice
}
I'm not a sorting expert, but I'm curious if using an online sorting algorithm here could be an improvement. There could be delays between iterations.
Comment From: earthboundkid
The heap package is in need of a total overhaul. It could incorporate iterators if that happened.
Comment From: earthboundkid
Maybe slices.SortedFunc should be stable by default. Anyone who wants a faster sort can write it manually, and stability bugs are more likely to matter in production than minor performance hits.
Comment From: rsc
Finishing this proposal discussion is blocked on https://github.com/golang/go/issues/61405.
Comment From: gopherbot
Change https://go.dev/cl/558737 mentions this issue: slices: add All, Backward, Values, Append, Collect, Sorted, SortedFunc
Comment From: rsc
Given slices.SortFunc exists and is unstable, it would be inconsistent for slices.SortedFunc to be stable. It would be especially annoying when moving between the two that the semantics change. If you replace a use of a stable SortedFunc with an unstable SortFunc, you'd be sad.
Given that slices.SortStableFunc exists, we should probably also add slices.SortedStableFunc to complete the set, so people don't have to remember which exist and which don't.
Comment From: rsc
Have all remaining concerns about this proposal been addressed?
// All returns an iterator over index-value pairs in the slice.
// The indexes range in the usual order, from 0 through len(s)-1.
func All[Slice ~[]Elem, Elem any](s Slice) iter.Seq2[int, Elem]
// Backward returns an iterator over index-value pairs in the slice,
// traversing it backward. The indexes range from len(s)-1 down to 0.
func Backward[Slice ~[]Elem, Elem any](s Slice) iter.Seq2[int, Elem]
// Values returns an iterator over the values in the slice,
// starting with s[0].
func Values[Slice ~[]Elem, Elem any](s Slice) iter.Seq[Elem]
// Append appends the values from seq to the slice and returns the extended slice.
func Append[Slice ~[]Elem, Elem any](x Slice, seq iter.Seq[Elem]) Slice
// Collect collects values from seq into a new slice and returns it.
func Collect[Elem any](seq iter.Seq[Elem]) []Elem
// Sorted collects values from seq into a new slice, sorts the slice, and returns it.
func Sorted[Elem comparable](seq iter.Seq[Elem]) []Elem
// SortedFunc collects values from seq into a new slice, sorts the slice, and returns it.
func SortedFunc[Elem any](seq iter.Seq[Elem], cmp func(Elem, Elem) int) []Elem
// SortedStableFunc collects values from seq into a new slice, sorts the slice
// using a stable sort, and returns it.
func SortedStableFunc[Elem any](seq iter.Seq[Elem], cmp func(Elem, Elem) int) []Elem
Comment From: ianlancetaylor
When I look at the list today, I'm a little worried about slices.Append. I think it may be confusing that it's not like append. Maybe slices.AppendSeq? But I don't feel strongly about it.
Comment From: eliben
When I look at the list today, I'm a little worried about
slices.Append. I think it may be confusing that it's not likeappend. Maybeslices.AppendSeq? But I don't feel strongly about it.
slices.Append feels like the odd-one-out to me too. On the other hand, if we called it AppendSeq it would look different from Collect, which doesn't have a Seq suffix. Another option is AppendInto.
Comment From: earthboundkid
slices.AppendAll?
Comment From: mibk
Or slices.AppendFrom.
Comment From: alexaandru
I don't think that naming is the problem, but rather the fact that we have two different ways of doing the exact same thing (namely, appending to a slice). Besides, if people see an AppendFrom they might wonder where is the missing AppendTo or worse, maybe think append is when you want to append to a slice and AppendFrom when you want to append from a slice. It's just new vs make on steroids... And AppendAll begs the question: "did append() only append some and that's why AppendAll() was added?". I mean, if you need an append ALL, clearly "someone" didn't append enough before... or we wouldn't need it, right?
I think that the bigger issue is that before this, appending to a slice was a no brainer: append(). End of story. After this change, we got decisions to make. And they involve probably the most common operation on the most common data structure used by... everyone?
To me personally, the most natural thing would be for append() to continue to do what it does today: append stuff to slices. Even if that stuff is a sequence of bytes, of strings, of anys or just an iter.Seq, which itself is the very definition of a sequence. It wouldn't break backward compatibility, it wouldn't "overload" append with any new responsibility, it would simply continue to append a sequence of elements to a slice, regardless of how that sequence is expressed.
Comment From: gophun
To me personally, the most natural thing would be for
append()to continue to do what it does today: append stuff to slices. Even if that stuff is a sequence ofbytes, ofstrings, ofanys or just aniter.Seq, which itself is the very definition of a sequence.
Does this append the iter.Seq itself or its elements?
var s []any
var seq iter.Seq[any]
s = append(s, seq)
You'd need a ... operator for iter.Seqs.
Comment From: Merovius
My counter-argument to changing append: As @gophun mentioned, you'd need to make it append(s, seq...), if nothing else, then for consistency. But then, the question becomes why you can pass an iter.Seq as a variadic argument to append, but not to, say fmt.Println. So we would want to really allow using an iter.Seq as a variadic argument in general. But then, the callee can use a variadic argument as a slice (including writing to it and randomly accessing it), which means the only way to implement that would be to essentially do fmt.Println(slices.Collect(seq)...), which is expensive - and the expense would probably frustrate those who don't treat the argument as a slice, but just read it once, in sequence.
So I don't really see a satisfying way to retro-fit iter.Seq into append.
Personally, I think slices.Append is fine as it is. The comparison to append is not awesome, but IMO not fatal.
Comment From: alexaandru
Yes, I stand corrected, modifying append is not really what I was looking for, just having append(s, slices.Collect(iter.Seq)...) work, the append(s, iter.Seq) should do the appending of iter.Seq to a []iter.Seq as expected. No extra magic or anything like that.
Having slices.Append() also do that, more succinctly, doesn't really bother me (and since it appends, it may as well be called that, I don't see a need to look for variations of the name "append").
I apologize for the noise.
Comment From: mohamedattahri
I personally think having Iter.Seq work as a variadic argument with “…” would actually make the most sense and would cement it alongside all the other natural types that represent a sequence of values in the language.As for the cost, yes there is one, but I don’t think it’s higher than the one incurred by inconsistency.On Feb 12, 2024, at 5:35 AM, Alexandru Ungur @.***> wrote: Yes, I stand corrected, modifying append is not really what I was looking for, just having append(s, slices.Collect(iter.Seq)...) work, the append(s, iter.Seq) should do the appending of iter.Seq to a []iter.Seq as expected. No extra magic or anything like that. Having slices.Append() also do that, more succinctly, doesn't really bother me (and since it appends, it may as well be called that, I don't see a need to look for variations of the name "append"). I apologize for the noise.
—Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you commented.Message ID: @.***>
Comment From: gophun
So we would want to really allow using an
iter.Seqas a variadic argument in general. But then, the callee can use a variadic argument as a slice (including writing to it and randomly accessing it), which means the only way to implement that would be to essentially dofmt.Println(slices.Collect(seq)...), which is expensive - and the expense would probably frustrate those who don't treat the argument as a slice, but just read it once, in sequence.
The case of s = append(s, seq...) might be optimized by the compiler to avoid allocating an intermediate slice. But yes, in the general case collecting elements into a slice would be necessary unless the compiler can determine whether the elements are used as a slice or merely iterated over within the function. I don't know enough about compiler optimizations to judge whether this is feasible or not.
Comment From: rsc
AppendSeq sounds fine; good point about confusion with builtin append.
Comment From: rsc
Based on the discussion above, this proposal seems like a likely accept. — rsc for the proposal review group
// All returns an iterator over index-value pairs in the slice.
// The indexes range in the usual order, from 0 through len(s)-1.
func All[Slice ~[]Elem, Elem any](s Slice) iter.Seq2[int, Elem]
// Backward returns an iterator over index-value pairs in the slice,
// traversing it backward. The indexes range from len(s)-1 down to 0.
func Backward[Slice ~[]Elem, Elem any](s Slice) iter.Seq2[int, Elem]
// Values returns an iterator over the values in the slice,
// starting with s[0].
func Values[Slice ~[]Elem, Elem any](s Slice) iter.Seq[Elem]
// AppendSeq appends the values from seq to the slice and returns the extended slice.
func AppendSeq[Slice ~[]Elem, Elem any](x Slice, seq iter.Seq[Elem]) Slice
// Collect collects values from seq into a new slice and returns it.
func Collect[Elem any](seq iter.Seq[Elem]) []Elem
// Sorted collects values from seq into a new slice, sorts the slice, and returns it.
func Sorted[Elem comparable](seq iter.Seq[Elem]) []Elem
// SortedFunc collects values from seq into a new slice, sorts the slice, and returns it.
func SortedFunc[Elem any](seq iter.Seq[Elem], cmp func(Elem, Elem) int) []Elem
// SortedStableFunc collects values from seq into a new slice, sorts the slice
// using a stable sort, and returns it.
func SortedStableFunc[Elem any](seq iter.Seq[Elem], cmp func(Elem, Elem) int) []Elem
Comment From: rsc
No change in consensus, so accepted. 🎉 This issue now tracks the work of implementing the proposal. — rsc for the proposal review group
// All returns an iterator over index-value pairs in the slice.
// The indexes range in the usual order, from 0 through len(s)-1.
func All[Slice ~[]Elem, Elem any](s Slice) iter.Seq2[int, Elem]
// Backward returns an iterator over index-value pairs in the slice,
// traversing it backward. The indexes range from len(s)-1 down to 0.
func Backward[Slice ~[]Elem, Elem any](s Slice) iter.Seq2[int, Elem]
// Values returns an iterator over the values in the slice,
// starting with s[0].
func Values[Slice ~[]Elem, Elem any](s Slice) iter.Seq[Elem]
// AppendSeq appends the values from seq to the slice and returns the extended slice.
func AppendSeq[Slice ~[]Elem, Elem any](x Slice, seq iter.Seq[Elem]) Slice
// Collect collects values from seq into a new slice and returns it.
func Collect[Elem any](seq iter.Seq[Elem]) []Elem
// Sorted collects values from seq into a new slice, sorts the slice, and returns it.
func Sorted[Elem comparable](seq iter.Seq[Elem]) []Elem
// SortedFunc collects values from seq into a new slice, sorts the slice, and returns it.
func SortedFunc[Elem any](seq iter.Seq[Elem], cmp func(Elem, Elem) int) []Elem
// SortedStableFunc collects values from seq into a new slice, sorts the slice
// using a stable sort, and returns it.
func SortedStableFunc[Elem any](seq iter.Seq[Elem], cmp func(Elem, Elem) int) []Elem
Comment From: gopherbot
Change https://go.dev/cl/568477 mentions this issue: slices: add iterator-related functions
Comment From: mpx
I suspect there is a typo in the API above. Sorted should probably take a cmp.Ordered rather than a comparable.
Comment From: fzipp
Should AppendSeq have a vet check according to #62729?
Comment From: ianlancetaylor
My intuition may not be good here, but I don't see why people would think that they can ignore the result of AppendSeq. Presumably people know that they can't ignore the result of append. This seems different from the cases discussed in #62729.
Comment From: fzipp
Presumably people know that they can't ignore the result of
append.
They should know once they are past the beginner stage, but the compiler actually does not allow ignoring the result of append:
package main
func main() {
s := []int{1, 2, 3}
append(s, 4)
}
./prog.go:5:2: append(s, 4) (value of type []int) is not used
https://go.dev/play/p/hsCnEm-VeqG
Comment From: gopherbot
Change https://go.dev/cl/595515 mentions this issue: slices: update docs for All, Backward, Values
Comment From: andig
Does x/exp/maps.Keys() still have a place? I assume that slices.Collect(maps.Keys()) cannot pre-allocate the slice while the former could. Has there been a general discussion regarding iterator performance (link appreciated)? Thank you!
Comment From: fzipp
@andig The discussion for these functions was in #61626, where you participated.
Comment From: zigo101
Some late, Is it better to rename slices.Values as slices.Elements to be consistent with the spec?
Comment From: ianlancetaylor
Values seems clearer to me and is consistent with maps.Values. Thanks.
Comment From: zigo101
Okay. Though personally, I think maps.Values should be also maps.Elements.
Comment From: bobg
Late to the party, but should a declaration like this:
func Collect[Elem any](seq iter.Seq[Elem]) []Elem
instead be:
func Collect[Elem any, Seq ~func(func(Elem) bool)](seq Seq) []Elem
This way the caller isn't confined to using the iter.Seq type.
The same comment applies in a few other places too.
Comment From: ianlancetaylor
@bobg It's possible to assign a value of type func(func(Elem) bool) to a parameter of type iter.Seq[Elem]. Can you show some realistic code where that change would make a difference? Thanks.
Comment From: bobg
Hm, I'm not sure I can. The closest I can come is to imagine that someone will want their own named type for specific kinds of sequence, maybe something like:
type MySeq[T constraints.Integer] func(func (T) bool)
It will be annoying in a case like this always to have to type-convert with iter.Seq[int](mySeq), especially in a post-1.24 future when that could have been avoided (I think?) by making iter.Seq an alias.
But I concede this is pretty hypothetical.