faqts : Computers : Programming : Languages : Python : Snippets

+ Search
Add Entry AlertManage Folder Edit Entry Add page to http://del.icio.us/
Did You Find This Entry Useful?

1 of 1 people (100%) answered Yes

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)