Entry
Fun with lazy streams
Jul 5th, 2000 10:03
Nathan Wallace, Hans Nowak, Snippet 379, Tim Peters
"""
Packages: functional_programming
"""
"""
Thought a fair # of people might enjoy playing with the attached. I've
likely posted all of it before over the years, but in scattered pieces
and
spelled different ways.
premature-spring-cleaning-ly y'rs - tim
PS: If this kind of thing really appeals to you, check out a language
in
which it's *natural*. I recommend Haskell (http://www.haskell.org/), in
which this kind of thing is as natural as breathing (and requires about
a
tenth the lines of code; or maybe a third if you don't take advantage of
Haskell's std libraries).
"""
class Stream:
def __init__(self, first, restf):
"""Construct an unbounded stream s from 'first' & 'restf'.
'first' is the first element of s, and is returned by
s.head().
'restf' is a no-argument function that, when invoked,
produces a Stream that is the rest of s. s.tail()
invokes restf.
"""
self.first = first
self.restf = restf
def head(self):
"""Return first element of stream."""
return self.first
def tail(self):
"""Return the stream from the 2nd element onward."""
return self.restf()
# Generally useful stream functions.
def sget(s, n):
"""s, n -> a list of the first 'n' elements of stream 's'."""
result = []
for i in xrange(n):
result.append(s.head())
s = s.tail()
return result
def szip(s, binop, t):
"""s, binop, t -> stream 's' zipped w/ stream 't' via 'binop'.
The result is the Stream
binop(s[0], t[0]), binop(s[1], t[1]), ...
"""
return Stream(binop(s.head(), t.head()),
lambda s=s, binop=binop, t=t:
szip(s.tail(), binop, t.tail()) )
def srange(i, inc=1):
"""i, inc=1 -> the stream i, i+inc, i+2*inc, ..."""
return Stream(i,
lambda i=i, inc=inc: srange(i+inc, inc))
def sfilter(s, pred):
"""s, pred -> the substream of 's' elements satisfying 'pred'.
Caution: this will get into an infinite loop if you try to
materialize enough of s so that no elements satisfying pred
remain in the rest of s.
"""
while not pred(s.head()):
s = s.tail()
return Stream(s.head(),
lambda s=s, pred=pred: sfilter(s.tail(), pred))
def smap(s, f):
"""Return stream f(s[0]), f(s[1]), ..."""
return Stream(f(s.head()),
lambda s=s, f=f: smap(s.tail(), f))
def sunion2(s, t):
"""s, t -> stream union.
s and t are increasing streams. Return the increasing
stream that is the union of s and t without duplicates.
"""
s1, t1 = s.head(), t.head()
if s1 == t1:
return Stream(s1, lambda s=s, t=t:
sunion2(s.tail(), t.tail()))
elif s1 < t1:
return Stream(s1, lambda s=s, t=t:
sunion2(s.tail(), t))
else:
return Stream(t1, lambda s=s, t=t:
sunion2(s, t.tail()))
def sunion(s, *streams):
"""Stream union of one or more increasing streams."""
result = s
for stream in streams:
result = sunion2(result, stream)
return result
def sintersect2(s, t):
"""s, t -> stream intersection.
s and t are increasing streams. Return the increasing
stream containing the elements they have in common.
"""
while 1:
s1, t1 = s.head(), t.head()
if s1 == t1:
break
elif s1 < t1:
s = s.tail()
else:
t = t.tail()
return Stream(s1, lambda s=s, t=t:
sintersect2(s.tail(), t.tail()))
def sintersect(s, *streams):
"""Stream intersection of one or more increasing streams."""
result = s
for stream in streams:
result = sintersect2(result, stream)
return result
def sdifference(s, t):
"""s, t -> stream difference.
s and t are increasing streams. Return the increasing
stream containing the elements of s not in t.
"""
while 1:
s1, t1 = s.head(), t.head()
if s1 < t1:
break
elif s1 == t1:
s = s.tail()
t = t.tail()
else:
t = t.tail()
return Stream(s1, lambda s=s, t=t:
sdifference(s.tail(), t))
# Fun examples.
ones = Stream(1, lambda: ones)
print "ones:", sget(ones, 10) # infinite stream of 1's
ints = srange(1)
print "ints:", sget(ints, 10) # guess
def sadd(s, t):
return szip(s, (lambda i, j: i+j), t)
print "ones + ints:", sget(sadd(ones, ints), 10)
fibs = Stream(1,
lambda: Stream(1,
lambda: sadd(fibs, fibs.tail())))
print "fibs:", sget(fibs, 10) # i.e., the Fibonacci numbers
# Stream of all primes.
def removemults(s, n): # s but without any multiples of n
def notdivisible(i, n=n):
return i % n
return sfilter(s, notdivisible)
def sieve(s):
return Stream(s.head(),
lambda s=s:
sieve(removemults(s.tail(), s.head())))
primes = sieve(srange(2))
print "primes:", sget(primes, 15)
# Increasing stream of all ints divisible by at least one of
# 3, 5 and 7.
multiples_of_3 = srange(3, 3)
multiples_of_5 = srange(5, 5)
multiples_of_7 = srange(7, 7)
divany357 = sunion(multiples_of_3,
multiples_of_5,
multiples_of_7)
print "divany357:", sget(divany357, 40)
# Increasing stream of all ints divisible by all of
# 3, 5 and 7.
divall357 = sintersect(multiples_of_3,
multiples_of_5,
multiples_of_7)
print "divall357:", sget(divall357, 20) # detect a pattern?
print "hmm :", sget(srange(105, 105), 20)
# Increasing stream of all ints divisible by nothing other
# than 3, 5 or 7 (i.e., of the form 3**i * 5**j * 7**k for
# i, j, k >= 0). Note: this is a famous problem. Try
# doing it efficiently without lazy streams! If you do,
# be very sure your program is correct too <wink>.
def timesn(s, n): # multiply stream by int
return smap(s, (lambda i, n=n: i*n))
divonly357 = Stream(1,
lambda: sunion(timesn(divonly357, 3),
timesn(divonly357, 5),
timesn(divonly357, 7)))
print "divonly357:", sget(divonly357, 20)
# Increasing stream of ints *not* of the form 3**i*5**j*7**k.
print "divnotonly357:", sget(sdifference(ints, divonly357), 20)
