0001 tutorial_tests = """ 0002 Let's try a simple generator: 0003 0004 >>> def f(): 0005 ... yield 1 0006 ... yield 2 0007 0008 >>> for i in f(): 0009 ... print i 0010 1 0011 2 0012 >>> g = f() 0013 >>> g.next() 0014 1 0015 >>> g.next() 0016 2 0017 0018 "Falling off the end" stops the generator: 0019 0020 >>> g.next() 0021 Traceback (most recent call last): 0022 File "<stdin>", line 1, in ? 0023 File "<stdin>", line 2, in g 0024 StopIteration 0025 0026 "return" also stops the generator: 0027 0028 >>> def f(): 0029 ... yield 1 0030 ... return 0031 ... yield 2 # never reached 0032 ... 0033 >>> g = f() 0034 >>> g.next() 0035 1 0036 >>> g.next() 0037 Traceback (most recent call last): 0038 File "<stdin>", line 1, in ? 0039 File "<stdin>", line 3, in f 0040 StopIteration 0041 >>> g.next() # once stopped, can't be resumed 0042 Traceback (most recent call last): 0043 File "<stdin>", line 1, in ? 0044 StopIteration 0045 0046 "raise StopIteration" stops the generator too: 0047 0048 >>> def f(): 0049 ... yield 1 0050 ... raise StopIteration 0051 ... yield 2 # never reached 0052 ... 0053 >>> g = f() 0054 >>> g.next() 0055 1 0056 >>> g.next() 0057 Traceback (most recent call last): 0058 File "<stdin>", line 1, in ? 0059 StopIteration 0060 >>> g.next() 0061 Traceback (most recent call last): 0062 File "<stdin>", line 1, in ? 0063 StopIteration 0064 0065 However, they are not exactly equivalent: 0066 0067 >>> def g1(): 0068 ... try: 0069 ... return 0070 ... except: 0071 ... yield 1 0072 ... 0073 >>> list(g1()) 0074 [] 0075 0076 >>> def g2(): 0077 ... try: 0078 ... raise StopIteration 0079 ... except: 0080 ... yield 42 0081 >>> print list(g2()) 0082 [42] 0083 0084 This may be surprising at first: 0085 0086 >>> def g3(): 0087 ... try: 0088 ... return 0089 ... finally: 0090 ... yield 1 0091 ... 0092 >>> list(g3()) 0093 [1] 0094 0095 Let's create an alternate range() function implemented as a generator: 0096 0097 >>> def yrange(n): 0098 ... for i in range(n): 0099 ... yield i 0100 ... 0101 >>> list(yrange(5)) 0102 [0, 1, 2, 3, 4] 0103 0104 Generators always return to the most recent caller: 0105 0106 >>> def creator(): 0107 ... r = yrange(5) 0108 ... print "creator", r.next() 0109 ... return r 0110 ... 0111 >>> def caller(): 0112 ... r = creator() 0113 ... for i in r: 0114 ... print "caller", i 0115 ... 0116 >>> caller() 0117 creator 0 0118 caller 1 0119 caller 2 0120 caller 3 0121 caller 4 0122 0123 Generators can call other generators: 0124 0125 >>> def zrange(n): 0126 ... for i in yrange(n): 0127 ... yield i 0128 ... 0129 >>> list(zrange(5)) 0130 [0, 1, 2, 3, 4] 0131 0132 """ 0133 0134 # The examples from PEP 255. 0135 0136 pep_tests = """ 0137 0138 Specification: Yield 0139 0140 Restriction: A generator cannot be resumed while it is actively 0141 running: 0142 0143 >>> def g(): 0144 ... i = me.next() 0145 ... yield i 0146 >>> me = g() 0147 >>> me.next() 0148 Traceback (most recent call last): 0149 ... 0150 File "<string>", line 2, in g 0151 ValueError: generator already executing 0152 0153 Specification: Return 0154 0155 Note that return isn't always equivalent to raising StopIteration: the 0156 difference lies in how enclosing try/except constructs are treated. 0157 For example, 0158 0159 >>> def f1(): 0160 ... try: 0161 ... return 0162 ... except: 0163 ... yield 1 0164 >>> print list(f1()) 0165 [] 0166 0167 because, as in any function, return simply exits, but 0168 0169 >>> def f2(): 0170 ... try: 0171 ... raise StopIteration 0172 ... except: 0173 ... yield 42 0174 >>> print list(f2()) 0175 [42] 0176 0177 because StopIteration is captured by a bare "except", as is any 0178 exception. 0179 0180 Specification: Generators and Exception Propagation 0181 0182 >>> def f(): 0183 ... return 1//0 0184 >>> def g(): 0185 ... yield f() # the zero division exception propagates 0186 ... yield 42 # and we'll never get here 0187 >>> k = g() 0188 >>> k.next() 0189 Traceback (most recent call last): 0190 File "<stdin>", line 1, in ? 0191 File "<stdin>", line 2, in g 0192 File "<stdin>", line 2, in f 0193 ZeroDivisionError: integer division or modulo by zero 0194 >>> k.next() # and the generator cannot be resumed 0195 Traceback (most recent call last): 0196 File "<stdin>", line 1, in ? 0197 StopIteration 0198 >>> 0199 0200 Specification: Try/Except/Finally 0201 0202 >>> def f(): 0203 ... try: 0204 ... yield 1 0205 ... try: 0206 ... yield 2 0207 ... 1//0 0208 ... yield 3 # never get here 0209 ... except ZeroDivisionError: 0210 ... yield 4 0211 ... yield 5 0212 ... raise 0213 ... except: 0214 ... yield 6 0215 ... yield 7 # the "raise" above stops this 0216 ... except: 0217 ... yield 8 0218 ... yield 9 0219 ... try: 0220 ... x = 12 0221 ... finally: 0222 ... yield 10 0223 ... yield 11 0224 >>> print list(f()) 0225 [1, 2, 4, 5, 8, 9, 10, 11] 0226 >>> 0227 0228 Guido's binary tree example. 0229 0230 >>> # A binary tree class. 0231 >>> class Tree: 0232 ... 0233 ... def __init__(self, label, left=None, right=None): 0234 ... self.label = label 0235 ... self.left = left 0236 ... self.right = right 0237 ... 0238 ... def __repr__(self, level=0, indent=" "): 0239 ... s = level*indent + repr(self.label) 0240 ... if self.left: 0241 ... s = s + "\\n" + self.left.__repr__(level+1, indent) 0242 ... if self.right: 0243 ... s = s + "\\n" + self.right.__repr__(level+1, indent) 0244 ... return s 0245 ... 0246 ... def __iter__(self): 0247 ... return inorder(self) 0248 0249 >>> # Create a Tree from a list. 0250 >>> def tree(list): 0251 ... n = len(list) 0252 ... if n == 0: 0253 ... return [] 0254 ... i = n // 2 0255 ... return Tree(list[i], tree(list[:i]), tree(list[i+1:])) 0256 0257 >>> # Show it off: create a tree. 0258 >>> t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ") 0259 0260 >>> # A recursive generator that generates Tree labels in in-order. 0261 >>> def inorder(t): 0262 ... if t: 0263 ... for x in inorder(t.left): 0264 ... yield x 0265 ... yield t.label 0266 ... for x in inorder(t.right): 0267 ... yield x 0268 0269 >>> # Show it off: create a tree. 0270 >>> t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ") 0271 >>> # Print the nodes of the tree in in-order. 0272 >>> for x in t: 0273 ... print x, 0274 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 0275 0276 >>> # A non-recursive generator. 0277 >>> def inorder(node): 0278 ... stack = [] 0279 ... while node: 0280 ... while node.left: 0281 ... stack.append(node) 0282 ... node = node.left 0283 ... yield node.label 0284 ... while not node.right: 0285 ... try: 0286 ... node = stack.pop() 0287 ... except IndexError: 0288 ... return 0289 ... yield node.label 0290 ... node = node.right 0291 0292 >>> # Exercise the non-recursive generator. 0293 >>> for x in t: 0294 ... print x, 0295 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 0296 0297 """ 0298 0299 # Examples from Iterator-List and Python-Dev and c.l.py. 0300 0301 email_tests = """ 0302 0303 The difference between yielding None and returning it. 0304 0305 >>> def g(): 0306 ... for i in range(3): 0307 ... yield None 0308 ... yield None 0309 ... return 0310 >>> list(g()) 0311 [None, None, None, None] 0312 0313 Ensure that explicitly raising StopIteration acts like any other exception 0314 in try/except, not like a return. 0315 0316 >>> def g(): 0317 ... yield 1 0318 ... try: 0319 ... raise StopIteration 0320 ... except: 0321 ... yield 2 0322 ... yield 3 0323 >>> list(g()) 0324 [1, 2, 3] 0325 0326 Next one was posted to c.l.py. 0327 0328 >>> def gcomb(x, k): 0329 ... "Generate all combinations of k elements from list x." 0330 ... 0331 ... if k > len(x): 0332 ... return 0333 ... if k == 0: 0334 ... yield [] 0335 ... else: 0336 ... first, rest = x[0], x[1:] 0337 ... # A combination does or doesn't contain first. 0338 ... # If it does, the remainder is a k-1 comb of rest. 0339 ... for c in gcomb(rest, k-1): 0340 ... c.insert(0, first) 0341 ... yield c 0342 ... # If it doesn't contain first, it's a k comb of rest. 0343 ... for c in gcomb(rest, k): 0344 ... yield c 0345 0346 >>> seq = range(1, 5) 0347 >>> for k in range(len(seq) + 2): 0348 ... print "%d-combs of %s:" % (k, seq) 0349 ... for c in gcomb(seq, k): 0350 ... print " ", c 0351 0-combs of [1, 2, 3, 4]: 0352 [] 0353 1-combs of [1, 2, 3, 4]: 0354 [1] 0355 [2] 0356 [3] 0357 [4] 0358 2-combs of [1, 2, 3, 4]: 0359 [1, 2] 0360 [1, 3] 0361 [1, 4] 0362 [2, 3] 0363 [2, 4] 0364 [3, 4] 0365 3-combs of [1, 2, 3, 4]: 0366 [1, 2, 3] 0367 [1, 2, 4] 0368 [1, 3, 4] 0369 [2, 3, 4] 0370 4-combs of [1, 2, 3, 4]: 0371 [1, 2, 3, 4] 0372 5-combs of [1, 2, 3, 4]: 0373 0374 From the Iterators list, about the types of these things. 0375 0376 >>> def g(): 0377 ... yield 1 0378 ... 0379 >>> type(g) 0380 <type 'function'> 0381 >>> i = g() 0382 >>> type(i) 0383 <type 'generator'> 0384 >>> [s for s in dir(i) if not s.startswith('_')] 0385 ['gi_frame', 'gi_running', 'next'] 0386 >>> print i.next.__doc__ 0387 x.next() -> the next value, or raise StopIteration 0388 >>> iter(i) is i 0389 True 0390 >>> import types 0391 >>> isinstance(i, types.GeneratorType) 0392 True 0393 0394 And more, added later. 0395 0396 >>> i.gi_running 0397 0 0398 >>> type(i.gi_frame) 0399 <type 'frame'> 0400 >>> i.gi_running = 42 0401 Traceback (most recent call last): 0402 ... 0403 TypeError: readonly attribute 0404 >>> def g(): 0405 ... yield me.gi_running 0406 >>> me = g() 0407 >>> me.gi_running 0408 0 0409 >>> me.next() 0410 1 0411 >>> me.gi_running 0412 0 0413 0414 A clever union-find implementation from c.l.py, due to David Eppstein. 0415 Sent: Friday, June 29, 2001 12:16 PM 0416 To: python-list@python.org 0417 Subject: Re: PEP 255: Simple Generators 0418 0419 >>> class disjointSet: 0420 ... def __init__(self, name): 0421 ... self.name = name 0422 ... self.parent = None 0423 ... self.generator = self.generate() 0424 ... 0425 ... def generate(self): 0426 ... while not self.parent: 0427 ... yield self 0428 ... for x in self.parent.generator: 0429 ... yield x 0430 ... 0431 ... def find(self): 0432 ... return self.generator.next() 0433 ... 0434 ... def union(self, parent): 0435 ... if self.parent: 0436 ... raise ValueError("Sorry, I'm not a root!") 0437 ... self.parent = parent 0438 ... 0439 ... def __str__(self): 0440 ... return self.name 0441 0442 >>> names = "ABCDEFGHIJKLM" 0443 >>> sets = [disjointSet(name) for name in names] 0444 >>> roots = sets[:] 0445 0446 >>> import random 0447 >>> gen = random.WichmannHill(42) 0448 >>> while 1: 0449 ... for s in sets: 0450 ... print "%s->%s" % (s, s.find()), 0451 ... print 0452 ... if len(roots) > 1: 0453 ... s1 = gen.choice(roots) 0454 ... roots.remove(s1) 0455 ... s2 = gen.choice(roots) 0456 ... s1.union(s2) 0457 ... print "merged", s1, "into", s2 0458 ... else: 0459 ... break 0460 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 0461 merged D into G 0462 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 0463 merged C into F 0464 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 0465 merged L into A 0466 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 0467 merged H into E 0468 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 0469 merged B into E 0470 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 0471 merged J into G 0472 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 0473 merged E into G 0474 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 0475 merged M into G 0476 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 0477 merged I into K 0478 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 0479 merged K into A 0480 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 0481 merged F into A 0482 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 0483 merged A into G 0484 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 0485 """ 0486 # Emacs turd ' 0487 0488 # Fun tests (for sufficiently warped notions of "fun"). 0489 0490 fun_tests = """ 0491 0492 Build up to a recursive Sieve of Eratosthenes generator. 0493 0494 >>> def firstn(g, n): 0495 ... return [g.next() for i in range(n)] 0496 0497 >>> def intsfrom(i): 0498 ... while 1: 0499 ... yield i 0500 ... i += 1 0501 0502 >>> firstn(intsfrom(5), 7) 0503 [5, 6, 7, 8, 9, 10, 11] 0504 0505 >>> def exclude_multiples(n, ints): 0506 ... for i in ints: 0507 ... if i % n: 0508 ... yield i 0509 0510 >>> firstn(exclude_multiples(3, intsfrom(1)), 6) 0511 [1, 2, 4, 5, 7, 8] 0512 0513 >>> def sieve(ints): 0514 ... prime = ints.next() 0515 ... yield prime 0516 ... not_divisible_by_prime = exclude_multiples(prime, ints) 0517 ... for p in sieve(not_divisible_by_prime): 0518 ... yield p 0519 0520 >>> primes = sieve(intsfrom(2)) 0521 >>> firstn(primes, 20) 0522 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71] 0523 0524 0525 Another famous problem: generate all integers of the form 0526 2**i * 3**j * 5**k 0527 in increasing order, where i,j,k >= 0. Trickier than it may look at first! 0528 Try writing it without generators, and correctly, and without generating 0529 3 internal results for each result output. 0530 0531 >>> def times(n, g): 0532 ... for i in g: 0533 ... yield n * i 0534 >>> firstn(times(10, intsfrom(1)), 10) 0535 [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] 0536 0537 >>> def merge(g, h): 0538 ... ng = g.next() 0539 ... nh = h.next() 0540 ... while 1: 0541 ... if ng < nh: 0542 ... yield ng 0543 ... ng = g.next() 0544 ... elif ng > nh: 0545 ... yield nh 0546 ... nh = h.next() 0547 ... else: 0548 ... yield ng 0549 ... ng = g.next() 0550 ... nh = h.next() 0551 0552 The following works, but is doing a whale of a lot of redundant work -- 0553 it's not clear how to get the internal uses of m235 to share a single 0554 generator. Note that me_times2 (etc) each need to see every element in the 0555 result sequence. So this is an example where lazy lists are more natural 0556 (you can look at the head of a lazy list any number of times). 0557 0558 >>> def m235(): 0559 ... yield 1 0560 ... me_times2 = times(2, m235()) 0561 ... me_times3 = times(3, m235()) 0562 ... me_times5 = times(5, m235()) 0563 ... for i in merge(merge(me_times2, 0564 ... me_times3), 0565 ... me_times5): 0566 ... yield i 0567 0568 Don't print "too many" of these -- the implementation above is extremely 0569 inefficient: each call of m235() leads to 3 recursive calls, and in 0570 turn each of those 3 more, and so on, and so on, until we've descended 0571 enough levels to satisfy the print stmts. Very odd: when I printed 5 0572 lines of results below, this managed to screw up Win98's malloc in "the 0573 usual" way, i.e. the heap grew over 4Mb so Win98 started fragmenting 0574 address space, and it *looked* like a very slow leak. 0575 0576 >>> result = m235() 0577 >>> for i in range(3): 0578 ... print firstn(result, 15) 0579 [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24] 0580 [25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80] 0581 [81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192] 0582 0583 Heh. Here's one way to get a shared list, complete with an excruciating 0584 namespace renaming trick. The *pretty* part is that the times() and merge() 0585 functions can be reused as-is, because they only assume their stream 0586 arguments are iterable -- a LazyList is the same as a generator to times(). 0587 0588 >>> class LazyList: 0589 ... def __init__(self, g): 0590 ... self.sofar = [] 0591 ... self.fetch = g.next 0592 ... 0593 ... def __getitem__(self, i): 0594 ... sofar, fetch = self.sofar, self.fetch 0595 ... while i >= len(sofar): 0596 ... sofar.append(fetch()) 0597 ... return sofar[i] 0598 0599 >>> def m235(): 0600 ... yield 1 0601 ... # Gack: m235 below actually refers to a LazyList. 0602 ... me_times2 = times(2, m235) 0603 ... me_times3 = times(3, m235) 0604 ... me_times5 = times(5, m235) 0605 ... for i in merge(merge(me_times2, 0606 ... me_times3), 0607 ... me_times5): 0608 ... yield i 0609 0610 Print as many of these as you like -- *this* implementation is memory- 0611 efficient. 0612 0613 >>> m235 = LazyList(m235()) 0614 >>> for i in range(5): 0615 ... print [m235[j] for j in range(15*i, 15*(i+1))] 0616 [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24] 0617 [25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80] 0618 [81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192] 0619 [200, 216, 225, 240, 243, 250, 256, 270, 288, 300, 320, 324, 360, 375, 384] 0620 [400, 405, 432, 450, 480, 486, 500, 512, 540, 576, 600, 625, 640, 648, 675] 0621 0622 0623 Ye olde Fibonacci generator, LazyList style. 0624 0625 >>> def fibgen(a, b): 0626 ... 0627 ... def sum(g, h): 0628 ... while 1: 0629 ... yield g.next() + h.next() 0630 ... 0631 ... def tail(g): 0632 ... g.next() # throw first away 0633 ... for x in g: 0634 ... yield x 0635 ... 0636 ... yield a 0637 ... yield b 0638 ... for s in sum(iter(fib), 0639 ... tail(iter(fib))): 0640 ... yield s 0641 0642 >>> fib = LazyList(fibgen(1, 2)) 0643 >>> firstn(iter(fib), 17) 0644 [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584] 0645 """ 0646 0647 # syntax_tests mostly provokes SyntaxErrors. Also fiddling with #if 0 0648 # hackery. 0649 0650 syntax_tests = """ 0651 0652 >>> def f(): 0653 ... return 22 0654 ... yield 1 0655 Traceback (most recent call last): 0656 .. 0657 SyntaxError: 'return' with argument inside generator (<doctest test.test_generators.__test__.syntax[0]>, line 2) 0658 0659 >>> def f(): 0660 ... yield 1 0661 ... return 22 0662 Traceback (most recent call last): 0663 .. 0664 SyntaxError: 'return' with argument inside generator (<doctest test.test_generators.__test__.syntax[1]>, line 3) 0665 0666 "return None" is not the same as "return" in a generator: 0667 0668 >>> def f(): 0669 ... yield 1 0670 ... return None 0671 Traceback (most recent call last): 0672 .. 0673 SyntaxError: 'return' with argument inside generator (<doctest test.test_generators.__test__.syntax[2]>, line 3) 0674 0675 This one is fine: 0676 0677 >>> def f(): 0678 ... yield 1 0679 ... return 0680 0681 >>> def f(): 0682 ... try: 0683 ... yield 1 0684 ... finally: 0685 ... pass 0686 Traceback (most recent call last): 0687 .. 0688 SyntaxError: 'yield' not allowed in a 'try' block with a 'finally' clause (<doctest test.test_generators.__test__.syntax[4]>, line 3) 0689 0690 >>> def f(): 0691 ... try: 0692 ... try: 0693 ... 1//0 0694 ... except ZeroDivisionError: 0695 ... yield 666 # bad because *outer* try has finally 0696 ... except: 0697 ... pass 0698 ... finally: 0699 ... pass 0700 Traceback (most recent call last): 0701 ... 0702 SyntaxError: 'yield' not allowed in a 'try' block with a 'finally' clause (<doctest test.test_generators.__test__.syntax[5]>, line 6) 0703 0704 But this is fine: 0705 0706 >>> def f(): 0707 ... try: 0708 ... try: 0709 ... yield 12 0710 ... 1//0 0711 ... except ZeroDivisionError: 0712 ... yield 666 0713 ... except: 0714 ... try: 0715 ... x = 12 0716 ... finally: 0717 ... yield 12 0718 ... except: 0719 ... return 0720 >>> list(f()) 0721 [12, 666] 0722 0723 >>> def f(): 0724 ... yield 0725 Traceback (most recent call last): 0726 SyntaxError: invalid syntax 0727 0728 >>> def f(): 0729 ... if 0: 0730 ... yield 0731 Traceback (most recent call last): 0732 SyntaxError: invalid syntax 0733 0734 >>> def f(): 0735 ... if 0: 0736 ... yield 1 0737 >>> type(f()) 0738 <type 'generator'> 0739 0740 >>> def f(): 0741 ... if "": 0742 ... yield None 0743 >>> type(f()) 0744 <type 'generator'> 0745 0746 >>> def f(): 0747 ... return 0748 ... try: 0749 ... if x==4: 0750 ... pass 0751 ... elif 0: 0752 ... try: 0753 ... 1//0 0754 ... except SyntaxError: 0755 ... pass 0756 ... else: 0757 ... if 0: 0758 ... while 12: 0759 ... x += 1 0760 ... yield 2 # don't blink 0761 ... f(a, b, c, d, e) 0762 ... else: 0763 ... pass 0764 ... except: 0765 ... x = 1 0766 ... return 0767 >>> type(f()) 0768 <type 'generator'> 0769 0770 >>> def f(): 0771 ... if 0: 0772 ... def g(): 0773 ... yield 1 0774 ... 0775 >>> type(f()) 0776 <type 'NoneType'> 0777 0778 >>> def f(): 0779 ... if 0: 0780 ... class C: 0781 ... def __init__(self): 0782 ... yield 1 0783 ... def f(self): 0784 ... yield 2 0785 >>> type(f()) 0786 <type 'NoneType'> 0787 0788 >>> def f(): 0789 ... if 0: 0790 ... return 0791 ... if 0: 0792 ... yield 2 0793 >>> type(f()) 0794 <type 'generator'> 0795 0796 0797 >>> def f(): 0798 ... if 0: 0799 ... lambda x: x # shouldn't trigger here 0800 ... return # or here 0801 ... def f(i): 0802 ... return 2*i # or here 0803 ... if 0: 0804 ... return 3 # but *this* sucks (line 8) 0805 ... if 0: 0806 ... yield 2 # because it's a generator 0807 Traceback (most recent call last): 0808 SyntaxError: 'return' with argument inside generator (<doctest test.test_generators.__test__.syntax[22]>, line 8) 0809 0810 This one caused a crash (see SF bug 567538): 0811 0812 >>> def f(): 0813 ... for i in range(3): 0814 ... try: 0815 ... continue 0816 ... finally: 0817 ... yield i 0818 ... 0819 >>> g = f() 0820 >>> print g.next() 0821 0 0822 >>> print g.next() 0823 1 0824 >>> print g.next() 0825 2 0826 >>> print g.next() 0827 Traceback (most recent call last): 0828 StopIteration 0829 """ 0830 0831 # conjoin is a simple backtracking generator, named in honor of Icon's 0832 # "conjunction" control structure. Pass a list of no-argument functions 0833 # that return iterable objects. Easiest to explain by example: assume the 0834 # function list [x, y, z] is passed. Then conjoin acts like: 0835 # 0836 # def g(): 0837 # values = [None] * 3 0838 # for values[0] in x(): 0839 # for values[1] in y(): 0840 # for values[2] in z(): 0841 # yield values 0842 # 0843 # So some 3-lists of values *may* be generated, each time we successfully 0844 # get into the innermost loop. If an iterator fails (is exhausted) before 0845 # then, it "backtracks" to get the next value from the nearest enclosing 0846 # iterator (the one "to the left"), and starts all over again at the next 0847 # slot (pumps a fresh iterator). Of course this is most useful when the 0848 # iterators have side-effects, so that which values *can* be generated at 0849 # each slot depend on the values iterated at previous slots. 0850 0851 def conjoin(gs): 0852 0853 values = [None] * len(gs) 0854 0855 def gen(i, values=values): 0856 if i >= len(gs): 0857 yield values 0858 else: 0859 for values[i] in gs[i](): 0860 for x in gen(i+1): 0861 yield x 0862 0863 for x in gen(0): 0864 yield x 0865 0866 # That works fine, but recursing a level and checking i against len(gs) for 0867 # each item produced is inefficient. By doing manual loop unrolling across 0868 # generator boundaries, it's possible to eliminate most of that overhead. 0869 # This isn't worth the bother *in general* for generators, but conjoin() is 0870 # a core building block for some CPU-intensive generator applications. 0871 0872 def conjoin(gs): 0873 0874 n = len(gs) 0875 values = [None] * n 0876 0877 # Do one loop nest at time recursively, until the # of loop nests 0878 # remaining is divisible by 3. 0879 0880 def gen(i, values=values): 0881 if i >= n: 0882 yield values 0883 0884 elif (n-i) % 3: 0885 ip1 = i+1 0886 for values[i] in gs[i](): 0887 for x in gen(ip1): 0888 yield x 0889 0890 else: 0891 for x in _gen3(i): 0892 yield x 0893 0894 # Do three loop nests at a time, recursing only if at least three more 0895 # remain. Don't call directly: this is an internal optimization for 0896 # gen's use. 0897 0898 def _gen3(i, values=values): 0899 assert i < n and (n-i) % 3 == 0 0900 ip1, ip2, ip3 = i+1, i+2, i+3 0901 g, g1, g2 = gs[i : ip3] 0902 0903 if ip3 >= n: 0904 # These are the last three, so we can yield values directly. 0905 for values[i] in g(): 0906 for values[ip1] in g1(): 0907 for values[ip2] in g2(): 0908 yield values 0909 0910 else: 0911 # At least 6 loop nests remain; peel off 3 and recurse for the 0912 # rest. 0913 for values[i] in g(): 0914 for values[ip1] in g1(): 0915 for values[ip2] in g2(): 0916 for x in _gen3(ip3): 0917 yield x 0918 0919 for x in gen(0): 0920 yield x 0921 0922 # And one more approach: For backtracking apps like the Knight's Tour 0923 # solver below, the number of backtracking levels can be enormous (one 0924 # level per square, for the Knight's Tour, so that e.g. a 100x100 board 0925 # needs 10,000 levels). In such cases Python is likely to run out of 0926 # stack space due to recursion. So here's a recursion-free version of 0927 # conjoin too. 0928 # NOTE WELL: This allows large problems to be solved with only trivial 0929 # demands on stack space. Without explicitly resumable generators, this is 0930 # much harder to achieve. OTOH, this is much slower (up to a factor of 2) 0931 # than the fancy unrolled recursive conjoin. 0932 0933 def flat_conjoin(gs): # rename to conjoin to run tests with this instead 0934 n = len(gs) 0935 values = [None] * n 0936 iters = [None] * n 0937 _StopIteration = StopIteration # make local because caught a *lot* 0938 i = 0 0939 while 1: 0940 # Descend. 0941 try: 0942 while i < n: 0943 it = iters[i] = gs[i]().next 0944 values[i] = it() 0945 i += 1 0946 except _StopIteration: 0947 pass 0948 else: 0949 assert i == n 0950 yield values 0951 0952 # Backtrack until an older iterator can be resumed. 0953 i -= 1 0954 while i >= 0: 0955 try: 0956 values[i] = iters[i]() 0957 # Success! Start fresh at next level. 0958 i += 1 0959 break 0960 except _StopIteration: 0961 # Continue backtracking. 0962 i -= 1 0963 else: 0964 assert i < 0 0965 break 0966 0967 # A conjoin-based N-Queens solver. 0968 0969 class Queens: 0970 def __init__(self, n): 0971 self.n = n 0972 rangen = range(n) 0973 0974 # Assign a unique int to each column and diagonal. 0975 # columns: n of those, range(n). 0976 # NW-SE diagonals: 2n-1 of these, i-j unique and invariant along 0977 # each, smallest i-j is 0-(n-1) = 1-n, so add n-1 to shift to 0- 0978 # based. 0979 # NE-SW diagonals: 2n-1 of these, i+j unique and invariant along 0980 # each, smallest i+j is 0, largest is 2n-2. 0981 0982 # For each square, compute a bit vector of the columns and 0983 # diagonals it covers, and for each row compute a function that 0984 # generates the possiblities for the columns in that row. 0985 self.rowgenerators = [] 0986 for i in rangen: 0987 rowuses = [(1L << j) | # column ordinal 0988 (1L << (n + i-j + n-1)) | # NW-SE ordinal 0989 (1L << (n + 2*n-1 + i+j)) # NE-SW ordinal 0990 for j in rangen] 0991 0992 def rowgen(rowuses=rowuses): 0993 for j in rangen: 0994 uses = rowuses[j] 0995 if uses & self.used == 0: 0996 self.used |= uses 0997 yield j 0998 self.used &= ~uses 0999 1000 self.rowgenerators.append(rowgen) 1001 1002 # Generate solutions. 1003 def solve(self): 1004 self.used = 0 1005 for row2col in conjoin(self.rowgenerators): 1006 yield row2col 1007 1008 def printsolution(self, row2col): 1009 n = self.n 1010 assert n == len(row2col) 1011 sep = "+" + "-+" * n 1012 print sep 1013 for i in range(n): 1014 squares = [" " for j in range(n)] 1015 squares[row2col[i]] = "Q" 1016 print "|" + "|".join(squares) + "|" 1017 print sep 1018 1019 # A conjoin-based Knight's Tour solver. This is pretty sophisticated 1020 # (e.g., when used with flat_conjoin above, and passing hard=1 to the 1021 # constructor, a 200x200 Knight's Tour was found quickly -- note that we're 1022 # creating 10s of thousands of generators then!), and is lengthy. 1023 1024 class Knights: 1025 def __init__(self, m, n, hard=0): 1026 self.m, self.n = m, n 1027 1028 # solve() will set up succs[i] to be a list of square #i's 1029 # successors. 1030 succs = self.succs = [] 1031 1032 # Remove i0 from each of its successor's successor lists, i.e. 1033 # successors can't go back to i0 again. Return 0 if we can 1034 # detect this makes a solution impossible, else return 1. 1035 1036 def remove_from_successors(i0, len=len): 1037 # If we remove all exits from a free square, we're dead: 1038 # even if we move to it next, we can't leave it again. 1039 # If we create a square with one exit, we must visit it next; 1040 # else somebody else will have to visit it, and since there's 1041 # only one adjacent, there won't be a way to leave it again. 1042 # Finelly, if we create more than one free square with a 1043 # single exit, we can only move to one of them next, leaving 1044 # the other one a dead end. 1045 ne0 = ne1 = 0 1046 for i in succs[i0]: 1047 s = succs[i] 1048 s.remove(i0) 1049 e = len(s) 1050 if e == 0: 1051 ne0 += 1 1052 elif e == 1: 1053 ne1 += 1 1054 return ne0 == 0 and ne1 < 2 1055 1056 # Put i0 back in each of its successor's successor lists. 1057 1058 def add_to_successors(i0): 1059 for i in succs[i0]: 1060 succs[i].append(i0) 1061 1062 # Generate the first move. 1063 def first(): 1064 if m < 1 or n < 1: 1065 return 1066 1067 # Since we're looking for a cycle, it doesn't matter where we 1068 # start. Starting in a corner makes the 2nd move easy. 1069 corner = self.coords2index(0, 0) 1070 remove_from_successors(corner) 1071 self.lastij = corner 1072 yield corner 1073 add_to_successors(corner) 1074 1075 # Generate the second moves. 1076 def second(): 1077 corner = self.coords2index(0, 0) 1078 assert self.lastij == corner # i.e., we started in the corner 1079 if m < 3 or n < 3: 1080 return 1081 assert len(succs[corner]) == 2 1082 assert self.coords2index(1, 2) in succs[corner] 1083 assert self.coords2index(2, 1) in succs[corner] 1084 # Only two choices. Whichever we pick, the other must be the 1085 # square picked on move m*n, as it's the only way to get back 1086 # to (0, 0). Save its index in self.final so that moves before 1087 # the last know it must be kept free. 1088 for i, j in (1, 2), (2, 1): 1089 this = self.coords2index(i, j) 1090 final = self.coords2index(3-i, 3-j) 1091 self.final = final 1092 1093 remove_from_successors(this) 1094 succs[final].append(corner) 1095 self.lastij = this 1096 yield this 1097 succs[final].remove(corner) 1098 add_to_successors(this) 1099 1100 # Generate moves 3 thru m*n-1. 1101 def advance(len=len): 1102 # If some successor has only one exit, must take it. 1103 # Else favor successors with fewer exits. 1104 candidates = [] 1105 for i in succs[self.lastij]: 1106 e = len(succs[i]) 1107 assert e > 0, "else remove_from_successors() pruning flawed" 1108 if e == 1: 1109 candidates = [(e, i)] 1110 break 1111 candidates.append((e, i)) 1112 else: 1113 candidates.sort() 1114 1115 for e, i in candidates: 1116 if i != self.final: 1117 if remove_from_successors(i): 1118 self.lastij = i 1119 yield i 1120 add_to_successors(i) 1121 1122 # Generate moves 3 thru m*n-1. Alternative version using a 1123 # stronger (but more expensive) heuristic to order successors. 1124 # Since the # of backtracking levels is m*n, a poor move early on 1125 # can take eons to undo. Smallest square board for which this 1126 # matters a lot is 52x52. 1127 def advance_hard(vmid=(m-1)/2.0, hmid=(n-1)/2.0, len=len): 1128 # If some successor has only one exit, must take it. 1129 # Else favor successors with fewer exits. 1130 # Break ties via max distance from board centerpoint (favor 1131 # corners and edges whenever possible). 1132 candidates = [] 1133 for i in succs[self.lastij]: 1134 e = len(succs[i]) 1135 assert e > 0, "else remove_from_successors() pruning flawed" 1136 if e == 1: 1137 candidates = [(e, 0, i)] 1138 break 1139 i1, j1 = self.index2coords(i) 1140 d = (i1 - vmid)**2 + (j1 - hmid)**2 1141 candidates.append((e, -d, i)) 1142 else: 1143 candidates.sort() 1144 1145 for e, d, i in candidates: 1146 if i != self.final: 1147 if remove_from_successors(i): 1148 self.lastij = i 1149 yield i 1150 add_to_successors(i) 1151 1152 # Generate the last move. 1153 def last(): 1154 assert self.final in succs[self.lastij] 1155 yield self.final 1156 1157 if m*n < 4: 1158 self.squaregenerators = [first] 1159 else: 1160 self.squaregenerators = [first, second] + \ 1161 [hard and advance_hard or advance] * (m*n - 3) + \ 1162 [last] 1163 1164 def coords2index(self, i, j): 1165 assert 0 <= i < self.m 1166 assert 0 <= j < self.n 1167 return i * self.n + j 1168 1169 def index2coords(self, index): 1170 assert 0 <= index < self.m * self.n 1171 return divmod(index, self.n) 1172 1173 def _init_board(self): 1174 succs = self.succs 1175 del succs[:] 1176 m, n = self.m, self.n 1177 c2i = self.coords2index 1178 1179 offsets = [( 1, 2), ( 2, 1), ( 2, -1), ( 1, -2), 1180 (-1, -2), (-2, -1), (-2, 1), (-1, 2)] 1181 rangen = range(n) 1182 for i in range(m): 1183 for j in rangen: 1184 s = [c2i(i+io, j+jo) for io, jo in offsets 1185 if 0 <= i+io < m and 1186 0 <= j+jo < n] 1187 succs.append(s) 1188 1189 # Generate solutions. 1190 def solve(self): 1191 self._init_board() 1192 for x in conjoin(self.squaregenerators): 1193 yield x 1194 1195 def printsolution(self, x): 1196 m, n = self.m, self.n 1197 assert len(x) == m*n 1198 w = len(str(m*n)) 1199 format = "%" + str(w) + "d" 1200 1201 squares = [[None] * n for i in range(m)] 1202 k = 1 1203 for i in x: 1204 i1, j1 = self.index2coords(i) 1205 squares[i1][j1] = format % k 1206 k += 1 1207 1208 sep = "+" + ("-" * w + "+") * n 1209 print sep 1210 for i in range(m): 1211 row = squares[i] 1212 print "|" + "|".join(row) + "|" 1213 print sep 1214 1215 conjoin_tests = """ 1216 1217 Generate the 3-bit binary numbers in order. This illustrates dumbest- 1218 possible use of conjoin, just to generate the full cross-product. 1219 1220 >>> for c in conjoin([lambda: iter((0, 1))] * 3): 1221 ... print c 1222 [0, 0, 0] 1223 [0, 0, 1] 1224 [0, 1, 0] 1225 [0, 1, 1] 1226 [1, 0, 0] 1227 [1, 0, 1] 1228 [1, 1, 0] 1229 [1, 1, 1] 1230 1231 For efficiency in typical backtracking apps, conjoin() yields the same list 1232 object each time. So if you want to save away a full account of its 1233 generated sequence, you need to copy its results. 1234 1235 >>> def gencopy(iterator): 1236 ... for x in iterator: 1237 ... yield x[:] 1238 1239 >>> for n in range(10): 1240 ... all = list(gencopy(conjoin([lambda: iter((0, 1))] * n))) 1241 ... print n, len(all), all[0] == [0] * n, all[-1] == [1] * n 1242 0 1 True True 1243 1 2 True True 1244 2 4 True True 1245 3 8 True True 1246 4 16 True True 1247 5 32 True True 1248 6 64 True True 1249 7 128 True True 1250 8 256 True True 1251 9 512 True True 1252 1253 And run an 8-queens solver. 1254 1255 >>> q = Queens(8) 1256 >>> LIMIT = 2 1257 >>> count = 0 1258 >>> for row2col in q.solve(): 1259 ... count += 1 1260 ... if count <= LIMIT: 1261 ... print "Solution", count 1262 ... q.printsolution(row2col) 1263 Solution 1 1264 +-+-+-+-+-+-+-+-+ 1265 |Q| | | | | | | | 1266 +-+-+-+-+-+-+-+-+ 1267 | | | | |Q| | | | 1268 +-+-+-+-+-+-+-+-+ 1269 | | | | | | | |Q| 1270 +-+-+-+-+-+-+-+-+ 1271 | | | | | |Q| | | 1272 +-+-+-+-+-+-+-+-+ 1273 | | |Q| | | | | | 1274 +-+-+-+-+-+-+-+-+ 1275 | | | | | | |Q| | 1276 +-+-+-+-+-+-+-+-+ 1277 | |Q| | | | | | | 1278 +-+-+-+-+-+-+-+-+ 1279 | | | |Q| | | | | 1280 +-+-+-+-+-+-+-+-+ 1281 Solution 2 1282 +-+-+-+-+-+-+-+-+ 1283 |Q| | | | | | | | 1284 +-+-+-+-+-+-+-+-+ 1285 | | | | | |Q| | | 1286 +-+-+-+-+-+-+-+-+ 1287 | | | | | | | |Q| 1288 +-+-+-+-+-+-+-+-+ 1289 | | |Q| | | | | | 1290 +-+-+-+-+-+-+-+-+ 1291 | | | | | | |Q| | 1292 +-+-+-+-+-+-+-+-+ 1293 | | | |Q| | | | | 1294 +-+-+-+-+-+-+-+-+ 1295 | |Q| | | | | | | 1296 +-+-+-+-+-+-+-+-+ 1297 | | | | |Q| | | | 1298 +-+-+-+-+-+-+-+-+ 1299 1300 >>> print count, "solutions in all." 1301 92 solutions in all. 1302 1303 And run a Knight's Tour on a 10x10 board. Note that there are about 1304 20,000 solutions even on a 6x6 board, so don't dare run this to exhaustion. 1305 1306 >>> k = Knights(10, 10) 1307 >>> LIMIT = 2 1308 >>> count = 0 1309 >>> for x in k.solve(): 1310 ... count += 1 1311 ... if count <= LIMIT: 1312 ... print "Solution", count 1313 ... k.printsolution(x) 1314 ... else: 1315 ... break 1316 Solution 1 1317 +---+---+---+---+---+---+---+---+---+---+ 1318 | 1| 58| 27| 34| 3| 40| 29| 10| 5| 8| 1319 +---+---+---+---+---+---+---+---+---+---+ 1320 | 26| 35| 2| 57| 28| 33| 4| 7| 30| 11| 1321 +---+---+---+---+---+---+---+---+---+---+ 1322 | 59|100| 73| 36| 41| 56| 39| 32| 9| 6| 1323 +---+---+---+---+---+---+---+---+---+---+ 1324 | 74| 25| 60| 55| 72| 37| 42| 49| 12| 31| 1325 +---+---+---+---+---+---+---+---+---+---+ 1326 | 61| 86| 99| 76| 63| 52| 47| 38| 43| 50| 1327 +---+---+---+---+---+---+---+---+---+---+ 1328 | 24| 75| 62| 85| 54| 71| 64| 51| 48| 13| 1329 +---+---+---+---+---+---+---+---+---+---+ 1330 | 87| 98| 91| 80| 77| 84| 53| 46| 65| 44| 1331 +---+---+---+---+---+---+---+---+---+---+ 1332 | 90| 23| 88| 95| 70| 79| 68| 83| 14| 17| 1333 +---+---+---+---+---+---+---+---+---+---+ 1334 | 97| 92| 21| 78| 81| 94| 19| 16| 45| 66| 1335 +---+---+---+---+---+---+---+---+---+---+ 1336 | 22| 89| 96| 93| 20| 69| 82| 67| 18| 15| 1337 +---+---+---+---+---+---+---+---+---+---+ 1338 Solution 2 1339 +---+---+---+---+---+---+---+---+---+---+ 1340 | 1| 58| 27| 34| 3| 40| 29| 10| 5| 8| 1341 +---+---+---+---+---+---+---+---+---+---+ 1342 | 26| 35| 2| 57| 28| 33| 4| 7| 30| 11| 1343 +---+---+---+---+---+---+---+---+---+---+ 1344 | 59|100| 73| 36| 41| 56| 39| 32| 9| 6| 1345 +---+---+---+---+---+---+---+---+---+---+ 1346 | 74| 25| 60| 55| 72| 37| 42| 49| 12| 31| 1347 +---+---+---+---+---+---+---+---+---+---+ 1348 | 61| 86| 99| 76| 63| 52| 47| 38| 43| 50| 1349 +---+---+---+---+---+---+---+---+---+---+ 1350 | 24| 75| 62| 85| 54| 71| 64| 51| 48| 13| 1351 +---+---+---+---+---+---+---+---+---+---+ 1352 | 87| 98| 89| 80| 77| 84| 53| 46| 65| 44| 1353 +---+---+---+---+---+---+---+---+---+---+ 1354 | 90| 23| 92| 95| 70| 79| 68| 83| 14| 17| 1355 +---+---+---+---+---+---+---+---+---+---+ 1356 | 97| 88| 21| 78| 81| 94| 19| 16| 45| 66| 1357 +---+---+---+---+---+---+---+---+---+---+ 1358 | 22| 91| 96| 93| 20| 69| 82| 67| 18| 15| 1359 +---+---+---+---+---+---+---+---+---+---+ 1360 """ 1361 1362 weakref_tests = """\ 1363 Generators are weakly referencable: 1364 1365 >>> import weakref 1366 >>> def gen(): 1367 ... yield 'foo!' 1368 ... 1369 >>> wr = weakref.ref(gen) 1370 >>> wr() is gen 1371 True 1372 >>> p = weakref.proxy(gen) 1373 1374 Generator-iterators are weakly referencable as well: 1375 1376 >>> gi = gen() 1377 >>> wr = weakref.ref(gi) 1378 >>> wr() is gi 1379 True 1380 >>> p = weakref.proxy(gi) 1381 >>> list(p) 1382 ['foo!'] 1383 1384 """ 1385 1386 __test__ = {"tut": tutorial_tests, 1387 "pep": pep_tests, 1388 "email": email_tests, 1389 "fun": fun_tests, 1390 "syntax": syntax_tests, 1391 "conjoin": conjoin_tests, 1392 "weakref": weakref_tests, 1393 } 1394 1395 # Magic test name that regrtest.py invokes *after* importing this module. 1396 # This worms around a bootstrap problem. 1397 # Note that doctest and regrtest both look in sys.argv for a "-v" argument, 1398 # so this works as expected in both ways of running regrtest. 1399 def test_main(verbose=None): 1400 from test import test_support, test_generators 1401 test_support.run_doctest(test_generators, verbose) 1402 1403 # This part isn't needed for regrtest, but for running the test directly. 1404 if __name__ == "__main__": 1405 test_main(1) 1406
Generated by PyXR 0.9.4