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:
> > 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)
>
More information about the Python-list
mailing list