Let's try a simple generator:
"Falling off the end" stops the generator:
Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "<stdin>", line 2, in g
"return" also stops the generator:
... yield 2 # never reached
Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "<stdin>", line 3, in f
>>> g.next() # once stopped, can't be resumed
Traceback (most recent call last):
File "<stdin>", line 1, in ?
"raise StopIteration" stops the generator too:
... yield 2 # never reached
Traceback (most recent call last):
File "<stdin>", line 1, in ?
Traceback (most recent call last):
File "<stdin>", line 1, in ?
However, they are not exactly equivalent:
This may be surprising at first:
Let's create an alternate range() function implemented as a generator:
Generators always return to the most recent caller:
... print "creator", r.next()
Generators can call other generators:
# The examples from PEP 255.
Restriction: A generator cannot be resumed while it is actively
Traceback (most recent call last):
File "<string>", line 2, in g
ValueError: generator already executing
Note that return isn't always equivalent to raising StopIteration: the
difference lies in how enclosing try/except constructs are treated.
because, as in any function, return simply exits, but
because StopIteration is captured by a bare "except", as is any
Specification: Generators and Exception Propagation
... yield f() # the zero division exception propagates
... yield 42 # and we'll never get here
Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "<stdin>", line 2, in g
File "<stdin>", line 2, in f
ZeroDivisionError: integer division or modulo by zero
>>> k.next() # and the generator cannot be resumed
Traceback (most recent call last):
File "<stdin>", line 1, in ?
Specification: Try/Except/Finally
... yield 3 # never get here
... except ZeroDivisionError:
... yield 7 # the "raise" above stops this
[1, 2, 4, 5, 8, 9, 10, 11]
Guido's binary tree example.
>>> # A binary tree class.
... def __init__(self, label, left=None, right=None):
... def __repr__(self, level=0, indent=" "):
... s = level*indent + repr(self.label)
... s = s + "\\n" + self.left.__repr__(level+1, indent)
... s = s + "\\n" + self.right.__repr__(level+1, indent)
>>> # Create a Tree from a list.
... return Tree(list[i], tree(list[:i]), tree(list[i+1:]))
>>> # Show it off: create a tree.
>>> t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
>>> # A recursive generator that generates Tree labels in in-order.
... for x in inorder(t.left):
... for x in inorder(t.right):
>>> # Show it off: create a tree.
>>> t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
>>> # Print the nodes of the tree in in-order.
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
>>> # A non-recursive generator.
... while not node.right:
>>> # Exercise the non-recursive generator.
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
# Examples from Iterator-List and Python-Dev and c.l.py.
The difference between yielding None and returning it.
Ensure that explicitly raising StopIteration acts like any other exception
in try/except, not like a return.
Next one was posted to c.l.py.
... "Generate all combinations of k elements from list x."
... first, rest = x[0], x[1:]
... # A combination does or doesn't contain first.
... # If it does, the remainder is a k-1 comb of rest.
... for c in gcomb(rest, k-1):
... # If it doesn't contain first, it's a k comb of rest.
... for c in gcomb(rest, k):
>>> for k in range(len(seq) + 2):
... print "%d-combs of %s:" % (k, seq)
... for c in gcomb(seq, k):
From the Iterators list, about the types of these things.
>>> [s for s in dir(i) if not s.startswith('_')]
['gi_frame', 'gi_running', 'next']
x.next() -> the next value, or raise StopIteration
>>> isinstance(i, types.GeneratorType)
Traceback (most recent call last):
TypeError: readonly attribute
A clever union-find implementation from c.l.py, due to David Eppstein.
Sent: Friday, June 29, 2001 12:16 PM
To: python-list@python.org
Subject: Re: PEP 255: Simple Generators
... def __init__(self, name):
... self.generator = self.generate()
... while not self.parent:
... for x in self.parent.generator:
... return self.generator.next()
... def union(self, parent):
... raise ValueError("Sorry, I'm not a root!")
>>> names = "ABCDEFGHIJKLM"
>>> sets = [disjointSet(name) for name in names]
>>> gen = random.WichmannHill(42)
... print "%s->%s" % (s, s.find()),
... s1 = gen.choice(roots)
... s2 = gen.choice(roots)
... print "merged", s1, "into", s2
A->A B->B C->C D->D E->E F->F G->G H->H I->I J->J K->K L->L M->M
A->A B->B C->C D->G E->E F->F G->G H->H I->I J->J K->K L->L M->M
A->A B->B C->F D->G E->E F->F G->G H->H I->I J->J K->K L->L M->M
A->A B->B C->F D->G E->E F->F G->G H->H I->I J->J K->K L->A M->M
A->A B->B C->F D->G E->E F->F G->G H->E I->I J->J K->K L->A M->M
A->A B->E C->F D->G E->E F->F G->G H->E I->I J->J K->K L->A M->M
A->A B->E C->F D->G E->E F->F G->G H->E I->I J->G K->K L->A M->M
A->A B->G C->F D->G E->G F->F G->G H->G I->I J->G K->K L->A M->M
A->A B->G C->F D->G E->G F->F G->G H->G I->I J->G K->K L->A M->G
A->A B->G C->F D->G E->G F->F G->G H->G I->K J->G K->K L->A M->G
A->A B->G C->F D->G E->G F->F G->G H->G I->A J->G K->A L->A M->G
A->A B->G C->A D->G E->G F->A G->G H->G I->A J->G K->A L->A M->G
A->G B->G C->G D->G E->G F->G G->G H->G I->G J->G K->G L->G M->G
# Fun tests (for sufficiently warped notions of "fun").
Build up to a recursive Sieve of Eratosthenes generator.
... return [g.next() for i in range(n)]
>>> firstn(intsfrom(5), 7)
>>> def exclude_multiples(n, ints):
>>> firstn(exclude_multiples(3, intsfrom(1)), 6)
... not_divisible_by_prime = exclude_multiples(prime, ints)
... for p in sieve(not_divisible_by_prime):
>>> primes = sieve(intsfrom(2))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
Another famous problem: generate all integers of the form
in increasing order, where i,j,k >= 0. Trickier than it may look at first!
Try writing it without generators, and correctly, and without generating
3 internal results for each result output.
>>> firstn(times(10, intsfrom(1)), 10)
[10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
The following works, but is doing a whale of a lot of redundant work --
it's not clear how to get the internal uses of m235 to share a single
generator. Note that me_times2 (etc) each need to see every element in the
result sequence. So this is an example where lazy lists are more natural
(you can look at the head of a lazy list any number of times).
... me_times2 = times(2, m235())
... me_times3 = times(3, m235())
... me_times5 = times(5, m235())
... for i in merge(merge(me_times2,
Don't print "too many" of these -- the implementation above is extremely
inefficient: each call of m235() leads to 3 recursive calls, and in
turn each of those 3 more, and so on, and so on, until we've descended
enough levels to satisfy the print stmts. Very odd: when I printed 5
lines of results below, this managed to screw up Win98's malloc in "the
usual" way, i.e. the heap grew over 4Mb so Win98 started fragmenting
address space, and it *looked* like a very slow leak.
... print firstn(result, 15)
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]
[25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80]
[81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192]
Heh. Here's one way to get a shared list, complete with an excruciating
namespace renaming trick. The *pretty* part is that the times() and merge()
functions can be reused as-is, because they only assume their stream
arguments are iterable -- a LazyList is the same as a generator to times().
... def __init__(self, g):
... def __getitem__(self, i):
... sofar, fetch = self.sofar, self.fetch
... while i >= len(sofar):
... sofar.append(fetch())
... # Gack: m235 below actually refers to a LazyList.
... me_times2 = times(2, m235)
... me_times3 = times(3, m235)
... me_times5 = times(5, m235)
... for i in merge(merge(me_times2,
Print as many of these as you like -- *this* implementation is memory-
>>> m235 = LazyList(m235())
... print [m235[j] for j in range(15*i, 15*(i+1))]
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]
[25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80]
[81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192]
[200, 216, 225, 240, 243, 250, 256, 270, 288, 300, 320, 324, 360, 375, 384]
[400, 405, 432, 450, 480, 486, 500, 512, 540, 576, 600, 625, 640, 648, 675]
Ye olde Fibonacci generator, LazyList style.
... yield g.next() + h.next()
... g.next() # throw first away
... for s in sum(iter(fib),
>>> fib = LazyList(fibgen(1, 2))
>>> firstn(iter(fib), 17)
[1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584]
# syntax_tests mostly provokes SyntaxErrors. Also fiddling with #if 0
Traceback (most recent call last):
SyntaxError: 'return' with argument inside generator (<doctest test.test_generators.__test__.syntax[0]>, line 2)
Traceback (most recent call last):
SyntaxError: 'return' with argument inside generator (<doctest test.test_generators.__test__.syntax[1]>, line 3)
"return None" is not the same as "return" in a generator:
Traceback (most recent call last):
SyntaxError: 'return' with argument inside generator (<doctest test.test_generators.__test__.syntax[2]>, line 3)
Traceback (most recent call last):
SyntaxError: 'yield' not allowed in a 'try' block with a 'finally' clause (<doctest test.test_generators.__test__.syntax[4]>, line 3)
... except ZeroDivisionError:
... yield 666 # bad because *outer* try has finally
Traceback (most recent call last):
SyntaxError: 'yield' not allowed in a 'try' block with a 'finally' clause (<doctest test.test_generators.__test__.syntax[5]>, line 6)
... except ZeroDivisionError:
Traceback (most recent call last):
SyntaxError: invalid syntax
Traceback (most recent call last):
SyntaxError: invalid syntax
... yield 2 # don't blink
... lambda x: x # shouldn't trigger here
... return 3 # but *this* sucks (line 8)
... yield 2 # because it's a generator
Traceback (most recent call last):
SyntaxError: 'return' with argument inside generator (<doctest test.test_generators.__test__.syntax[22]>, line 8)
This one caused a crash (see SF bug 567538):
Traceback (most recent call last):
# conjoin is a simple backtracking generator, named in honor of Icon's
# "conjunction" control structure. Pass a list of no-argument functions
# that return iterable objects. Easiest to explain by example: assume the
# function list [x, y, z] is passed. Then conjoin acts like:
# So some 3-lists of values *may* be generated, each time we successfully
# get into the innermost loop. If an iterator fails (is exhausted) before
# then, it "backtracks" to get the next value from the nearest enclosing
# iterator (the one "to the left"), and starts all over again at the next
# slot (pumps a fresh iterator). Of course this is most useful when the
# iterators have side-effects, so that which values *can* be generated at
# each slot depend on the values iterated at previous slots.
values
= [None] * len(gs
)
def gen(i
, values
=values
):
for values
[i
] in gs
[i
]():
# That works fine, but recursing a level and checking i against len(gs) for
# each item produced is inefficient. By doing manual loop unrolling across
# generator boundaries, it's possible to eliminate most of that overhead.
# This isn't worth the bother *in general* for generators, but conjoin() is
# a core building block for some CPU-intensive generator applications.
# Do one loop nest at time recursively, until the # of loop nests
# remaining is divisible by 3.
def gen(i
, values
=values
):
for values
[i
] in gs
[i
]():
# Do three loop nests at a time, recursing only if at least three more
# remain. Don't call directly: this is an internal optimization for
def _gen3(i
, values
=values
):
assert i
< n
and (n
-i
) % 3 == 0
ip1
, ip2
, ip3
= i
+1, i
+2, i
+3
# These are the last three, so we can yield values directly.
# At least 6 loop nests remain; peel off 3 and recurse for the
# And one more approach: For backtracking apps like the Knight's Tour
# solver below, the number of backtracking levels can be enormous (one
# level per square, for the Knight's Tour, so that e.g. a 100x100 board
# needs 10,000 levels). In such cases Python is likely to run out of
# stack space due to recursion. So here's a recursion-free version of
# NOTE WELL: This allows large problems to be solved with only trivial
# demands on stack space. Without explicitly resumable generators, this is
# much harder to achieve. OTOH, this is much slower (up to a factor of 2)
# than the fancy unrolled recursive conjoin.
def flat_conjoin(gs
): # rename to conjoin to run tests with this instead
_StopIteration
= StopIteration # make local because caught a *lot*
it
= iters
[i
] = gs
[i
]().next
# Backtrack until an older iterator can be resumed.
# Success! Start fresh at next level.
# A conjoin-based N-Queens solver.
# Assign a unique int to each column and diagonal.
# columns: n of those, range(n).
# NW-SE diagonals: 2n-1 of these, i-j unique and invariant along
# each, smallest i-j is 0-(n-1) = 1-n, so add n-1 to shift to 0-
# NE-SW diagonals: 2n-1 of these, i+j unique and invariant along
# each, smallest i+j is 0, largest is 2n-2.
# For each square, compute a bit vector of the columns and
# diagonals it covers, and for each row compute a function that
# generates the possiblities for the columns in that row.
rowuses
= [(1L << j
) |
# column ordinal
(1L << (n
+ i
-j
+ n
-1)) |
# NW-SE ordinal
(1L << (n
+ 2*n
-1 + i
+j
)) # NE-SW ordinal
def rowgen(rowuses
=rowuses
):
if uses
& self
.used
== 0:
self
.rowgenerators
.append(rowgen
)
for row2col
in conjoin(self
.rowgenerators
):
def printsolution(self
, row2col
):
squares
= [" " for j
in range(n
)]
squares
[row2col
[i
]] = "Q"
print "|" + "|".join(squares
) + "|"
# A conjoin-based Knight's Tour solver. This is pretty sophisticated
# (e.g., when used with flat_conjoin above, and passing hard=1 to the
# constructor, a 200x200 Knight's Tour was found quickly -- note that we're
# creating 10s of thousands of generators then!), and is lengthy.
def __init__(self
, m
, n
, hard
=0):
# solve() will set up succs[i] to be a list of square #i's
# Remove i0 from each of its successor's successor lists, i.e.
# successors can't go back to i0 again. Return 0 if we can
# detect this makes a solution impossible, else return 1.
def remove_from_successors(i0
, len=len):
# If we remove all exits from a free square, we're dead:
# even if we move to it next, we can't leave it again.
# If we create a square with one exit, we must visit it next;
# else somebody else will have to visit it, and since there's
# only one adjacent, there won't be a way to leave it again.
# Finelly, if we create more than one free square with a
# single exit, we can only move to one of them next, leaving
# the other one a dead end.
return ne0
== 0 and ne1
< 2
# Put i0 back in each of its successor's successor lists.
def add_to_successors(i0
):
# Generate the first move.
# Since we're looking for a cycle, it doesn't matter where we
# start. Starting in a corner makes the 2nd move easy.
corner
= self
.coords2index(0, 0)
remove_from_successors(corner
)
add_to_successors(corner
)
# Generate the second moves.
corner
= self
.coords2index(0, 0)
assert self
.lastij
== corner
# i.e., we started in the corner
assert len(succs
[corner
]) == 2
assert self
.coords2index(1, 2) in succs
[corner
]
assert self
.coords2index(2, 1) in succs
[corner
]
# Only two choices. Whichever we pick, the other must be the
# square picked on move m*n, as it's the only way to get back
# to (0, 0). Save its index in self.final so that moves before
# the last know it must be kept free.
for i
, j
in (1, 2), (2, 1):
this
= self
.coords2index(i
, j
)
final
= self
.coords2index(3-i
, 3-j
)
remove_from_successors(this
)
succs
[final
].append(corner
)
succs
[final
].remove(corner
)
# Generate moves 3 thru m*n-1.
# If some successor has only one exit, must take it.
# Else favor successors with fewer exits.
for i
in succs
[self
.lastij
]:
assert e
> 0, "else remove_from_successors() pruning flawed"
candidates
.append((e
, i
))
if remove_from_successors(i
):
# Generate moves 3 thru m*n-1. Alternative version using a
# stronger (but more expensive) heuristic to order successors.
# Since the # of backtracking levels is m*n, a poor move early on
# can take eons to undo. Smallest square board for which this
# matters a lot is 52x52.
def advance_hard(vmid
=(m
-1)/2.0, hmid
=(n
-1)/2.0, len=len):
# If some successor has only one exit, must take it.
# Else favor successors with fewer exits.
# Break ties via max distance from board centerpoint (favor
# corners and edges whenever possible).
for i
in succs
[self
.lastij
]:
assert e
> 0, "else remove_from_successors() pruning flawed"
i1
, j1
= self
.index2coords(i
)
d
= (i1
- vmid
)**2 + (j1
- hmid
)**2
candidates
.append((e
, -d
, i
))
for e
, d
, i
in candidates
:
if remove_from_successors(i
):
# Generate the last move.
assert self
.final
in succs
[self
.lastij
]
self
.squaregenerators
= [first
]
self
.squaregenerators
= [first
, second
] + \
[hard
and advance_hard
or advance
] * (m
*n
- 3) + \
def coords2index(self
, i
, j
):
def index2coords(self
, index
):
assert 0 <= index
< self
.m
* self
.n
return divmod(index
, self
.n
)
offsets
= [( 1, 2), ( 2, 1), ( 2, -1), ( 1, -2),
(-1, -2), (-2, -1), (-2, 1), (-1, 2)]
s
= [c2i(i
+io
, j
+jo
) for io
, jo
in offsets
for x
in conjoin(self
.squaregenerators
):
def printsolution(self
, x
):
format
= "%" + str(w
) + "d"
squares
= [[None] * n
for i
in range(m
)]
i1
, j1
= self
.index2coords(i
)
squares
[i1
][j1
] = format
% k
sep
= "+" + ("-" * w
+ "+") * n
print "|" + "|".join(row
) + "|"
Generate the 3-bit binary numbers in order. This illustrates dumbest-
possible use of conjoin, just to generate the full cross-product.
>>> for c in conjoin([lambda: iter((0, 1))] * 3):
For efficiency in typical backtracking apps, conjoin() yields the same list
object each time. So if you want to save away a full account of its
generated sequence, you need to copy its results.
>>> def gencopy(iterator):
... all = list(gencopy(conjoin([lambda: iter((0, 1))] * n)))
... print n, len(all), all[0] == [0] * n, all[-1] == [1] * n
And run an 8-queens solver.
>>> for row2col in q.solve():
... print "Solution", count
... q.printsolution(row2col)
>>> print count, "solutions in all."
And run a Knight's Tour on a 10x10 board. Note that there are about
20,000 solutions even on a 6x6 board, so don't dare run this to exhaustion.
... print "Solution", count
+---+---+---+---+---+---+---+---+---+---+
| 1| 58| 27| 34| 3| 40| 29| 10| 5| 8|
+---+---+---+---+---+---+---+---+---+---+
| 26| 35| 2| 57| 28| 33| 4| 7| 30| 11|
+---+---+---+---+---+---+---+---+---+---+
| 59|100| 73| 36| 41| 56| 39| 32| 9| 6|
+---+---+---+---+---+---+---+---+---+---+
| 74| 25| 60| 55| 72| 37| 42| 49| 12| 31|
+---+---+---+---+---+---+---+---+---+---+
| 61| 86| 99| 76| 63| 52| 47| 38| 43| 50|
+---+---+---+---+---+---+---+---+---+---+
| 24| 75| 62| 85| 54| 71| 64| 51| 48| 13|
+---+---+---+---+---+---+---+---+---+---+
| 87| 98| 91| 80| 77| 84| 53| 46| 65| 44|
+---+---+---+---+---+---+---+---+---+---+
| 90| 23| 88| 95| 70| 79| 68| 83| 14| 17|
+---+---+---+---+---+---+---+---+---+---+
| 97| 92| 21| 78| 81| 94| 19| 16| 45| 66|
+---+---+---+---+---+---+---+---+---+---+
| 22| 89| 96| 93| 20| 69| 82| 67| 18| 15|
+---+---+---+---+---+---+---+---+---+---+
+---+---+---+---+---+---+---+---+---+---+
| 1| 58| 27| 34| 3| 40| 29| 10| 5| 8|
+---+---+---+---+---+---+---+---+---+---+
| 26| 35| 2| 57| 28| 33| 4| 7| 30| 11|
+---+---+---+---+---+---+---+---+---+---+
| 59|100| 73| 36| 41| 56| 39| 32| 9| 6|
+---+---+---+---+---+---+---+---+---+---+
| 74| 25| 60| 55| 72| 37| 42| 49| 12| 31|
+---+---+---+---+---+---+---+---+---+---+
| 61| 86| 99| 76| 63| 52| 47| 38| 43| 50|
+---+---+---+---+---+---+---+---+---+---+
| 24| 75| 62| 85| 54| 71| 64| 51| 48| 13|
+---+---+---+---+---+---+---+---+---+---+
| 87| 98| 89| 80| 77| 84| 53| 46| 65| 44|
+---+---+---+---+---+---+---+---+---+---+
| 90| 23| 92| 95| 70| 79| 68| 83| 14| 17|
+---+---+---+---+---+---+---+---+---+---+
| 97| 88| 21| 78| 81| 94| 19| 16| 45| 66|
+---+---+---+---+---+---+---+---+---+---+
| 22| 91| 96| 93| 20| 69| 82| 67| 18| 15|
+---+---+---+---+---+---+---+---+---+---+
Generators are weakly referencable:
>>> wr = weakref.ref(gen)
>>> p = weakref.proxy(gen)
Generator-iterators are weakly referencable as well:
>>> p = weakref.proxy(gi)
__test__
= {"tut": tutorial_tests
,
"conjoin": conjoin_tests
,
"weakref": weakref_tests
,
# Magic test name that regrtest.py invokes *after* importing this module.
# This worms around a bootstrap problem.
# Note that doctest and regrtest both look in sys.argv for a "-v" argument,
# so this works as expected in both ways of running regrtest.
def test_main(verbose
=None):
from test
import test_support
, test_generators
test_support
.run_doctest(test_generators
, verbose
)
# This part isn't needed for regrtest, but for running the test directly.
if __name__
== "__main__":