pure generators
Graham Fawcett
fawcett at uwindsor.ca
Thu May 13 07:31:18 PDT 2010
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
More information about the Digitalmars-d
mailing list