[Tutor] recursive generator
Hello,
Is it possible at all to have a recursive generator? I think at a iterator for
a recursive data structure (here, a trie). The following code does not work: it
only yields a single value. Like if child.__iter__() were never called.
def __iter__(self):
''' Iteration on (key,value) pairs. '''
print '*',
if self.holdsEntry:
yield (self.key,self.value)
for child in self.children:
print ,
child.__iter__()
print ,
raise StopIteration
With the debug prints in code above, for e in t: print e outputs:
* ('', 0)
print len(t.children) # -- 9
Why is no child.__iter__() executed at all? I imagine this can be caused by the
special feature of a generator recording current execution point. (But then, is
it at all possible to have a call in a generator? Or does the issue only appear
whan the callee is a generator itself?) Else, the must be an obvious error in
my code.
Denis
--
la vita e estrany
spir.wikidot.com
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] recursive generator
On Sun, 7 Mar 2010 11:58:05 pm spir wrote: Hello, Is it possible at all to have a recursive generator? Yes. def recursive_generator(n): ... if n == 0: ... return ... yield n ... for i in recursive_generator(n-1): ... yield i ... it = recursive_generator(5) it.next() 5 it.next() 4 it.next() 3 it.next() 2 it.next() 1 it.next() Traceback (most recent call last): File stdin, line 1, in module StopIteration I think at a iterator for a recursive data structure (here, a trie). The following code does not work: it only yields a single value. Like if child.__iter__() were never called. def __iter__(self): ''' Iteration on (key,value) pairs. ''' print '*', if self.holdsEntry: yield (self.key,self.value) for child in self.children: print , child.__iter__() print , raise StopIteration __iter__ should be an ordinary function, not a generator. Something like this should work: # Untested. def __iter__(self): ''' Iteration on (key,value) pairs. ''' def inner(): print '*', # Side effects bad... if self.holdsEntry: yield (self.key,self.value) for child in self.children: print , child.__iter__() print , raise StopIteration return inner() This means that your class won't *itself* be an iterator, but calling iter() on it will return a generator object, which of course is an iterator. If you want to make your class an iterator itself, then you need to follow the iterator protocol. __iter__ must return the instance itself, and next must return (not yield) the next iteration. class MyIterator(object): def __init__(self, n): self.value = n def next(self): if self.value == 0: raise StopIteration self.value //= 2 return self.value def __iter__(self): return self See the discussion in the docs about the iterator protocol: http://docs.python.org/library/stdtypes.html#iterator-types Why is no child.__iter__() executed at all? I imagine this can be caused by the special feature of a generator recording current execution point. That's exactly what generators do: when they reach a yield, execution is halted, but the state of the generator is remembered. Then when you call the next() method, execution resumes. (But then, is it at all possible to have a call in a generator? Or does the issue only appear whan the callee is a generator itself?) Else, the must be an obvious error in my code. I don't understand what you mean. -- Steven D'Aprano ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] recursive generator
Steven D'Aprano, 07.03.2010 14:27: On Sun, 7 Mar 2010 11:58:05 pm spir wrote: def __iter__(self): ''' Iteration on (key,value) pairs. ''' print '*', if self.holdsEntry: yield (self.key,self.value) for child in self.children: print , child.__iter__() print , raise StopIteration __iter__ should be an ordinary function, not a generator. Something like this should work: # Untested. def __iter__(self): ''' Iteration on (key,value) pairs. ''' def inner(): print '*', # Side effects bad... if self.holdsEntry: yield (self.key,self.value) for child in self.children: print , child.__iter__() print , raise StopIteration return inner() That's just an unnecessarily redundant variation on the above. It's perfectly ok if __iter__() is a generator method. Stefan ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
[Tutor] recursive generator
sorry, forgot to forward this to the list.
On Sun, Mar 7, 2010 at 1:58 PM, spir denis.s...@gmail.com wrote:
Hello,
Is it possible at all to have a recursive generator? I think at a iterator
for a recursive data structure (here, a trie). The following code does not
work: it only yields a single value. Like if child.__iter__() were never
called.
def __iter__(self):
''' Iteration on (key,value) pairs. '''
print '*',
if self.holdsEntry:
yield (self.key,self.value)
for child in self.children:
print ,
child.__iter__()
print ,
raise StopIteration
With the debug prints in code above, for e in t: print e outputs:
* ('', 0)
print len(t.children) # -- 9
Why is no child.__iter__() executed at all? I imagine this can be caused by
the special feature of a generator recording current execution point. (But
then, is it at all possible to have a call in a generator? Or does the issue
only appear whan the callee is a generator itself?) Else, the must be an
obvious error in my code.
Denis
remember that child.__iter__ returns a generator object. Merely
calling the function won't do anything. To actually get elements from
a generator object, you need to call next() on the returned iterator,
or iterate over it in another way (e.g. a for loop). I would write
this method more or less like so:
from itertools import chain
def __iter__(self):
this_entry = [(self.key, self.value)] is self.holds_entry else []
return chain(this_entry, *[iter(c) for c in self.children])
(Warning! untested! I'm pretty sure chain will work like this, but you
might have to do a little tweaking)
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] recursive generator
On 7 March 2010 12:58, spir denis.s...@gmail.com wrote:
Hello,
Is it possible at all to have a recursive generator? I think at a iterator
for a recursive data structure (here, a trie). The following code does not
work: it only yields a single value. Like if child.__iter__() were never
called.
def __iter__(self):
''' Iteration on (key,value) pairs. '''
print '*',
if self.holdsEntry:
yield (self.key,self.value)
for child in self.children:
print ,
child.__iter__()
print ,
raise StopIteration
With the debug prints in code above, for e in t: print e outputs:
* ('', 0)
print len(t.children) # -- 9
Why is no child.__iter__() executed at all? I imagine this can be caused by
the special feature of a generator recording current execution point. (But
then, is it at all possible to have a call in a generator? Or does the issue
only appear whan the callee is a generator itself?) Else, the must be an
obvious error in my code.
Denis
--
la vita e estrany
spir.wikidot.com
___
Tutor maillist - tu...@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
You are calling child.__iter__(), but it's return value is being thrown away.
What you want to be doing is something like
def __iter__(self):
if self.holdsEntry:
yield self.entry
for child in self.children:
print
for val in child: #implicit call to child.__iter__()
yield val
print
Then, when the child.__iter__() is called, the returned iterator is
iterated, and the values are passed up the call stack. There's
probably a more terse way of doing this using itertools, but I think
this is probably more readable.
Hope this clears things up (a little, anyway...)
--
Rich Roadie Rich Lovely
Just because you CAN do something, doesn't necessarily mean you SHOULD.
In fact, more often than not, you probably SHOULDN'T. Especially if I
suggested it.
10 re-discover BASIC
20 ???
30 PRINT Profit
40 GOTO 10
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] recursive generator
On Sun, 7 Mar 2010 17:20:07 +0100
Hugo Arts hugo.yo...@gmail.com wrote:
On Sun, Mar 7, 2010 at 1:58 PM, spir denis.s...@gmail.com wrote:
Hello,
Is it possible at all to have a recursive generator? I think at a iterator
for a recursive data structure (here, a trie). The following code does not
work: it only yields a single value. Like if child.__iter__() were never
called.
def __iter__(self):
''' Iteration on (key,value) pairs. '''
print '*',
if self.holdsEntry:
yield (self.key,self.value)
for child in self.children:
print ,
child.__iter__()
print ,
raise StopIteration
With the debug prints in code above, for e in t: print e outputs:
* ('', 0)
print len(t.children) # -- 9
Why is no child.__iter__() executed at all? I imagine this can be caused by
the special feature of a generator recording current execution point. (But
then, is it at all possible to have a call in a generator? Or does the
issue only appear whan the callee is a generator itself?) Else, the must be
an obvious error in my code.
Denis
remember that child.__iter__ returns a generator object. Merely
calling the function won't do anything. To actually get elements from
a generator object, you need to call next() on the returned iterator,
or iterate over it in another way (e.g. a for loop). I would write
this method more or less like so:
from itertools import chain
def __iter__(self):
this_entry = [(self.key, self.value)] is self.holds_entry else []
return chain(this_entry, *[iter(c) for c in self.children])
(Warning! untested! I'm pretty sure chain will work like this, but you
might have to do a little tweaking)
@ Hugo Steven
Thank you very much. I'll study your proposals as soon as I can, then tell you
about the results.
In the meanwhile, I (recursively) constructed the collection of entries and
returned iter(collection). [This works, indeed, but I also want do know how to
properly build a recursive iterator.]
Denis
--
la vita e estrany
spir.wikidot.com
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
