Python advanced, part 2 of 5
Python Iterators and Generators
Every for loop you have written used an iterator without showing it. This page opens the loop up to see the two functions behind it, then writes iterators by hand, and then shows generators, the short way to write the same thing. The examples use a small family bank: accounts, transactions and statements.
Iterators
Part 1 of 2 · what a for loop really does
An iterator is an object that hands out items one at a time and remembers where it is. Lists, strings, dictionaries and files can all be looped over because each of them can supply an iterator when asked.
- A for loop by hand:
iter(),next()andStopIteration - Iterable and iterator: two words, two different things
- Writing an iterator class: a countdown
- A passbook iterator: walking through an account's transactions
- Making a class iterable: a fresh iterator for every loop
- The __getitem__ fallback: the old way still works
- Lazy built-in tools:
enumerate,zip,map,filter,reversed - iter with a stop value: call a function until it says stop
A for loop by hand
A for loop does two things. First it calls iter() on the collection to get an iterator. Then it calls next() on that iterator again and again. Each call returns the next item. When nothing is left, next() raises the error StopIteration, and the loop ends quietly.
So this for loop and this while loop do the same work. The first is what you write. The second is what Python does.
Iterable and iterator
An iterable is anything you can loop over. It has an __iter__ method, which iter() calls. An iterator is the object that does the stepping. It has a __next__ method, which next() calls. A list is an iterable, but it is not an iterator.
The last line matters. An iterator is also iterable, and asking it for an iterator gives back the same object. That is why you can use an iterator in a for loop.
An iterator is used up once
An iterator only moves forward. After it reaches the end it stays empty. The list is not touched, so you can always ask it for a new iterator.
Picture: the list is a passbook. An iterator is a finger moving down the page. Many fingers can point into the same passbook, and each one moves only forward.
Writing an iterator class
Any class with these two methods is an iterator. __iter__ returns self. __next__ returns the next item, or raises StopIteration when it has none.
Nothing here stores the numbers 5, 4, 3, 2, 1. Each one is worked out at the moment it is asked for. And because the class follows the rules, for, list() and sum() all accept it.
Protocol: these two methods together are called the iterator protocol. A protocol is an agreement about method names. Python does not care what the class is, only that the methods are there.
A passbook iterator
The same shape with bank data. The iterator walks through a list of transactions and returns each one together with the balance after it. Its state is a position and a running balance.
The second loop gets nothing, because the iterator is used up. For a countdown that is fine. For an account it is a nuisance: you want to print the statement as often as you like. The next chapter fixes that.
Making a class iterable
Split the two roles. The Account holds the data and is the iterable. Its __iter__ builds and returns a new iterator every time. Each loop then starts from the top, just as it does with a list.
Rule of thumb: a container should be an iterable that returns a fresh iterator. Only the short-lived stepping object should return self from __iter__.
The __getitem__ fallback
There is an older, second way. If a class has no __iter__ but has __getitem__, Python tries index 0, 1, 2 and so on until it gets an IndexError.
Advice: know that this exists, because you will see it in old code. In new code write __iter__. It says clearly that the class is meant to be looped over.
Lazy built-in tools
Several built-in functions you already use return iterators, not lists. They are lazy: they do no work until something asks for the next item. Wrap them in list() to see everything at once.
| Tool | Each next() gives |
|---|---|
enumerate(items) | a pair: a running number and the item |
zip(a, b) | a tuple with one item from each. Stops at the shortest |
map(func, items) | func(item) for the next item |
filter(func, items) | the next item for which func(item) is true |
reversed(sequence) | the items from last to first, without copying the sequence |
Also lazy: range() works numbers out on demand too, though it is an iterable and not an iterator, so you can loop over the same range many times. A file object is an iterator over its lines.
iter with a stop value
iter() has a second form with two arguments: a function and a stop value, called a sentinel. The iterator calls the function again and again, and ends when the function returns the sentinel.
Where it helps: reading a file in fixed-size pieces until an empty piece comes back, or reading messages until a "stop" message arrives.
Generators
Part 2 of 2 · iterators written the short way
An iterator class needs three methods and has to keep its own position. A generator is a function that Python turns into an iterator for you. You write an ordinary loop and put yield where each value should come out.
- Generator functions:
yieldinstead of a class - Pause and resume: how the function runs in pieces
- Lazy means small: memory used by a list and by a generator
- Infinite generators: endless streams and
islice - Generator expressions: a comprehension in round brackets
- Generator pipelines: small steps joined together
- yield from: hand over to another generator
- Sending values in:
send() - Return value and close: how a generator ends
- A tour of itertools: ready-made iterator tools
- Common mistakes and which one to use
Generator functions
Here is Countdown again, first as the class from before, then as a generator function. Both give the same numbers.
Any function with yield in its body is a generator function. Calling it does not run the body. It returns a generator object, which is an iterator: it has __iter__ and __next__, and raises StopIteration when the function ends.
What you saved: no class, no self.current, no raise StopIteration. The position is simply the local variable current and the place where the function is waiting.
Pause and resume
return ends a function and throws its local variables away. yield hands out a value and pauses the function with everything kept. The next next() continues from the line after the yield.
Local variables survive each pause. That is how a generator keeps a running balance without any class.
Compare: this is the whole passbook iterator from earlier, in five lines.
Lazy means small
A list holds all its items in memory at once. A generator holds only the code and where it has got to, and makes each item when asked. So its size does not grow with the number of items.
The exact sizes differ between Python versions, so the example prints comparisons. On this machine the list takes roughly 800 kilobytes and the generator about a hundred bytes. With a million items the list would be ten times larger. The generator would stay the same.
Trade: a generator saves memory but gives up what a list can do. You cannot index it, ask its length, or go through it twice.
Infinite generators
Because items are made on demand, a generator may never end. A while True loop with a yield inside is safe, as long as the caller stops asking. itertools.islice takes the first few items from any iterator.
Monthly interest, forever. The caller decides how many months to look at.
Generator expressions
A list comprehension in round brackets is a generator expression. It is the shortest way to make a generator when the logic fits on one line.
Choose: use a generator expression when the result is consumed once, straight away, by something like sum(), max(), any() or join(). Use a list comprehension when you need to keep the items.
Generator pipelines
A generator can take another iterator as its input. Join several and you have a pipeline: each stage does one small job and passes items on, one at a time. No stage ever holds the whole file in memory.
Nothing is read until sum() asks for the first amount. That request travels back through the stages to the file, one line comes forward, and so on. The same code would work on a file with millions of lines.
Shape: each stage is "for each item coming in, maybe yield something out". Short stages can also be written as generator expressions.
yield from
yield from other yields every item of another iterable, one by one. It replaces the loop for item in other: yield item.
Flattening nested data
It is most useful when a generator calls itself. The family's money is spread over nested dictionaries. The generator walks down every branch and yields only the amounts.
Sending values in
So far values only came out. yield can also receive a value. Written as amount = yield balance, it hands out balance, pauses, and when the caller uses send(value), that value becomes amount. A generator used this way is often called a coroutine.
The first next() is required. It moves the generator to its first yield, where it can receive something. Sending a value before that raises TypeError.
A running average works the same way.
How often: you will rarely write send() yourself. It is worth knowing because async and await, covered later, grew out of this idea.
Return value and close
A generator ends when its function ends. A plain return stops it early. A return value is allowed too, but a for loop never sees that value. It travels inside the StopIteration error, and yield from picks it up.
close()
close() stops a paused generator for good. Python raises GeneratorExit at the paused yield, so a finally block or a with block inside the generator still cleans up.
A tour of itertools
The standard module itertools is a box of ready-made lazy iterators. They combine well with generators and with each other.
count, cycle, chain, islice
accumulate and groupby
accumulate gives running totals. groupby collects neighbouring items with the same key, so sort by that key first.
product, permutations, combinations
These make every arrangement of their input. The results grow very fast, which is exactly why they are lazy.
| Tool | Gives |
|---|---|
count(start, step) | numbers without end |
cycle(items) | the items again and again, without end |
chain(a, b, ...) | all of a, then all of b, and so on |
islice(it, stop) or islice(it, start, stop, step) | a slice of any iterator |
accumulate(items) | running totals |
groupby(items, key) | pairs of a key and an iterator over the neighbouring items with that key |
product(a, b) | every pairing of an item from a with an item from b |
permutations(items, r) | every ordered choice of r items |
combinations(items, r) | every choice of r items, ignoring order |
Common mistakes
Going through a generator twice
A generator is an iterator, so it is used up after one pass. The second pass is empty and gives no error, which makes this easy to miss.
Asking a generator for its length or an index
A generator does not know how many items it will give, and it cannot jump to a position.
Collecting an infinite generator
list(), sum() and sorted() keep asking until the end. An infinite generator has no end, so the program hangs and memory fills up. This block is not run by the page checker, because it would never finish.
Take a limited number of items first.
Also watch for: a function that tests an iterator, such as if 9000 in generator, uses up every item it had to look at.
Which one to use
All three give you an iterator. Pick the smallest one that does the job.
| Iterator class | Generator function | Generator expression | |
|---|---|---|---|
| How you write it | A class with __iter__ and __next__ | A def with yield | (x for x in items) |
| Where the position lives | In attributes you manage | In local variables, kept for you | Hidden |
| Amount of code | Most | Little | One line |
| Use it when | The object needs extra methods or attributes, or is a container that must give a fresh iterator each time | The logic needs several statements, a loop with state, cleanup, or never ends | A simple transform or filter that is consumed once, straight away |
| Example on this page | Account and Passbook | passbook, pipeline stages | sum(amount for ...) |
| You want to | Write |
|---|---|
| Step through something by hand | it = iter(items), then next(it) |
Get a default instead of StopIteration | next(it, None) |
Make your own class work in a for loop | __iter__ that returns a fresh iterator, or is itself a generator function |
| Take the first n items of anything | islice(it, n) |
| Join generators | yield from other or chain(a, b) |
| Loop more than once | Keep a list, or call the generator function again |
The shortest iterable class of all combines both halves of this page: write __iter__ as a generator function. Each loop calls it and gets a new generator.
Generators run one piece at a time. To run several jobs at the same time, continue with Python Threads and Processes.