Lazy evaluation in python: zipping infinite lists

‹ What is memcache? | Spreadsheet dataflow programming ›

One demonstration of lazy evaluation in a programming language is to create an infinitely long list containing the Fibonacci sequence, defined recursively as the concatenation of two lists:

  • the list [1, 1]
  • a list made by zipping the Fibonacci sequence with the tail of the Fibonacci sequence, and summing the resulting pairs

The canonical example code in Haskell is:

fib = 1 : 1 : zipWith (+) fib (tail fib)

It is possible to implement this in Python using a generator to represent the infinite list and the itertools library for lazy operations on generators:

from itertools import izip
from itertools import islice
def fib():
    yield 1
    yield 1
    for l, r in izip(fib(), islice(fib(), 1, None)):
        yield l+r

The above implementation is very slow, since each call to fib() will lead to two more calls to fib(). One way to address this flaw is to use the itertools.tee() function to duplicate an iterator:

from itertools import izip
from itertools import islice
from itertools import tee
from types import GeneratorType

Tee = tee([], 1)[0].__class__
def memoized(f):
    cache = {}
    def ret(*args):
        if args not in cache:
            cache[args] = f(*args)
        if isinstance(cache[args], (GeneratorType, Tee)):
            cache[args], r = tee(cache[args])
            return r
        return cache[args]
    return ret

@memoized
def fib():
    yield 1
    yield 1
    for l, r in izip(fib(), islice(fib(), 1, None)):
        yield l+r

I have not spent the time to investigate whether the above implementation consumes memory without bound. There is approach at https://github.com/kachayev/talks/blob/952c8bfd1c433cebfb46d60e6182b6a3ca4552c8/kharkivpy%236/code/stream_33.py which does the streaming in application code.  I haven't tested it either, but skimming it, it may have better memory usage properties.

Subscribe to All Posts - Wesley Tanaka