Recursive Generator Question

[Jp Calderone]

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. Curiously, if I replace that for loop with
> 
> for termNodes in terminals(abcd): # see definition below 
> 	print termNodes.data # no problem!
> 
> then it actually prints out:
> a
> b
> c
> d
> 
> Here's the definition of terminals--pretty much identical to next. 
> 
> def terminals(t):
> 	""" Returns an iteration over the leaves of a tree, t """
> 	if t.data: # if I have data, then I'm a terminal node
> 		yield t
> 	else: 
> 		for child in t.children:
> 			for terminal in terminals(child):
> 				yield terminal
> 
> Am I missing something? Or is it not possible to define recursive
> generators in this way?

   The generators are a red herring :)  Iterating over an object calls 
__iter__ on the object, then repeatedly calls next on the object 
returned by __iter__.  Each object next returns is taken as a value for 
iteration.

   So, if we examine your node class, we see that when __iter__ is 
called, the same object is returned.  When next is called on the node 
class, a generator is returned.  Oops.  Throw away your current __iter__ 
method and rename your next method __iter__.  Now when __iter__ is 
called, it will return a generator, and when next is called on the 
generator, you will get the leaf nodes you were looking for.

   Jp


> 
> Thanks,
> Paul