Python Adventures

“Generators are a simple and powerful tool for creating iterators. They are written like regular functions but use the yield statement whenever they want to return data. Each time next() is called, the generator resumes where it left-off (it remembers all the data values and which statement was last executed).”

Let’s rewrite our Fibonacci function using generators. In the previous approach, we specified how many Fibonacci numbers we want to get. The function calculated all of them and returned a list containing all the elements. With generators, we can calculate the numbers one by one. The new function will calculate a number, return it, and suspend its execution. When we call it again, it will resume where it left off and it runs until it computes another number, etc.

First let’s see a Fibonacci function that calculates the numbers in an infinite loop:

#!/usr/bin/env python

def fib():
    a, b = 0, 1
    while True:
        print a    # the current number is here
        a, b = b, a+b

fib()

In order to rewrite it in the form of a generator, we need to locate the part where the current value is calculated. This is the line with print a. We only need to replace this with yield a. It means that the function will return this value and suspend its execution until called again.

So, with generators it will look like this:

#!/usr/bin/env python

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

f = fib()
for i in range(10):    # print the first ten Fibonacci numbers
    print f.next(),    # 0 1 1 2 3 5 8 13 21 34

It is also possible to get a slice from the values of a generator. For instance, we want the 5^th, 6^th, and 7^th Fibonacci numbers:

#!/usr/bin/env python

from itertools import islice

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

for i in islice(fib(), 5, 8):
    print i    # 5 8 13

More info on islice is here. For this post I used tips from here.

Update (20110406)

Here is a presentation in PDF entitled “Generator Tricks For Systems Programmers” by David Beazley (presented at PyCon 2008). (_{Reddit thread is here.})