What is the idiomatic way of creating a go iterator?

1826 views
Skip to first unread message

WillRubin

unread,
Nov 17, 2011, 2:38:39 PM11/17/11
to golang-nuts
What is the go way of generating an iterator for separate distinct
arrays/slices of a user defined struct?

(Full code example can be found here: http://play.golang.org/p/rwoyu8EV0b
)

HERE'S WHAT I'D LIKE TO ACCOMPLISH
Surfacing a collection like this is second nature to my coding style.
// not a real go code ... no yield in go
/*
func (store *Store) AllPayments() []*Payment {
for _, customer := range store.customerList {
for _, payment := range customer.paymentList {
yield payment
}
}
}
*/

----------------------------------------
ITERATOR-LIKE OPTIONS I'VE FOUND SO FAR
----------------------------------------

WHAT I'M CURRENTLY DOING (and don't like)
/* Inverted iterator: using a function passed in.
This is what I'm currently doing, but I hate it about half the time I
code for it.
I'd like a more "yieldy" way of iterating when it's more natural to
think in terms of an exposed collection.
*/
func (store *Store) DoForAllPayments(f func(payment *Payment)) {
for _, customer := range store.customerList {
for _, payment := range customer.paymentList {
f(payment)
}
}
}

I'D DO THIS EXCEPT FOR ALL THE PLACES WHERE I'VE SEEN "DON'T DO THIS."
// Iterator using channels.
// This is what I want to accomplish, but in a non-channel way.
// That is, unless channels have overcome the problems mentioned in
the message links
// and are now considered the idiomatic go iterator pattern.
func (store *Store) AllPayments() <-chan *Payment {
ch := make(chan *Payment)
go func(ch chan<- *Payment) {
for _, customer := range store.customerList {
for _, payment := range customer.paymentList {
ch <- payment
}
}
close(ch)
}(ch)
return ch
}

Here are some of the "don't" links:
http://stackoverflow.com/questions/5033605/common-programming-mistakes-for-go-developers-to-avoid

http://sites.google.com/site/gopatterns/object-oriented/iterators

http://groups.google.com/group/golang-nuts/browse_thread/thread/a0cdffcf3a63c23f/e373d1ac6f606eca?lnk=gst&q=yield+%2Bpike#e373d1ac6f606eca

Ian Lance Taylor

unread,
Nov 17, 2011, 4:00:17 PM11/17/11
to WillRubin, golang-nuts
WillRubin <endo...@gmail.com> writes:

> I'D DO THIS EXCEPT FOR ALL THE PLACES WHERE I'VE SEEN "DON'T DO THIS."
> // Iterator using channels.
> // This is what I want to accomplish, but in a non-channel way.
> // That is, unless channels have overcome the problems mentioned in
> the message links
> // and are now considered the idiomatic go iterator pattern.

I would say that it is fine to use a channel as an iterator as long as
you know what you are doing. It's not the same as using yield. But if
you are just iterating over slices it works fine.

Passing in a function literal also works fine, of course.

You can also write a little iterator type, but it's definitely more
tedious. Untested code:

type Iterator struct {
Store *store
customer int
payment int
}
func Begin(store *Store) *Iterator {
p := &Iterator{store}
for p.customer < len(store.customerList) && len(store.customerList[p.customer].paymentList) == 0 {
p.customer++
}
}
func (p *Iterator) Done() bool {
return p.customer >= len(p.store.customerList)
}
func (p *Iterator) Next() *Payment {
r := p.store.customerList[p.customer].paymentList[p.payment]
p.payment++
if p.payment >= len(p.store.customerList[p.customer]) {
p.customer++
p.payment = 0
for p.customer < len(p.store.customerList) && len(p.store.customerList[p.customer].paymentList) == 0 {
p.customer++
}
}


Use it as in
p := Begin(store)
while !p.Done() {
payment := p.Next()
// ...
}


Ian

Steven Blenkinsop

unread,
Nov 17, 2011, 10:12:31 PM11/17/11
to Ian Lance Taylor, WillRubin, golang-nuts
On Thu, Nov 17, 2011 at 4:00 PM, Ian Lance Taylor <ia...@google.com> wrote:
WillRubin <endo...@gmail.com> writes:

> I'D DO THIS EXCEPT FOR ALL THE PLACES WHERE I'VE SEEN "DON'T DO THIS."
> // Iterator using channels.
> // This is what I want to accomplish, but in a non-channel way.
> // That is, unless channels have overcome the problems mentioned in
> the message links
> // and are now considered the idiomatic go iterator pattern.

I would say that it is fine to use a channel as an iterator as long as
you know what you are doing.  It's not the same as using yield.  But if
you are just iterating over slices it works fine.

Passing in a function literal also works fine, of course.

You can also write a little iterator type, but it's definitely more
tedious.  Untested code:

SteveD

unread,
Nov 18, 2011, 1:42:03 AM11/18/11
to golang-nuts
On Nov 18, 5:12 am, Steven Blenkinsop <steven...@gmail.com> wrote:
> Or you could do:http://play.golang.org/p/I6GHIOmurv

Here's an iterator using channels:

http://play.golang.org/p/B5IkKTIG7R

and you end up with a simple iterator loop

for payment := range iter {
fmt.Println(payment)
}

BTW, this is probably a bit more expensive than using a closure, but
I'd imagine that if the loop payload was non-trivial, it would not be
noticeable. It's equivalent to use of yield in Python and Lua for
similar purposes, and really saves your ass if you have to write an
iterator over a recursive tree visit, etc.

steve d.

SteveD

unread,
Nov 18, 2011, 2:03:21 AM11/18/11
to golang-nuts
On Nov 18, 8:42 am, SteveD <steve.j.dono...@gmail.com> wrote:
> BTW, this is probably a bit more expensive than using a closure, but
> I'd imagine that if the loop payload was non-trivial, it would not be
> noticeable.

Well, when in doubt, test. Repeating the loop 1e7 times gives 0.8 sec
for the channel version, 0.15 for the closure version.

(BTW, how do I find out the amount of garbage generated?)

So, it all depends on the loop payload. I would certainly not use it
for important inner loops.

steve d.

roger peppe

unread,
Nov 18, 2011, 5:00:59 AM11/18/11
to SteveD, golang-nuts
On 18 November 2011 06:42, SteveD <steve.j...@gmail.com> wrote:
> BTW, this is probably a bit more expensive than using a closure, but
> I'd imagine that if the loop payload was non-trivial, it would not be
> noticeable. It's equivalent to use of yield in Python and Lua for
> similar purposes, and really saves your ass if you have to write an
> iterator over a recursive tree visit, etc.

one crucial difference: if you're using a simple channel iterator and
you want to break half way through the loop, you will generate non-collectable
garbage (the goroutine), whereas closures can be GC'd.

it's not hard to make a channel iterator that can be stopped,
but it requires care and a little more code.

SteveD

unread,
Nov 18, 2011, 5:32:56 AM11/18/11
to golang-nuts
On Nov 18, 12:00 pm, roger peppe <rogpe...@gmail.com> wrote:
> it's not hard to make a channel iterator that can be stopped,
> but it requires care and a little more code.

Well, that's what happens when one blindly uses another language's
idioms ;)

Would this do the trick?

http://play.golang.org/p/0GgKXGIay2

That is, one has a separate kill channel that makes the gorouttine
return.

(Another solution would be to have an ok channel and always send back
an acknowledgement.)

steve d.

WillRubin

unread,
Nov 18, 2011, 2:59:31 PM11/18/11
to golang-nuts
To me, this is the most promising. If I can make it generic I'm going
this route.

If I get it working I'll post the code.

B.Fivel

unread,
Nov 19, 2011, 6:41:45 AM11/19/11
to golang-nuts
On 18 nov, 11:32, SteveD <steve.j.dono...@gmail.com> wrote:
>
> Would this do the trick?
>
> http://play.golang.org/p/0GgKXGIay2
>
> That is, one has a separate kill channel that makes the gorouttine
> return.

This code will deadlock if the test on k (line 47) to break is the
number of items instead of 3 (try with 'if k == 12'):
the iterator goroutine will be done and the kill <- 1 will block.

Using a select with an empty default clause (so that the send doesn't
block) does the trick:
if k == 3 {
select {
case kill<- 1:
default:
}
break
}

roger peppe

unread,
Nov 19, 2011, 8:00:28 AM11/19/11
to B.Fivel, golang-nuts

No - if the goroutine isn't ready to receive, the message will be lost. A buffered channel works better, as I outlined above.

Message has been deleted

roger peppe

unread,
Nov 21, 2011, 9:16:27 AM11/21/11
to B.Fivel, golang-nuts
On 20 November 2011 10:06, B.Fivel <b.fi...@gmail.com> wrote:

> On 19 nov, 14:00, roger peppe <rogpe...@gmail.com> wrote:
>> No - if the goroutine isn't ready to receive, the message will be lost.
>> buffered channel works better, as I outlined above.
> If the iterator goroutine is done, the message sent to the buffered
> channel will be lost too.
> But in both ways no one cares as the message is just a "kill signal"
> for the iterator goroutine to stop, which it has already done.

the iterator might not have stopped - it may still be inside the loop
but not inside the select statement. that is, this method
may leave the iterator goroutine still around indefinitely
because the kill message may never be received.

you can easily simulate this occurrence by adding a sleep
after the select in the iterator.

Reply all
Reply to author
Forward
0 new messages