slices: add iterator-related functions #61899

rsc · 2023-08-09T16:03:28Z

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
}

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

seankhliao · 2023-08-09T16:19:44Z

Concat takes a a variadic second arg #56353
Should Append and Collect (and Values?) do the same?

mohamedattahri · 2023-08-09T18:57:35Z

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

earthboundkid · 2023-08-09T19:45:52Z

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

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.

DeedleFake · 2023-08-09T20:29:06Z

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.

rsc · 2023-08-09T21:41:24Z

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

hherman1 · 2023-08-10T00:46:53Z

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.

zephyrtronium · 2023-08-10T00:57:05Z

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

hherman1 · 2023-08-10T01:22:10Z

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.

willfaught · 2023-08-10T06:27:08Z

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

hherman1 · 2023-08-10T08:00:22Z

I dont mind the colorless code blocks. The tone there also seems a bit rude @willfaught

willfaught · 2023-08-11T05:46:09Z

The tone there also seems a bit rude @willfaught

My apologies.

leaxoy · 2023-08-15T08:11:58Z

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

DeedleFake · 2023-08-15T14:01:57Z

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

ChrisHines · 2023-08-15T14:31:23Z

I had not paid close attention to the names of the functions this proposal wants to add so far. In #61626 (comment), @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?

Merovius · 2023-08-15T14:40:35Z

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

earthboundkid · 2023-08-15T15:38:29Z

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

earthboundkid · 2023-08-16T13:55:18Z

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

eliben · 2023-08-16T16:53:53Z

Python's sorted is guaranteed to be stable, so they only have one sorted (not sorted and sortedstable) but that one sorted is stable

willfaught · 2023-08-17T06:56:47Z

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.

earthboundkid · 2023-08-17T10:55:40Z

The heap package is in need of a total overhaul. It could incorporate iterators if that happened.

earthboundkid · 2023-08-17T10:58:58Z

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.

rsc · 2023-08-30T17:43:37Z

Finishing this proposal discussion is blocked on #61405.

gopherbot · 2024-01-26T04:35:42Z

Change https://go.dev/cl/558737 mentions this issue: slices: add All, Backward, Values, Append, Collect, Sorted, SortedFunc

rsc · 2024-01-31T18:38:02Z

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.

rsc · 2024-02-08T23:59:39Z

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

ianlancetaylor · 2024-02-09T23:05:05Z

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.

eliben · 2024-02-10T00:28:33Z

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.

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.

earthboundkid · 2024-02-10T15:04:55Z

slices.AppendAll?

mibk · 2024-02-12T07:17:30Z

Or slices.AppendFrom.

alexaandru · 2024-02-12T08:08:10Z

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.

gophun · 2024-02-12T08:43:40Z

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.

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.

Merovius · 2024-02-12T10:22:06Z

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.

alexaandru · 2024-02-12T10:35:39Z

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.

mohamedattahri · 2024-02-12T10:51:42Z

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

gophun · 2024-02-12T11:06:30Z

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.

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.

rsc · 2024-02-14T18:14:57Z

AppendSeq sounds fine; good point about confusion with builtin append.

rsc · 2024-02-14T23:50:45Z

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

rsc · 2024-03-01T17:49:18Z

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

gopherbot · 2024-03-02T01:49:45Z

Change https://go.dev/cl/568477 mentions this issue: slices: add iterator-related functions

mpx · 2024-03-02T02:23:38Z

I suspect there is a typo in the API above. Sorted should probably take a cmp.Ordered rather than a comparable.

rsc added the Proposal label Aug 9, 2023

gopherbot added this to the Proposal milestone Aug 9, 2023

rsc mentioned this issue Aug 9, 2023

iter: new package for iterators #61897

Open

fzipp mentioned this issue Aug 9, 2023

spec: add range over int, range over func #61405

Closed

rsc mentioned this issue Aug 9, 2023

proposal: maps: add maps.KeysSlice and maps.ValuesSlice #61626

Closed

Merovius mentioned this issue Aug 12, 2023

proposal: regexp: add iterator forms of matching methods #61902

Open

This was referenced Dec 10, 2023

cmd/compile: pre-allocate a slice of provable length #64595

Open

proposal: slices: convert one slice to another #64742

Closed

rsc added the Proposal-FinalCommentPeriod label Feb 14, 2024

ianlancetaylor mentioned this issue Mar 1, 2024

proposal: slices: add a reusable slices.Contains() #66022

Open

rsc changed the title ~~proposal: slices: add iterator-related functions~~ slices: add iterator-related functions Mar 1, 2024

rsc modified the milestones: Proposal, Backlog Mar 1, 2024

rsc added Proposal-Accepted and removed Proposal-FinalCommentPeriod labels Mar 1, 2024

This was referenced Mar 19, 2024

slices: add CloneFunc function #66404

Closed

proposal: slices: add Channel #66409

Closed

ChrisHines mentioned this issue Apr 12, 2024

Use a concrete type for JSON pointer go-json-experiment/json#30

Merged

slices: add iterator-related functions #61899

slices: add iterator-related functions #61899

Comments

rsc commented Aug 9, 2023 • edited by ianlancetaylor

seankhliao commented Aug 9, 2023

mohamedattahri commented Aug 9, 2023 • edited

earthboundkid commented Aug 9, 2023

DeedleFake commented Aug 9, 2023 • edited

rsc commented Aug 9, 2023

hherman1 commented Aug 10, 2023

zephyrtronium commented Aug 10, 2023

hherman1 commented Aug 10, 2023

willfaught commented Aug 10, 2023 • edited

hherman1 commented Aug 10, 2023

willfaught commented Aug 11, 2023

leaxoy commented Aug 15, 2023 • edited

DeedleFake commented Aug 15, 2023 • edited

ChrisHines commented Aug 15, 2023

Merovius commented Aug 15, 2023

earthboundkid commented Aug 15, 2023

earthboundkid commented Aug 16, 2023

eliben commented Aug 16, 2023 • edited

willfaught commented Aug 17, 2023

earthboundkid commented Aug 17, 2023

earthboundkid commented Aug 17, 2023

rsc commented Aug 30, 2023

gopherbot commented Jan 26, 2024

rsc commented Jan 31, 2024

rsc commented Feb 8, 2024

ianlancetaylor commented Feb 9, 2024

eliben commented Feb 10, 2024 • edited

earthboundkid commented Feb 10, 2024

mibk commented Feb 12, 2024

alexaandru commented Feb 12, 2024

gophun commented Feb 12, 2024

Merovius commented Feb 12, 2024 • edited

alexaandru commented Feb 12, 2024

mohamedattahri commented Feb 12, 2024 via email

gophun commented Feb 12, 2024

rsc commented Feb 14, 2024

rsc commented Feb 14, 2024

rsc commented Mar 1, 2024

gopherbot commented Mar 2, 2024

mpx commented Mar 2, 2024

rsc commented Aug 9, 2023 •

edited by ianlancetaylor

mohamedattahri commented Aug 9, 2023 •

edited

DeedleFake commented Aug 9, 2023 •

edited

willfaught commented Aug 10, 2023 •

edited

leaxoy commented Aug 15, 2023 •

edited

DeedleFake commented Aug 15, 2023 •

edited

eliben commented Aug 16, 2023 •

edited

eliben commented Feb 10, 2024 •

edited

Merovius commented Feb 12, 2024 •

edited