FAQ
Hi all --

a couple of Gophers have independently hit upon an elegant pattern for
iterators in Go. Say you define a FooList type, which might be

type FooList []Foo

or

type FooList struct {
list []Foo
}

...or whatever. Your users can't use range, but you want for loops to
be easy for them. The solution (credit for independent discovery to
Adam Crossland and Steve Blenkinsop) looks like

var list FooList = ...
iter := list.Iterator()
for foo, ok := iter(); ok; foo, ok := iter() {
// do stuff with foo
}

where iter is a "func() (Foo, bool)" -- it's a closure that remembers
where it left off in its traversal and returns ok=false when you're
done. The implementation of FooList.Iterator() is straightforward for
simple data structures with simple traversal algorithms: e.g. see

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

However, I'm trying to apply this iterator pattern to a depth-first
search of a directed graph, and I'm stumped. The problem is that DFS
is best implemented recursively, which makes it awfully hard for that
iterator closure to just return a current value and then resume where
it left off. The iteration state is really the recursive call stack,
not a simple array index or two.

Suggestions? After spending several hours and many pieces of scrap
paper, I think I have figured out how to do a non-recursive DFS. Or at
least, I figured out enough to convince myself that recursive DFS is a
massive win. So I'd really rather not have to go through the painful
exercise of implementing non-recursive DFS.

Thanks --

Greg

--

Search Discussions

•  at Dec 6, 2012 at 5:49 pm ⇧
If you know the number of items in the list, you can create a buffered
channel large enough to hold (pointers to) each item and then run the
recursive algorithm, pushing them all into the channel. Then "next" is a
simple matter of popping the next item off the list. It's basically a
slightly easier-to-read version of passing a queue down through the
recursion and having everything push onto it. Since the caller isn't
required to exhaust them, I would make sure the channel is sufficiently
buffered so that you don't leak goroutines.

The other option, of course, is to use a stack and save the stack in the
iterator closure, but as you say, it's a bit involved (mostly because you'd
have to push more than just the node onto the stack, you'd also have to
include some state with it).

On Thu, Dec 6, 2012 at 12:36 PM, Greg Ward wrote:

Hi all --

a couple of Gophers have independently hit upon an elegant pattern for
iterators in Go. Say you define a FooList type, which might be

type FooList []Foo

or

type FooList struct {
list []Foo
}

...or whatever. Your users can't use range, but you want for loops to
be easy for them. The solution (credit for independent discovery to
Adam Crossland and Steve Blenkinsop) looks like

var list FooList = ...
iter := list.Iterator()
for foo, ok := iter(); ok; foo, ok := iter() {
// do stuff with foo
}

where iter is a "func() (Foo, bool)" -- it's a closure that remembers
where it left off in its traversal and returns ok=false when you're
done. The implementation of FooList.Iterator() is straightforward for
simple data structures with simple traversal algorithms: e.g. see

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

However, I'm trying to apply this iterator pattern to a depth-first
search of a directed graph, and I'm stumped. The problem is that DFS
is best implemented recursively, which makes it awfully hard for that
iterator closure to just return a current value and then resume where
it left off. The iteration state is really the recursive call stack,
not a simple array index or two.

Suggestions? After spending several hours and many pieces of scrap
paper, I think I have figured out how to do a non-recursive DFS. Or at
least, I figured out enough to convince myself that recursive DFS is a
massive win. So I'd really rather not have to go through the painful
exercise of implementing non-recursive DFS.

Thanks --

Greg

--

--
•  at Dec 6, 2012 at 6:02 pm ⇧
Iterator() can create an unbuffered channel of Foo, launch a goroutine to fill the channel, and return a closure that reads Foo's from the channel.

Also, Iterative DFS is not hard: you simply need a stack (LIFO) to record discovered edges at each node before exploring them, and that's trivially implemented using slices. If you found this hard, you should to do it as an exercise, IMHO. Also, it will be much faster than the channel-based approach.

--Glenn

--
•  at Dec 6, 2012 at 6:16 pm ⇧

However, I'm trying to apply this iterator pattern to a depth-first
search of a directed graph, and I'm stumped.
i'd invert the control flow and have the iterator call an
iterator function that you call it (as filepath.Walk does, for example).

it probably has about the same performance characteristics,
but will be much easier to write.

if the caller wants to traverse two such iterators concurrently,
they could use channels (admittedly with significant performance cost)

On 6 December 2012 17:36, Greg Ward wrote:
Hi all --

a couple of Gophers have independently hit upon an elegant pattern for
iterators in Go. Say you define a FooList type, which might be

type FooList []Foo

or

type FooList struct {
list []Foo
}

...or whatever. Your users can't use range, but you want for loops to
be easy for them. The solution (credit for independent discovery to
Adam Crossland and Steve Blenkinsop) looks like

var list FooList = ...
iter := list.Iterator()
for foo, ok := iter(); ok; foo, ok := iter() {
// do stuff with foo
}

where iter is a "func() (Foo, bool)" -- it's a closure that remembers
where it left off in its traversal and returns ok=false when you're
done. The implementation of FooList.Iterator() is straightforward for
simple data structures with simple traversal algorithms: e.g. see

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

However, I'm trying to apply this iterator pattern to a depth-first
search of a directed graph, and I'm stumped. The problem is that DFS
is best implemented recursively, which makes it awfully hard for that
iterator closure to just return a current value and then resume where
it left off. The iteration state is really the recursive call stack,
not a simple array index or two.

Suggestions? After spending several hours and many pieces of scrap
paper, I think I have figured out how to do a non-recursive DFS. Or at
least, I figured out enough to convince myself that recursive DFS is a
massive win. So I'd really rather not have to go through the painful
exercise of implementing non-recursive DFS.

Thanks --

Greg

--
--
•  at Dec 6, 2012 at 7:27 pm ⇧

On Thu, Dec 6, 2012 at 6:36 PM, Greg Ward wrote:
a couple of Gophers have independently hit upon an elegant pattern for
iterators in Go.
I have to say the obvious: `elegant` is _totally_ subjective.
Say you define a FooList type, which might be

type FooList []Foo

or

type FooList struct {
list []Foo
}

...or whatever. Your users can't use range, but you want for loops to
be easy for them.
In the first case users _can_ use range. In the second they've been
intentionally disallowed to do that (assuming "user" lives in another
package). Isn't it just simpler to let the user do what he needs to
do?
What language is that written in?

-j

--
•  at Dec 7, 2012 at 4:51 pm ⇧

On 06 December 2012, Jan Mercl said:
On Thu, Dec 6, 2012 at 6:36 PM, Greg Ward wrote:
a couple of Gophers have independently hit upon an elegant pattern for
iterators in Go.
I have to say the obvious: `elegant` is _totally_ subjective.
Fair enough.
Say you define a FooList type, which might be

type FooList []Foo

or

type FooList struct {
list []Foo
}

...or whatever. Your users can't use range, but you want for loops to
be easy for them.
In the first case users _can_ use range. In the second they've been
intentionally disallowed to do that (assuming "user" lives in another
package). Isn't it just simpler to let the user do what he needs to
do?
Not all data structures are as simple as a wrapper around a slice. I
would never in a zillion years expect the "range" operator to
recognize my particular implementation of a directed graph, nor for it
to iterate over that graph in topological order. Of *course* I have to
write my own DFS that yields a topo sort. I'm just trying to expose
that functionality to the rest of my app in a nice, clean way.

Currently I'm using a callback:

// Callback function to visit nodes from DFS(). Return a non-nil error
// to abort the traversal and make DFS() return that error. DFS()
// aborted this way does not report dependency cycles.
type DFSVisitor func(id int) error

// Perform a partial depth-first search of the graph, exploring
// ancestors of all nodes in 'start'. For each node visited, call
// visit() just as we're leaving that node -- i.e. calls to visit()
// are in topological order. visit() can abort the search; see
// DFSVisitor for details.
func (self *DAG) DFS(start NodeSet, visit DFSVisitor) error {
[...]
}

That works fine, but it leads to slightly inside-out code, e.g.

visit := func(id int) error {
[...do stuff with the node specified by id...]
}
err := self.dag.DFS(targets, visit)

The closure-as-iterator pattern appeals because it lets you write
something like

iter := dag.Iterator()
for id, ok := iter(); ok; id, ok := iter() {
[...do stuff with the node specified by id...]
}

which I find slightly more readable. I thought it would be worth
playing around to see if I could figure out a way to make this work
despite having a recursive iteration algorithm.
What language is that written in?
Very droll. For the record, I did not write that code, but I like the
way it lets the data structure hide its inner workings from callers,
but still lets callers use a normal "for" loop. Perhaps a callback
would be more idiomatic Go, but this strikes me as a nice use of the
"comma ok" idiom.

Greg

--
•  at Dec 7, 2012 at 5:39 pm ⇧
in terms of minimising boilerplate, one could say it reads slightly
better like this:

err := dag.DFS(targets, DFSVisitor {
[...do stuff with the node specified by id...]
return nil
})

It'd be even nicer if the Go compiler could infer the type of the
closure and one could write:

err := dag.DFS(targets, {
[...do stuff with the node specified by id...]
return nil
})

Nico

--
•  at Dec 7, 2012 at 7:21 pm ⇧
One approach I stumbled upon a while ago was to sort of trampoline* the
iterators, like this: http://play.golang.org/p/HG3R8Tx9mW

Doing this with other traversal orders is left as an exercise to the reader
;). The advantage this has over the approach that David DENG posted is that
you don't have to retraverse the recursive path each time you call the
iterator.

* I didn't know there was a name for it until after I "invented" it. Bummer.

On Fri, Dec 7, 2012 at 12:39 PM, N. Riesco - GMail wrote:

in terms of minimising boilerplate, one could say it reads slightly better
like this:

err := dag.DFS(targets, DFSVisitor {

[...do stuff with the node specified by id...]
return nil
})

It'd be even nicer if the Go compiler could infer the type of the closure
and one could write:

err := dag.DFS(targets, {

[...do stuff with the node specified by id...]
return nil
})

Nico

--

--
•  at Dec 7, 2012 at 8:56 pm ⇧

On 07 December 2012, Steven Blenkinsop said:
One approach I stumbled upon a while ago was to sort of trampoline* the
iterators, like this: http://play.golang.org/p/HG3R8Tx9mW
Ooh, that is clever. At least I think it is... I won't understand it
until I work through it on paper. *sigh*
Doing this with other traversal orders is left as an exercise to the reader
;). The advantage this has over the approach that David DENG posted is that
you don't have to retraverse the recursive path each time you call the
iterator.
Yeah, I noticed that too. Downsides to the trampoline approach:

* two function calls for each iteration, compared to one for my
current callback
* lots of short-lived closures: I wonder how that affects GC?
* makes my brain explode

So far I'm inclined to stick with the straightforward, obvious
implementation that I already have. "Dammit, Go, why won't you let me
be subtle, sneaky, tricky, and clever?" ;-)

Greg

--
•  at Dec 7, 2012 at 10:09 pm ⇧

On Fri, Dec 7, 2012 at 3:56 PM, Greg Ward wrote:
Yeah, I noticed that too. Downsides to the trampoline approach:

* two function calls for each iteration, compared to one for my
current callback
You can, of course, skip the Iterator and just use the Stepper directly.

* lots of short-lived closures: I wonder how that affects GC?
It's basically the same as recursively making a linked list stack, except
that it can be a bit lazy, and you don't have to write a separate Pop
function. You could cache the first step if you wanted to, but it would be
invalidated as soon as you altered the tree. Here's a version that uses an
slice in place of closures, and uses it directly rather than through an
iterator:
http://play.golang.org/p/xHqInvz2Z0

Post-order traversal:
http://play.golang.org/p/6e-LPh3EcV

* makes my brain explode
Maybe my stack version makes more sense? It's essentially logically
equivalent. The function literal there is just the closure equivalent of
append.

So far I'm inclined to stick with the straightforward, obvious
implementation that I already have. "Dammit, Go, why won't you let me
be subtle, sneaky, tricky, and clever?" ;-)

Greg
--
•  at Dec 8, 2012 at 2:41 am ⇧
Okay, now I'm just playing with it. This is more of a toy than anything,
but I was trying to see if I could replicate the behaviour of the closure
based version, but store values in a slice rather than closing over them. I
took a more object oriented approach, since Popping can now be destructive.
Because the function literals don't close over anything, they shouldn't
allocate any memory. I designed the stack so it only gets as big as the
height of the tree. I can also now push multiple trees onto one stack and,
I think interestingly, I can make them take up only one element until you
start popping nodes from them, like I did with inOrder in this example.

most likely be worse, though it operates on the same principle:
http://play.golang.org/p/8zVDGYfFN3

On Fri, Dec 7, 2012 at 5:00 PM, Steven Blenkinsop wrote:
On Fri, Dec 7, 2012 at 3:56 PM, Greg Ward wrote:

Yeah, I noticed that too. Downsides to the trampoline approach:

* two function calls for each iteration, compared to one for my
current callback
You can, of course, skip the Iterator and just use the Stepper directly.

* lots of short-lived closures: I wonder how that affects GC?
It's basically the same as recursively making a linked list stack, except
that it can be a bit lazy, and you don't have to write a separate Pop
function. You could cache the first step if you wanted to, but it would be
invalidated as soon as you altered the tree. Here's a version that uses an
slice in place of closures, and uses it directly rather than through an
iterator:
http://play.golang.org/p/xHqInvz2Z0

Post-order traversal:
http://play.golang.org/p/6e-LPh3EcV

* makes my brain explode
Maybe my stack version makes more sense? It's essentially logically
equivalent. The function literal there is just the closure equivalent of
append.

So far I'm inclined to stick with the straightforward, obvious
implementation that I already have. "Dammit, Go, why won't you let me
be subtle, sneaky, tricky, and clever?" ;-)

Greg
--
•  at Dec 8, 2012 at 3:32 am ⇧

On Fri, Dec 7, 2012 at 2:21 PM, Steven Blenkinsop wrote:

One approach I stumbled upon a while ago was to sort of trampoline* the
iterators, like this: http://play.golang.org/p/HG3R8Tx9mW

That is brilliant!

For those playing along at home, the DFS (aka "pre-order") version is:
http://play.golang.org/p/QUWvSoau5T <http://play.golang.org/p/2KUNoZ3ESG>

Doing this with other traversal orders is left as an exercise to the
reader ;). The advantage this has over the approach that David DENG posted
is that you don't have to retraverse the recursive path each time you call
the iterator.

* I didn't know there was a name for it until after I "invented" it.
Bummer.

On Fri, Dec 7, 2012 at 12:39 PM, N. Riesco - GMail <
nicolas.riesco@gmail.com> wrote:
in terms of minimising boilerplate, one could say it reads slightly
better like this:

err := dag.DFS(targets, DFSVisitor {

[...do stuff with the node specified by id...]
return nil
})

It'd be even nicer if the Go compiler could infer the type of the closure
and one could write:

err := dag.DFS(targets, {

[...do stuff with the node specified by id...]
return nil
})

Nico

--

--

--
•  at Dec 6, 2012 at 8:23 pm ⇧
I'd rather use a channel instead, the code looks simpler to me.

Modifying your code just a little bit:

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

Modifying it a little bit more

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

Cheers,

On Thu, Dec 6, 2012 at 9:36 AM, Greg Ward wrote:

Hi all --

a couple of Gophers have independently hit upon an elegant pattern for
iterators in Go. Say you define a FooList type, which might be

type FooList []Foo

or

type FooList struct {
list []Foo
}

...or whatever. Your users can't use range, but you want for loops to
be easy for them. The solution (credit for independent discovery to
Adam Crossland and Steve Blenkinsop) looks like

var list FooList = ...
iter := list.Iterator()
for foo, ok := iter(); ok; foo, ok := iter() {
// do stuff with foo
}

where iter is a "func() (Foo, bool)" -- it's a closure that remembers
where it left off in its traversal and returns ok=false when you're
done. The implementation of FooList.Iterator() is straightforward for
simple data structures with simple traversal algorithms: e.g. see

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

However, I'm trying to apply this iterator pattern to a depth-first
search of a directed graph, and I'm stumped. The problem is that DFS
is best implemented recursively, which makes it awfully hard for that
iterator closure to just return a current value and then resume where
it left off. The iteration state is really the recursive call stack,
not a simple array index or two.

Suggestions? After spending several hours and many pieces of scrap
paper, I think I have figured out how to do a non-recursive DFS. Or at
least, I figured out enough to convince myself that recursive DFS is a
massive win. So I'd really rather not have to go through the painful
exercise of implementing non-recursive DFS.

Thanks --

Greg

--

--
--
Francesc

--
•  at Dec 6, 2012 at 8:57 pm ⇧
The problem with this approach (as has been pointed out numerous times when
iterators come up on the mailing list) is that you cannot break out of that
loop without leaving a goroutine hanging around forever.
On Thu, Dec 6, 2012 at 3:23 PM, Francesc Campoy Flores wrote:

http://play.golang.org/p/K7K22Jwy5A
--
•  at Dec 6, 2012 at 9:18 pm ⇧
Sure you can, or are quit chans illegal now?
http://play.golang.org/p/X4M-S-APgk

--
•  at Dec 6, 2012 at 9:23 pm ⇧
My bad Kyle, I just realized I mis-interpreted your post, I somehow failed to realize you were talking about magical iterators. So used to doing things the easy way at this point.

-Simon Watt

--
•  at Dec 7, 2012 at 4:38 am ⇧
You can, but you have to do it explicitly

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

On Thu, Dec 6, 2012 at 12:57 PM, Kyle Lemons wrote:

The problem with this approach (as has been pointed out numerous times
when iterators come up on the mailing list) is that you cannot break out of
that loop without leaving a goroutine hanging around forever.
On Thu, Dec 6, 2012 at 3:23 PM, Francesc Campoy Flores wrote:

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

--
--
Francesc

--
•  at Dec 7, 2012 at 2:29 pm ⇧
Wow that is surprising and good to know. Maybe something should be added to
the FAQ or Effective Go about it. Here's the bugtracker issue, for anyone
WontFix).

-Ryan
On Thursday, December 6, 2012 3:57:30 PM UTC-5, Kyle Lemons wrote:

The problem with this approach (as has been pointed out numerous times
when iterators come up on the mailing list) is that you cannot break out of
that loop without leaving a goroutine hanging around forever.

On Thu, Dec 6, 2012 at 3:23 PM, Francesc Campoy Flores <cam...@golang.org<javascript:>
--
•  at Dec 7, 2012 at 12:01 am ⇧
Two alternative ways
1) Use a slice as a stack to do DFS
2) Recursively call iterator functions

two implementations have be shown here: http://play.golang.org/p/Vn1Eak-cDt

David
On Friday, December 7, 2012 1:36:08 AM UTC+8, Greg Ward wrote:

Hi all --

a couple of Gophers have independently hit upon an elegant pattern for
iterators in Go. Say you define a FooList type, which might be

type FooList []Foo

or

type FooList struct {
list []Foo
}

...or whatever. Your users can't use range, but you want for loops to
be easy for them. The solution (credit for independent discovery to
Adam Crossland and Steve Blenkinsop) looks like

var list FooList = ...
iter := list.Iterator()
for foo, ok := iter(); ok; foo, ok := iter() {
// do stuff with foo
}

where iter is a "func() (Foo, bool)" -- it's a closure that remembers
where it left off in its traversal and returns ok=false when you're
done. The implementation of FooList.Iterator() is straightforward for
simple data structures with simple traversal algorithms: e.g. see

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

However, I'm trying to apply this iterator pattern to a depth-first
search of a directed graph, and I'm stumped. The problem is that DFS
is best implemented recursively, which makes it awfully hard for that
iterator closure to just return a current value and then resume where
it left off. The iteration state is really the recursive call stack,
not a simple array index or two.

Suggestions? After spending several hours and many pieces of scrap
paper, I think I have figured out how to do a non-recursive DFS. Or at
least, I figured out enough to convince myself that recursive DFS is a
massive win. So I'd really rather not have to go through the painful
exercise of implementing non-recursive DFS.

Thanks --

Greg
--
•  at Dec 7, 2012 at 8:24 pm ⇧

On 06 December 2012, David DENG said:
Two alternative ways
1) Use a slice as a stack to do DFS
2) Recursively call iterator functions

two implementations have be shown here: http://play.golang.org/p/Vn1Eak-cDt
Nice. However, I'm working with a directed graph, and I need a
topological sort, ie. the graph equivalent of a postorder traversal.
(I also need to detect and report cycles -- I need a DAG, but cannot
assume it.) Your code does a preorder traversal of a binary tree,
which is much simpler.

Turns out that a non-recursive postorder traversal of a binary tree is
a bit tricky. I managed to work out a very old-fashioned looking
algorithm (gotos! labels! no loops!) that works. Then I remembered

http://www.leetcode.com/2010/10/binary-tree-post-order-traversal.html

Anyways, I think I've blown enough time on this very minor refactoring
for now. Thanks for your suggestions!

Greg

--

Related Discussions

Discussion Overview
 group golang-nuts categories go posted Dec 6, '12 at 5:36p active Dec 8, '12 at 3:32a posts 20 users 11 website golang.org

11 users in discussion

Content

People

Support

Translate

site design / logo © 2022 Grokbase