Entering a recursive data structure

Question

I am trying to use a generator with a Python class that works in much the same way as a linked list.

Here is a really simple example of what I mean:

class GeneratorTest(): def __init__(self, list): if list: self.elem = list[0] if list[1:]: self.n = GeneratorTest(list[1:]) else: self.n = None def __iter__(self): return self def next(self): my_next = self while my_next is not None: yield my_next my_next = my_next.n 

Of course, this is just an example, but this is enough to illustrate this point.

Now I was expecting to be able to call something like:

 g = GeneratorTest([1,2,3,4,5]) for x in g: print x 

And stop the loop when it reaches the last value, but the for loop just continues indefinitely.

I am completely new to generators, so I am sure that this is the main premise that I am missing here.

Is the problem related to the fact that I give the same object that the generator creates? I am sure that if I had an object with a list of GeneratorTest objects, I could just return each of these objects, but I feel there must be a way to do this work without a wrapper object.

What am I missing here?

Answer 1

The problem is that next (or in Py3, __next__ ) should not be a generator - it should maintain its external state and return each value. You return a new generator each time, but since Python does not iterate over this generator, your loop never starts. This may mean that you want __iter__ initially return something other than self (although it requires __iter__ to return self to return).

But the good news is that generators exist to keep track of these rules for you. Move the current next code to __iter__ and everything will work. Python __iter__ over any __iter__ return (as you would expect).

Answer 2

I essentially did this when I ported data from java; this code can serve as an example: http://stromberg.dnsalias.org/~strombrg/treap/

See also “exit”, a recent Python feature that makes this simpler: http://www.python.org/dev/peps/pep-0380/

The treap code does this without a lesson.