Recursive Generator Question

[Paul Chiusano]

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?

Thanks,
Paul

[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

[Dan Perl]

Why do you define __iter__? And Node.next is your generator function, so
you have to invoke it, it's not invoked implicitly. You are not creating an
iterator yourself, the generator function returns one for you. That
iterator has a next( ) method and that's what's getting called to iterate
through the tree. So there is no need to actually name the generator
function in your class "next", you can name it anything.

BTW, here is the definition for generator functions:
http://docs.python.org/ref/types.html#l2h-90

Here is the way I think your code should be with minimal changes (I put in
comments for the changes):
class Node:
def __init__(self, data=None, left=None, right=None):
self.children = []
self.children.append(left)
self.children.append(right)
self.data = data

# Got rid of the __iter__ method

def next(self):
"""Generator function""" # Better description
if self.data:
yield self
else:
for child in self.children:
for terminal in child.next(): # Changed child to
child.next()
yield terminal

if '__main__'==__name__:
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.next(): # Changed abcd to
abcd.next()
print termNodes.data # no error

Dan

"Paul Chiusano" <pc******@umich.edu> wrote in message
news:65**************************@posting.google.c om...

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?

Thanks,
Paul

[Dan Christensen]

pc******@umich.edu (Paul Chiusano) writes:

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

If you are defining next yourself, you are defining an iterator, not a
generator, and you should use return statements, not yield statements.
But then you also need to keep track of where you are in the tree.
If you like to use a generator to save the state for you, one way
that works is the following.

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 != None:
yield self.data
for child in self.children:
if child != None:
for terminal in child:
yield terminal

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

# Produces:
#
# a
# b
# c
# d

Notes:

- __iter__ is a generator, so when called it returns an iterator
- No explicit next method
- termNodes.data changed to termNodes
- child != None checked

To the experts: I don't recall seeing __iter__ be a generator like
this before. How would you code it?

Dan

[Tim Peters]

[Dan Christensen]
....

def __iter__(self):
if self.data != None:
yield self.data
for child in self.children:
if child != None:
for terminal in child:
yield terminal
....
To the experts: I don't recall seeing __iter__ be a generator like
this before. How would you code it?

The way you did. A generator *is* a (one kind of) iterator, so it's
fine to use a generator anywhere an iterator is desired.
(Technically, the __iter__ method there is called a
generator-function, and the thing it returns is called a
generator-iterator.)

[Dan Perl]

"Jp Calderone" <ex*****@divmod.com> wrote in message
news:ma**************************************@pyth on.org...

Paul Chiusano wrote: ......... 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.

I think a clarification is in order here. Done this way, __iter__ *IS* a
generator function and it returns an iterator, not a generator. The next( )
is called on the iterator returned by __iter__. Using __iter__ as the
generator takes advantage of the fact that the 'for' statement invokes it
implicitly. But the generator could have any name and it would just have to
be called explicitly.

I would rather do it the explicit way, and it's not just because I'm
following the advice I've been getting from a lot of people in another
thread, where I was on the 'implicit' side of the argument. ;-)

But this way, the 'implicit' call to __iter__, works too.

Dan

[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

[Shalabh Chaturvedi]

Shalabh Chaturvedi wrote:

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.

3 should be
3. A generator is an object with next() on it.

--
Shalabh

[Brian McErlean]

pc******@umich.edu (Paul Chiusano) wrote in message news:<65**************************@posting.google. com>...

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

[ ... ]
For some reason, that iteration is returning generators instead of
leaves. Curiously, if I replace that for loop with

This is because you told it to. The next() method needs to return the
single next element, but the one above is returning a generator, so
you end up with a sequence of generators. If you make the object its
own iterator (returning self in __iter__), you will have to save some
state to remember what position you are at (which is bad since it
prevents multiple iterators)

What you probably meant to do is to put the code in the next() method
directly in __iter__ - that way the generator returned is your
iterator, rather than the object itself.

Brian.