Mailing List Archive

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