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__()


  • 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)
    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():


  • 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