Recursive Generator Question

[Shalabh Chaturvedi]

Paul Chiusano wrote:
> I've been playing around with generators and have run into a
> difficulty. Suppose I've defined a Node class like so:
> 
> class Node:	
> 	def __init__(self, data=None, left=None, right=None):
> 		self.children = []
> 		self.children.append(left)
> 		self.children.append(right)
> 		self.data = data
> 	
> 	def __iter__(self): return self
> 			
> 	def next(self):
>         """ Returns iteration over terminal nodes of this tree. """
> 		if self.data:
> 			yield self
> 		else:
> 			for child in self.children:
> 				for terminal in child:
> 					yield terminal
> 
> 
> And then suppose I create a little binary tree like so:
> 
> a = Node('a')
> b = Node('b')
> c = Node('c')
> d = Node('d')
> ab = Node(left=a, right=b)
> cd = Node(left=c, right=d)
> abcd = Node(left=ab, right=cd)
> 
> for termNodes in abcd:
> 	print termNodes.data # gives an error
> 
> when I do this, I get the following error:
> Traceback (most recent call last):
>   File "C:\Documents and Settings\Paul
> Chiusano\workspace\sandbox\hello.py", line 69, in ?
>     print termNodes.data
> AttributeError: 'generator' object has no attribute 'data'
> 
> For some reason, that iteration is returning generators instead of
> leaves.
<snip>
> Am I missing something? Or is it not possible to define recursive
> generators in this way?

It is possible to define recursive generators. To fix the code, copy the 
contents of next() into __iter__().

class Node:	
	def __init__(self, data=None, left=None, right=None):
		self.children = []
		self.children.append(left)
		self.children.append(right)
		self.data = data
	
	def __iter__(self):
		if self.data:
			yield self
		else:
			for child in self.children:
				for terminal in child:
					yield terminal

Iterators and generators can get a little confusing. Note that:

1. Calling __iter__() should return an object with next() on it.
2. When you call a function containing yield, it returns a generator.
3. A generator is function with next() on it.

Conclusion, __iter__() should have yield in it.

To expand point 2 - calling a function containing yield does *not* 
return the yielded results. It returns an generator object and repeated 
calls on next() of the generator object return the yielded results.

When you put it all together, Python does try to make this easier to 
use. You don't need to always go through the extra step of implementing 
next(), you just have to put yield in the __iter__.

Hopefully this makes some sense. Play around with generators to get a 
better idea.

--
Shalabh