# 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?

## 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