# Infinite lists and generators

Steven D. Majewski sdm7g at Virginia.EDU
Wed Nov 14 17:55:23 CET 2001

```On Wed, 14 Nov 2001, Terry Reedy wrote:

> 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:
> >                        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.

You just do 'lazy' filtering -- in fact you try to avoid forcing
evaluation of the whole stream until the very end, and then you
stop when you get a sufficient number, or reach the end of the
stream. ( And if possible, you may not have to force full evaluation
at all if you can do your output one item at a time. You should
avoid list comprehensions though, which force evaluation -- kind
of like Icon's 'every' )

Filter is just:

def filter( f, stream ):
for item in stream:
if f(item): yield item

> 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)
>

```