question about generators

[David Eppstein]

In article <7xbs83iy9p.fsf at ruckus.brouhaha.com>,
 Paul Rubin <phr-n2002b at NOSPAMnightsong.com> wrote:

> Anyway, the problem you're having where yield doesn't really work like
> print comes from this implementation limitation, not anything inherent
> in the notion of generators.

I think it's also inherent in the syntax chosen for simple generators -- 
there's no way of distinguishing a function that when called returns a 
new simple generator (call this a generator factory) from a function 
that when called routes its yields to the outlet of its caller (call 
this a subgenerator).

Tim has proposed a "yield every x()" syntactic-sugar that would allow 
you to take a generator factory x and use it as if it were a 
subgenerator.  This seems a reasonable idea, but there is an efficiency 
argument for having a direct syntax for subgenerators:

Suppose you have a long call chain of "yield every" statements (as can 
occur for instance in the tree traversal example from the simple 
generator PEP) -- say the length of the chain is L.  Then the obvious 
implementation is to simply expand each "yield every x" statement into 
"for i in x: yield i".  But, this would incur O(L) overhead for each 
generated item.  One could try to speed this up by using some kind of 
balanced tree data structure to keep track of which generators are 
participating in "yield every" statements, but this seems difficult 
because of the complication that a single x may occur in multiple 
simultaneous "yield every" statements.

On the other hand, suppose you have a syntax for defining subgenerators, 
and a long call chain of subgenerators.  Each subgenerator can point 
directly to the output point for its yields (known at the time the 
subgenerator is created and never changed), so the time per yielded item 
is only a constant.

-- 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein at ics.uci.edu http://www.ics.uci.edu/~eppstein/