Some useful functions which work on infinite lists, including generalized versions of map, filter, zip on gLists.
Python, 126 lines
Download
Copy to clipboard1 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.
Tags: algorithms
