Infinite lists and generators
Terry Reedy
tjreedy at home.com
Wed Nov 14 17:32:28 CET 2001
"Luigi Ballabio" <ballabio at mac.com> wrote in message
news:mailman.1005728119.32612.python-list at python.org...
>
> Hi all,
> I've been reading a few back issues of the Perl Journal, and I came
across
> an article on implementing infinite lists in Perl. Just for fun I
went
> ahead and reimplemented it in Python---I know someone probably did
already,
> but as I said, it was for fun. Also, I've written a test suite which
> showcases a few tricks such as building the list of all prime
numbers, of
> the Hamming numbers, and the power series of exp, sin and cos. I'm
> including the file below.
>
> My question is: how does one go about pulling such stunts with
generators
> instead?
Two easy examples (untested, but pretty sure correct):
def integersFrom(n):
"Infinite stream of integers starting from n"
> return Stream(n,lambda n=n:integersFrom(n+1))
while 1:
yield n
n += 1
>def filter(f,s):
> """returns the stream of the elements x of the
> input stream s which satisfy the predicate f"""
> while s and not f(s.head()):
> s = s.tail()
> if not s:
> return None
> else:
> return Stream(s.head(),
> lambda f=f,s=s: filter(f,s.tail()))
The problem with filtering an infinite stream is that if there are
only N items that pass, the filter will never halt looking for the
N+1st.
def iterate(f,x):
"returns the stream of x, f(x), f(f(x)), f(f(f(x))), ..."
> return Stream(x,
> lambda f=f,x=x: iterate(f,f(x)))
while 1:
yield x
x = f(x)
Terry J. Reedy
More information about the Python-list
mailing list