pure generators

[Graham Fawcett]

Hi bearophile,

On Wed, 12 May 2010 19:46:30 -0400, bearophile wrote:

> In Haskell many "generators" are pure, this allows to do things
> like:
>
> fibonacci = 1 : 1 : zipWith (+) fibonacci (tail fibonacci) fibs = take
> 20 fibonacci
> main = print fibs

It's not purity that makes the this code possible in Haskell, it's
lazy evaluation.

> That prints:
> [1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765]
> 
> The meaning of that little Haskell program is simple: fibonacci is a
> symbol, it can be seen as a lazy generator that yields a list of
> numbers. The first and second are 1 (the colon stands for list item
> concatenation), to it concatenates the zipping between the result of the
> generator and another "copy" of the same generator minus the first item.
> 
> You can write the same algorithm in Python using lazy iterators:
> 
> from itertools import izip, islice
> 
> def fibonacci():
>     yield 1
>     yield 1
>     for nm1, n in izip(fibonacci(), islice(fibonacci(), 1, None)):
>         yield nm1 + n
> 
> fibs = islice(fibonacci(), 0, 20)
> print list(fibs)

The comparison is unfair, because those two programs don't do the same
thing -- it looks like they do, but that's a surface similarity.

In the Python code, 'fibonacci' is a constructor that returns a
generator. The body of fibonacci() does not define a function, but
rather a coroutine. Calling the fibonacci() constructor "recursively"
leads to a quadratic growth of generator instances. If the stack
didn't blow so quickly, the heap would soon follow.

In the Haskell code, 'fibonacci' is a list instance: a lazy, infinite
list. The list refers to itself: there is only one instance of it.
This is not equivalent to calling a recursive function; rather you are
creating a recursive, lazy data structure. Because you maintain a
reference to the head of this list, the heap will be consumed --
linearly -- as the tail of list is incrementally evaluated.

> Even if doesn't show, the Haskell compiler is able to optimize quite
> well that little program, it can generate many Fibonacci numbers in a
> short time, while that Python code is really slow, uses tons of RAM, and
> it soon blows up the stack. (Lazyness in Python is easy to use, but it
> was bolted on Python at the last minute and it's not always good
> enough).

Don't blame Python; you're just doing it wrong. :) Python generators
are not lazy lists, and they aren't even functions, they are
coroutines. Apples, oranges, and lemons. The Fibonacci sequence can be
implemented succinctly and efficiently as a Python generator:

def fibonacci():
    a, b = 1, 1
    while True:
        yield a
        a, b = b, a + b

If you use that definition in the following program, which prints the
infinite sequence:

for n in fibonacci():
    print n

...it will run as fast as Python can add two bignums, and it will run
in constant space.

Graham