lambda fun: infinite streams

[Joe Bowbeer]

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