Recursive Generator Question

Dan Perl dperl at rogers.com
Thu Sep 2 23:40:04 EDT 2004


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" <pchiusan at umich.edu> wrote in message
news:6543373d.0409021839.5caff11d at 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
>
>
> 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





More information about the Python-list mailing list