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