Iteration and Generators

Iteration in Python

• for loops are very common in Python

• They operate on iterators

• Just about any composite data type is iterable

  • Lists

  • Dictionaries

  • Strings

  • Files

  • …

What’s an Iterator?

An iterator is an object that yields a data stream …

• The next() method yields the next element in the stream

• If there is no next element, it raises the StopIteration exception

Question: where do iterators come from?

Answer: they are made by iterables

What’s an Iterable?

Iterables are objects that support iteration (Gosh!)

Iterables that are built into Python are for example …

• Sequence, tuple

• Dictionary (iteration yields key/value pairs)

• Set

• String

• File

• … and many more …

The Iterator Protocol (1)

Technically speaking …

• An iterable can make an iterator through the __iter__()

  method

• Not usually done by hand

• Done for me by for loop

for elem in iterable:
    ... do something with elem ...

The interpreter …

• Creates an iterator before entering the loop (⟶ __iter__())

• Calls next() on that iterator before every iteration

• Terminates the loop when StopIteration is caught

The Iterator Protocol (2)

iterator = iter(iterable)
try:
    i = next(iterator)
except StopIteration:
    ...

• Often the calculation of the next element is complicated

• ⟶ object state has to be kept manually

• Coding iterables is no fun

• … at least not without language support

Generators: Motivation

Examples of complicated iteration …

• Traverse a binary tree in depth-first or breadth-first order

• Infinite sets like Fibonacci numbers

Stupid solution:

• Store result in a list

• Return the list

• ⟶ Problem with large iterables (Fibonacci?)

• ⟶ Best to generate on-demand

Generators: How?

def odd_numbers():
    i = 0
    while True:
        if i%2 != 0:
            yield i
        i += 1

for j in odd_numbers():
    print(j)

Observations

• odd_numbers is iterable

• yield is magic

• Every function that calls yield is a generator

• Each call to next(iterator) (speak: execution of the for body) continues the function where yield left it.

• This is outright genius!

More on Generators

Python 2 to 3 transition

• range() is a generator in 3

• Python 2: returns a (temporary) list

• … had to use xrange() to generate

• Many more places converted to generators

Standard library helpers

• itertools

• operator