lambda fun: infinite streams
Joe Bowbeer
joeb at go2net.com
Sat Aug 7 05:53:21 CEST 1999
Fya.
I was doing a little investigating with Python's lambda expressions and
it looks like they are indeed powerful enough to create some of my
favorite beasts: infinitely long streams [*].
If we define a stream to be a 'pair' of the form (head, tail), where
head is the first element and tail is a function that returns the rest
of the stream (which is itself a stream), then we can define 'head' and
'tail' functions in Python as follows:
def head(s): # return first element in stream
return s and s[0]
def tail(s): # return remainder of stream
return s and s[1] and s[1]()
We create a new stream given a head element and a tail stream as
follows:
s = (head, lambda : tail)
# I'd use a 'special form' or macro above if Python had them..
Here are two more functions that operate on streams. (I'd implement
these tail-recursively if it were more efficient.)
def nthStream(s, n): # return nth element of stream s
while n > 0:
s, n = tail(s), n-1
return head(s)
def printStream(s, n): # print first n elements of stream s
while n > 0:
print head(s),
s, n = tail(s), n-1
print
Now things start to get interesting:
# infinite stream of ones
ones = (1, lambda : ones)
# print some ones
printStream(ones, 10)
def addStreams(si, sj): # add corres. elements of two streams
if not si: return sj
if not sj: return si
tailsum = lambda ti=si, tj=sj : addStreams(tail(ti), tail(tj))
return (head(si) + head(sj), tailsum)
# infinitely many integers
integers = (0, lambda : addStreams(ones, integers))
# infinite stream of Fibonacci numbers
fibs = (0, lambda : (1, lambda : addStreams(tail(fibs), fibs)))
# Too bad 'int' can only represent a finite number of digits...
Better performance can be achieved by memo-izing the functions that
evaluate the tails. A simple Memo class can be defined as follows. It
lazily evaluates the 'thunk' function and then memorizes the result:
class Memo: # memoized call-by-need thunk
def __init__(self, thunk):
self.result, self.thunk = None, thunk
def eval(self):
if self.thunk:
self.result, self.thunk = self.thunk(), None
return self.result
Memo-ized streams are created as follows:
s = (head, Memo(lambda : tail))
And the tail function becomes:
def tail(s): # return remainder of stream
return s and s[1] and s[1].eval()
----
*SICP:
Structure and Interpretation of Computer Programs
Abelson and Sussman
http://mitpress.mit.edu/sicp/
----
Joe Bowbeer
More information about the Python-list
mailing list