Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

proposal: Go 2: iterators #40605

Closed
Zaba505 opened this issue Aug 6, 2020 · 8 comments
Closed

proposal: Go 2: iterators #40605

Zaba505 opened this issue Aug 6, 2020 · 8 comments
Labels
FrozenDueToAge Go2 A change that can only be done in Go 2 LanguageChange Proposal WaitingForInfo Issue is not actionable because of missing required information, which needs to be provided.
Milestone

Comments

@Zaba505
Copy link

Zaba505 commented Aug 6, 2020

This proposal is for the addition of a new builtin type, iterator, and a new package, iter:

type iterator interface{
  Next() (item interface{}, more bool)
}

// Under package iter

// This struct is for extending the basic builtin iterator to support
// a broader and higher level method set.
//
type Iterator struct {
  // internals would all be private
}

// An example of a method that this type could provide
func (i Iterator) Map(f func(item interface{}) interface{}) Iterator {}

Why

builtin iterator type

This follows a similar reason as to why error is a single method interface and not a struct because it allows any implementation to provide the desired behaviour. The behaviour then comes from the definition of an iterator: a producer of items; hence, the single method, Next. A direct benefit (all be it difficult to document) is that existing builtin types that are iterable can automatically implement the iterator interface. Thus no wrapper types would have to be created to accommodate the use of, for example, []int in a function which looks like this func sum(nums iterator) int.

package iter

Again much like iterator follows error, iter follows the errors package in the sense that its purpose is to provide utilities for working with iterators. I won't go in to everything that can be built on top of the basic iterator interface because a quick google search can bring you up to speed on some very common methods like map, reduce, filter, etc. The main reason for including this package is to provide all users with a consistent and convenient package for simplifying their work with iterators.

Some Thoughts

  • What about errors? - Should iterator actually look like Next() (interface{}, error) where no more items would be identified with io.EOF or possibly iter.EOI.
  • Is this future proof in regards to generics? - Some initial thinking leads me to believe so since ideally it would amount to a change looking like this: Next() (item T, more bool)
  • How useful is this to the greater community really? - I think fairly useful since my (probably wrong) view of the community is one rich with "data processing" (broader sense than just pipelines/aggregation) usage which are workloads that iterators really excel at

For reference, this proposal has been heavily influenced by Rust's implementation of iterators.

@gopherbot gopherbot added this to the Proposal milestone Aug 6, 2020
@martisch
Copy link
Contributor

martisch commented Aug 6, 2020

"is that existing builtin types that are iterable can automatically implement the iterator interface"

I think it needs to be spelled out what this means. How can []int implement the iterator interface? Does that mean []int would have a Next method which is a fairly invasive language change for all types now to have methods. Next requires a state. How and when is this intialized/reset for a value like []int{1,2,3} or map[string]int{"foo":1,...} and where is it stored?

Please give some full examples how usage would look like.

What does an iterator on a channel do? How do iterators deal with the slice or maps being modified (also in the number of entries)?

Would e.g. range use that iterator interface? Why not? If yes how?

To change the signature of next with generics would be backwards incomaptible. It seems it would be good to see how generics will turn out first. Using interface{} values is also very cumbersome as it will require type assertions in the calling code of next.

Its also good to think about implementation. Using all these interfaces will cause a lot of allocations and performance impact.

@martisch martisch added Go2 A change that can only be done in Go 2 LanguageChange WaitingForInfo Issue is not actionable because of missing required information, which needs to be provided. labels Aug 6, 2020
@mvdan
Copy link
Member

mvdan commented Aug 6, 2020

Please note that you should fill https://github.com/golang/proposal/blob/master/go2-language-changes.md when proposing a language change.

@ianlancetaylor ianlancetaylor changed the title proposal: iterators proposal: Go 2: iterators Aug 6, 2020
@icholy
Copy link

icholy commented Aug 7, 2020

The generics proposal will enable writing your own iterator interface outside of the stdlib.

type Iterator[type T] interface {
    Next() bool
    Value() T
}

This gives you everything except the range behavior (which I don't think adds too much value anyway).

for x := range it {
    fmt.Println(x)
}

// vs

for it.Next() {
    fmt.Println(it.Value())
}

@leaxoy
Copy link

leaxoy commented Aug 17, 2020

To get an usable and convenient version of Iterator, I think we need above features.

  1. interface default method. To chain function like a.Map(func (int) string {}).Filter(func(string)bool{}).Collect() while a is any struct that implement Iterator interface. This design borrow from rust.
  2. Method type parameter. With this feature, we can write Map method with another type parameter inside Iterator interface.
  3. Type specialization. With this feature, we can get Sum method only type parameter implement Summable or Addable.

Further,we can add simple lambda expression, describe at #21498. Enum for Option, describe at #19412.

@leaxoy
Copy link

leaxoy commented Aug 17, 2020

And any type implement Iterator should be passed to for-loop statement.

@elissa2333
Copy link

elissa2333 commented Sep 1, 2020

Why don't you try to implement iterators using channels

package main

import "fmt"

func main() {
	for i := range iterator() {
		if i > 5 { // You can exit at any time
			break
		}
		fmt.Println(i)
	}
}

func iterator() <-chan int {
	ch := make(chan int)
	go func(ch chan int) {
		defer close(ch)
		for i := 0; i < 10; i++ {
			ch <- i
		}

	}(ch)

	return ch
}

@gopherbot
Copy link

gopherbot commented Sep 6, 2020

Timed out in state WaitingForInfo. Closing.

(I am just a bot, though. Please speak up if this is a mistake or you have the requested information.)

@quenbyako
Copy link

quenbyako commented Apr 20, 2021

@elissa2333 no, you may have a goroutine leak because this example expects that ALL values will be read from the channel, and only then it will close.

the problem with this example is that we cannot find out whether someone is reading from the channel or not (btw, it’s a matter of one pr! implementation of this functionality is way easier that you think), and if no one reads from the channel, so the iterator goroutine will simply be blocked! so this is far from the best option (at the time of this writing)

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge Go2 A change that can only be done in Go 2 LanguageChange Proposal WaitingForInfo Issue is not actionable because of missing required information, which needs to be provided.
Projects
None yet
Development

No branches or pull requests

8 participants