Welcome, guest | Sign In | My Account | Store | Cart

Some useful functions which work on infinite lists, including generalized versions of map, filter, zip on gLists.

Python, 126 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126``` ```"""Collection of useful functions which work on infinite lists. The infinite lists are actually the generator objects. Note that the functions will have side effects on the passed-in gLists. """ from __future__ import generators def gInfinite(obj): """Return infinite list of repeated objects obj""" while 1: yield obj gNone = gInfinite(None) def gJoin(gl1, gl2): """Return gl1+gl2, i.e [gl1[0],...,gl1[n],gl2[0],...] Apparently only useful when gl1 is finite. """ for x in gl1: yield x for x in gl2: yield x def gCon(x, xs): """Return [x, xs[0], xs[1], ...]""" yield x xs = iter(xs) # make sure it also works for ordinary list while 1: yield xs.next() def gRange(start=0,step=1,stop=None): """Generalized version of range() - could be infinite Note the difference in the order of arguments from those of range(). """ if stop is None: x = int(start) step = int(step) while 1: yield x x += step else: for x in range(start, stop, step): yield x def gMap(f, *gLists): """Generalized version of map() - work on infinite list Work differently from map(), stops when the end of the shortest gList is reached. """ if f is None: f = lambda *x: x gLists = map(iter, gLists) # make sure it also works for ordinary list while 1: yield f(*[gl.next() for gl in gLists]) def gZip(*gLists): """Generalized version of zip() - work on infinite list""" for x in gMap(None, *gLists): yield x def gFilter(f, gList): """Generalized version of filter() - work on infinite list""" if f is None: f = lambda x: x for x in gList: # WARNING: may fall into forever loop # without yielding anything if f(x) is # always false from a certain x onwards if f(x): yield x def gCompre(f, gList, cond = lambda *x: 1): """List Comprehension [f(*x) for x in gList if cond(*x)] """ for x in gList: # WARNING: may fall into forever loop # without yielding anything if f(*x) is # always false from a certain x onwards if cond(*x): yield f(*x) def pList(gList, limit=20): """Return partial ordinary list of gList.""" if type(gList) is type(gNone): return [pList(x[0]) for x in zip(gList, range(limit))] else: return gList if __name__=='__main__': print pList(gMap(lambda x,y,z: x+y+z, gRange(1), gRange(2,2), gRange(3,3))) # -> [1+2+3, 2+4+6, 3+6+9, ...] def f(x,y): return '%s%i' % (x,y) def g(x,y): return y%3==0 print pList(gCompre(f, gZip(gInfinite('A'), gRange(2)), g)) # or pList(gCompre(lambda x,y: '%s%i' % (x,y), gZip(gInfinite('A'), gRange(2)), lambda x,y: y%3==0)) # -> ['A3', 'A6', 'A9', ...] def sieve(gList): """Sieve of Eratosthene""" x = gList.next() xs = sieve(gFilter(lambda y: y % x != 0, gList)) for y in gCon(x, xs): yield y import sys sys.setrecursionlimit(sys.maxint) # needed for bigger lists of primes primes = sieve(gRange(2)) # infinite list of primes print pList(primes, 100) # print the first 100 primes print pList(primes, 500) # print subsequent 500 primes # gList of gLists print pList(gMap(gRange, gRange())) ```

Sometimes thinking in infinite lists is immensely useful. Generators come to mind when I want to implement infinite lists. Here gList(generalized list? generated list?) is actually a generator by itself. Apparently we want to set our mindset in thinking infinite lists rather than worrying about the underlying implementation. The natural thing to do is to extend functions like map, filter, zip to gList, so that we can manipulate gLists easily. One can easily wrap up all these functions nicely in a class so that we can even implement index, slicing, or concatenating operators etc.

 Created by Chong Hooi Min on Wed, 25 Dec 2002 (PSF)