Learnings

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

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.

ToolEach 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

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.

ToolGives
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 classGenerator functionGenerator expression
How you write itA class with __iter__ and __next__A def with yield(x for x in items)
Where the position livesIn attributes you manageIn local variables, kept for youHidden
Amount of codeMostLittleOne line
Use it whenThe object needs extra methods or attributes, or is a container that must give a fresh iterator each timeThe logic needs several statements, a loop with state, cleanup, or never endsA simple transform or filter that is consumed once, straight away
Example on this pageAccount and Passbookpassbook, pipeline stagessum(amount for ...)
You want toWrite
Step through something by handit = iter(items), then next(it)
Get a default instead of StopIterationnext(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 anythingislice(it, n)
Join generatorsyield from other or chain(a, b)
Loop more than onceKeep 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.