Re: [Tutor] Here is newbie doc on how to implement generators
On Mon, Jul 16, 2007 at 06:13:35PM -0400, Kent Johnson wrote: Kent - Rather than try to reply in detail to your suggestions, I've tried to ammend my document to reflect your comments. Thanks again for the help. Dave [good suggestions and corrections from Kent, snipped] -- Dave Kuhlman http://www.rexx.com/~dkuhlman ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Here is newbie doc on how to implement generators
Dave Kuhlman wrote: > I find iterators and generators fascinating. So, in order to try > to understand them better myself, I've written up some notes. I'm > hoping that these notes might help someone new to the generators > and iterators in Python. You can find it here: > > http://www.rexx.com/~dkuhlman/python_comments.html > > http://www.rexx.com/~dkuhlman/python_comments.html#iterators-and-generators > > I'll appreciate any comments and suggestions that might help me > improve it. In the Consumers section, the first time you mention the iterator protocol, you omit mention of __init__() - this is a required method of an iterator. In the section "The iterator protocol", the __iter__() bullet, "(2) return the value returned by a generator method" is not correct. An iterator must return self from __iter__(). An object that returns a (new) generator from __iter__() is an iterable, not an iterator. In some cases there is no need to write a separate generator method and call it in __iter__(); __iter__() itself can be written as a generator method using yield. This works if the generator method doesn't need any arguments. Your Doubler class will not behave correctly because of the re-initialization of the index in __iter__(). Calling __iter__() should not have any side effects. Here is an example of why this is a problem, using Doubler as you have written it: In [9]: d=Doubler(range(5)) In [10]: d.next() Out[10]: 0 In [11]: d.next() Out[11]: 2 In [12]: for i in d: print i : 0 2 4 6 8 Notice how the for loop resets the iterator (because it calls __iter__() to make sure it has an iterator). Compare with a correctly implemented iterator: In [13]: it = iter(range(5)) In [14]: it.next() Out[14]: 0 In [15]: it.next() Out[15]: 1 In [16]: for i in it: print i : 2 3 4 Double would actually be easier to implement with __iter__() as a generator method. I already commented on the pitfalls of making an object its own iterator. In the standard library, a file is its own iterator. That makes sense because it is a wrapper around a singleton state - the seek position of the file. I don't think it makes much sense in general to have an object be its own iterator unless the object is just an iterator. Another reference is the What's New doc for Python 2.2: http://www.python.org/doc/2.2.3/whatsnew/node4.html and the following page. Kent ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Here is newbie doc on how to implement generators
Dave Kuhlman wrote: > On Fri, Jul 13, 2007 at 12:39:40PM +1200, John Fouhy wrote: >> On 13/07/07, Dave Kuhlman <[EMAIL PROTECTED]> wrote: >>> And, I have a question -- If you look at the example of the >>> iterative (non-recursive) generator (the Doubler class), you will >>> see that it walks a list, not a tree. That's because I was *not* >>> able to figure out how to implement a non-recursive tree walk >>> generator. >> You should just be able to use a stack -- push the children onto a >> stack, then pop them off and walk through them. >> >> Here's an example, using tuples and lists as a basic tree data type: >> >> ### treetest.py # >> >> TREE = (0, [(1, [(2, [(3, []), >> (4, []), >> (5, [(6, []), >>(7, []), >>(8, []), >>(9, []), >>]), >> (10, [(11, []), >> (12, []), >> ]), >> ]), >> (13, [(14, []), >>(15, []), >>(16, [])]), >> (17, []), >> (18, []), >> ]), >> (19, []), >> (20, []), >> ]) >> >> def walkTree(tree): >> # stack to hold nodes as we walk through >> stack = [] >> stack.append(tree) >> >> while stack: >> value, children = stack.pop() >> for child in reversed(children): # reverse children to get >> the right order. >> stack.append(child) >> yield value >> >> if __name__ == '__main__': >> for value in walkTree(TREE): >> print value >> >> ### treetest.py # > > John - > > That is so cool. I can't believe that it is so simple and elegant. > I thought that a stack was involved in the solution, but I could > not figure out how to use it. Thanks. > > And, to extend this a bit more, here are two slightly modified > versions of your solution that implement classes whose > instances are iterators. > > > # > # Version #1 -- This version has a next() method, as required by > # the iterator protocol. > # > class Node(object): > def __init__(self, value='', children=None): > self.value = chr(value + 97) * 3 > if children is None: > children = [] > else: > self.children = children > def walk_tree(self): > # stack to hold nodes as we walk through > stack = [] > stack.append(self) > while stack: > node = stack.pop() > # reverse children to get the right order. > stack.extend(reversed(node.children)) > yield node > def __iter__(self): > self.iterator = self.walk_tree() > return self > def next(self): > return self.iterator.next() > > > # > # Version #2 -- This version does not have a next() method, but > # the iterators returned by __iter__() do have a next(). > # > class Node(object): > def __init__(self, value='', children=None): > self.value = chr(value + 97) * 3 > if children is None: > children = [] > else: > self.children = children > def walk_tree(self): > # stack to hold nodes as we walk through > stack = [] > stack.append(self) > while stack: > node = stack.pop() > # reverse children to get the right order. > stack.extend(reversed(node.children)) > yield node > def __iter__(self): > return self.walk_tree() I think Version 2 is preferable. Not only is it shorter, but it is safer. Version 1 has essentially a singleton iterator so any code that tries to iterate the same node more than once will fail. For example multi-threaded code, or perhaps during an iteration there could be a reason to start a new iteration. Kent ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Here is newbie doc on how to implement generators
John Fouhy wrote: > def walkTree(tree): > # stack to hold nodes as we walk through > stack = [] > stack.append(tree) > > while stack: > value, children = stack.pop() > for child in reversed(children): # reverse children to get > the right order. > stack.append(child) FWIW this could be written as stack.extend(reversed(children)) Kent ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Here is newbie doc on how to implement generators
On Fri, Jul 13, 2007 at 12:39:40PM +1200, John Fouhy wrote: > On 13/07/07, Dave Kuhlman <[EMAIL PROTECTED]> wrote: > > And, I have a question -- If you look at the example of the > > iterative (non-recursive) generator (the Doubler class), you will > > see that it walks a list, not a tree. That's because I was *not* > > able to figure out how to implement a non-recursive tree walk > > generator. > > You should just be able to use a stack -- push the children onto a > stack, then pop them off and walk through them. > > Here's an example, using tuples and lists as a basic tree data type: > > ### treetest.py # > > TREE = (0, [(1, [(2, [(3, []), > (4, []), > (5, [(6, []), >(7, []), >(8, []), >(9, []), >]), > (10, [(11, []), > (12, []), > ]), > ]), > (13, [(14, []), >(15, []), >(16, [])]), > (17, []), > (18, []), > ]), > (19, []), > (20, []), > ]) > > def walkTree(tree): > # stack to hold nodes as we walk through > stack = [] > stack.append(tree) > > while stack: > value, children = stack.pop() > for child in reversed(children): # reverse children to get > the right order. > stack.append(child) > yield value > > if __name__ == '__main__': > for value in walkTree(TREE): > print value > > ### treetest.py # John - That is so cool. I can't believe that it is so simple and elegant. I thought that a stack was involved in the solution, but I could not figure out how to use it. Thanks. And, to extend this a bit more, here are two slightly modified versions of your solution that implement classes whose instances are iterators. # # Version #1 -- This version has a next() method, as required by # the iterator protocol. # class Node(object): def __init__(self, value='', children=None): self.value = chr(value + 97) * 3 if children is None: children = [] else: self.children = children def walk_tree(self): # stack to hold nodes as we walk through stack = [] stack.append(self) while stack: node = stack.pop() # reverse children to get the right order. stack.extend(reversed(node.children)) yield node def __iter__(self): self.iterator = self.walk_tree() return self def next(self): return self.iterator.next() # # Version #2 -- This version does not have a next() method, but # the iterators returned by __iter__() do have a next(). # class Node(object): def __init__(self, value='', children=None): self.value = chr(value + 97) * 3 if children is None: children = [] else: self.children = children def walk_tree(self): # stack to hold nodes as we walk through stack = [] stack.append(self) while stack: node = stack.pop() # reverse children to get the right order. stack.extend(reversed(node.children)) yield node def __iter__(self): return self.walk_tree() # # Create some data. # TREE = Node(0, [Node(1, [Node(2, [Node(3, []), Node(4, []), Node(5, [Node(6, []), Node(7, []), Node(8, []), Node(9, []), ]), Node(10, [Node(11, []), Node(12, []), ]), ]), Node(13, [Node(14, []), Node(15, []), Node(16, [])]), Node(17, []), Node(18, []), ]), Node(19, []), Node(20, []), ]) # # Here is a function to exercise the iterator. # def test(): for node in TREE: print 'value: %s' % (node.value, ) Dave -- Dave Kuhlman http://www.rexx.com/~dkuhlman ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Here is newbie doc on how to implement generators
Dave Kuhlman wrote: > I find iterators and generators fascinating. So, in order to try > to understand them better myself, I've written up some notes. I'm > hoping that these notes might help someone new to the generators > and iterators in Python. You can find it here: > > http://www.rexx.com/~dkuhlman/python_comments.html > > http://www.rexx.com/~dkuhlman/python_comments.html#iterators-and-generators > > I'll appreciate any comments and suggestions that might help me > improve it. > > Please pass the above link along to anyone you think it might help. > > And, I have a question -- If you look at the example of the > iterative (non-recursive) generator (the Doubler class), you will > see that it walks a list, not a tree. That's because I was *not* > able to figure out how to implement a non-recursive tree walk > generator. > > I found examples showing non-recursive/iterative solutions to how > to walk a *binary* tree. Those examples are at: > > Lib/test/test_generator.py # in the Python distribution > http://en.wikipedia.org/wiki/Inorder_tree_walk > > But, I could not find a example that shows a non-recursive way to > walk a tree in which each node has an arbitrary number of children. > If you store your tree data in an adjacency list iteration becomes trivial. > Alas, I could not write that non-recursive tree walk. The recusive > walk is easy and clean. So, maybe I should not worry about the > non-recursive approach. Still, it really bothers me that I could > not do it. > > So, if you know where there are some examples, that would help me > improve my notes on iterators and generators, please give me a > link. > > Dave > > > > ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Here is newbie doc on how to implement generators
On 13/07/07, Dave Kuhlman <[EMAIL PROTECTED]> wrote: > And, I have a question -- If you look at the example of the > iterative (non-recursive) generator (the Doubler class), you will > see that it walks a list, not a tree. That's because I was *not* > able to figure out how to implement a non-recursive tree walk > generator. You should just be able to use a stack -- push the children onto a stack, then pop them off and walk through them. Here's an example, using tuples and lists as a basic tree data type: ### treetest.py # TREE = (0, [(1, [(2, [(3, []), (4, []), (5, [(6, []), (7, []), (8, []), (9, []), ]), (10, [(11, []), (12, []), ]), ]), (13, [(14, []), (15, []), (16, [])]), (17, []), (18, []), ]), (19, []), (20, []), ]) def walkTree(tree): # stack to hold nodes as we walk through stack = [] stack.append(tree) while stack: value, children = stack.pop() for child in reversed(children): # reverse children to get the right order. stack.append(child) yield value if __name__ == '__main__': for value in walkTree(TREE): print value ### treetest.py # HTH! -- John. ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
[Tutor] Here is newbie doc on how to implement generators
I find iterators and generators fascinating. So, in order to try to understand them better myself, I've written up some notes. I'm hoping that these notes might help someone new to the generators and iterators in Python. You can find it here: http://www.rexx.com/~dkuhlman/python_comments.html http://www.rexx.com/~dkuhlman/python_comments.html#iterators-and-generators I'll appreciate any comments and suggestions that might help me improve it. Please pass the above link along to anyone you think it might help. And, I have a question -- If you look at the example of the iterative (non-recursive) generator (the Doubler class), you will see that it walks a list, not a tree. That's because I was *not* able to figure out how to implement a non-recursive tree walk generator. I found examples showing non-recursive/iterative solutions to how to walk a *binary* tree. Those examples are at: Lib/test/test_generator.py # in the Python distribution http://en.wikipedia.org/wiki/Inorder_tree_walk But, I could not find a example that shows a non-recursive way to walk a tree in which each node has an arbitrary number of children. Alas, I could not write that non-recursive tree walk. The recusive walk is easy and clean. So, maybe I should not worry about the non-recursive approach. Still, it really bothers me that I could not do it. So, if you know where there are some examples, that would help me improve my notes on iterators and generators, please give me a link. Dave -- Dave Kuhlman http://www.rexx.com/~dkuhlman ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
