Infinite lists and generators

[Steven D. Majewski]

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

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