Re: [Tutor] recursive generator
On Sun, 7 Mar 2010 17:20:07 +0100
Hugo Arts wrote:
> On Sun, Mar 7, 2010 at 1:58 PM, spir 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
Re: [Tutor] recursive generator
On 7 March 2010 12:58, spir 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
Here's a (more or less) useful example. It generates the "nth triangular
series" (my term), n=2 is the triangular numbers, n=3 the tetrahedral numbers
(n has a correspondence to dimension). Each series is the sum of the elements
of the previous one. They are also the columns of Pascal's Triangle.
Probably only "useful" if you enjoy playing around with math.
def triangular(n):
if n == 0:
while True:
yield 1
else:
g = triangular(n-1)
a = 0
while True:
a += g.next()
yield a
I wouldn't use that to build Pascal's triangle, by the way (usually you want
it rowwise). Here's my code.
def pascal():
r = 0
l = [1]
yield l
while True:
l = [1] + [ l[i] + l[i+1] for i in range(r) ] + [1]
r += 1
yield l
>>> g=pascal()
>>> for i in range(9):
... print ' '.join(['%2d'%(i,) for i in g.next()])
...
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
Here are the triangular-ly generated numbers (I made them a square, just to
illustrate an interesting property.)
>>> for i in range(7):
... g=triangular(i)
... print ' '.join(['%3d'%(j,) for j in [g.next() for k in range(7)]])
...
1 1 1 1 1 1 1
1 2 3 4 5 6 7
1 3 6 10 15 21 28
1 4 10 20 35 56 84
1 5 15 35 70 126 210
1 6 21 56 126 252 462
1 7 28 84 210 462 924
Cheers
On Sunday 07 March 2010, spir 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
>
___
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 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 Mon, 8 Mar 2010 01:49:21 am Stefan Behnel wrote: > Steven D'Aprano, 07.03.2010 14:27: > > __iter__ should be an ordinary function, not a generator. Something > > like this should work: [...] > That's just an unnecessarily redundant variation on the above. It's > perfectly ok if __iter__() is a generator method. So it is. Thank you for the correction. -- 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
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 "", line 1, in 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
[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
