Der Blog

Gimbo, as many of you know, is learning Haskell, and just discovered the power and conciseness of lazy evaluation with a one-line definition of the entire Fibonacci sequence.

You can do a vaguely similar thing in Python. First we have a lazy list class:

class LazyList:
    def __init__(self):
        self._list = []

    def __getitem__(self, key):
        length = len(self._list)
        if key.__class__ == int:
            max = key
        elif key.__class__ == slice:
            max = key.stop
        if max >= length:
            for i in xrange(length-1,max):
                self._list.append(self._gen.next())
        return self._list[key]

To create the actual Fibonacci sequence, we define a subclass:

class FibList(LazyList):
    def __init__(self):
        def fibgen():
            lastfib = 0
            nextfib = 1
            yield lastfib
            yield nextfib
            while True:
                (lastfib, nextfib) = (nextfib, lastfib+nextfib)
                yield nextfib
        LazyList.__init__(self)
        self._gen = fibgen()

Then a "list" (not really a list, but looks like one) of the Fibonacci numbers is

somefibs = FibList()

and we can look up the nth Fibonacci number, and take slices of it:

>>> somefibs[0]
0
>>> somefibs[3]
2
>>> somefibs[0:3]
[0, 1, 1]
>>> somefibs[2:20:4]
[1, 8, 55, 377, 2584]

But of course this isn't a one-liner. Plus we've fallen victim to a variant of Greenspun's Tenth Rule, substituting "Common Lisp" with "Haskell 98" :)