F2.5 · LESSON 5 OF 6

Generators and lazy iteration

Organize a small program into modules and classes while handling files, failures and iteration.

THE IDEA

Produce values when asked, not all at once

Suppose you want the squares of the first million numbers. A list holds all of them at the same time. A generator holds none: it computes the next value only when something asks. A function becomes a generator function the moment its body contains yield. Calling it does not run the body. It returns a generator object.

limit20

def squares_up_to(limit): n = 1 while n * n <= limit: yield n * n n += 1

Generator object

statenot started

local ndoes not exist yet

g = squares_up_to(20)(nothing yet)

Values handed out so far

none

A list of all 4 squares would hold 4 values at once. The generator holds one local variable n and its place in the code.

The call built a generator object. Not one line of the function body has run yet.

Press next(g). The function runs until the next yield, hands out a value and freezes with its local variables intact. Move the slider and reset to change the limit.

for loops, list() and sum() all work by calling next until StopIteration. That is why generators plug into ordinary Python code.

Why it matters: memory and endless streams

A lazy generator does not need space for every result, and it can represent a sequence with no end, such as lines of a huge log file or an endless counter. You take only what you need.

import sysn = 100000as_list = [i * i for i in range(n)]lazy = (i * i for i in range(n))print("list of", n, "squares:", sys.getsizeof(as_list), "bytes (the list itself)")print("generator:", sys.getsizeof(lazy), "bytes")print("same total:", sum(lazy) == sum(as_list))print("second sum of the same generator:", sum(lazy))

Both lines produce the same 100000 squares. Press the button to see how much space each one needs.

Real sizes measured by Python in your browser.

Generator expressions

squares = (n * n for n in range(1_000_000))     # round brackets: lazy, nothing computed yet
first = next(squares)                            # 0
rest_total = sum(squares)                        # consumes the remaining values

One pass only

A generator remembers its position, and there is no rewind. Once it has produced its last value it is exhausted: asking again gives nothing.

Predict first. g = (n for n in range(3)), then list(g) runs. What does a second list(g) give?

The bug in disguise

evens = (n for n in range(10) if n % 2 == 0)
total = sum(evens)            # 20
count = len(list(evens))      # 0  <- already exhausted!
average = total / count       # ZeroDivisionError

Chapter context

As a program grows, the difficult part becomes keeping state and responsibilities understandable. Use simple functions for transformations, classes for related state and behavior, and modules to give those responsibilities names.

TRY IT YOURSELF

Exercise 1: a lazy running total

Write the generator function running_total(values). It yields the total so far after each value: for [1, 2, 3] it yields 1, 3, 6.
It must be lazy: it reads one input value only when the next result is asked for. So it also works on an endless source, and it must not build a list first.
A generator is used up after one pass. Calling running_total(...) again gives a fresh generator.

def running_total(values):
    # TODO: keep a total, and yield it after adding each value
    pass

# print(list(running_total([1, 2, 3])))   # [1, 3, 6]

Ctrl/⌘ + Enter runs it

Exercise 2: lazy chunks

Write the generator chunks(iterable, size) that yields lists of size items, in order. The last list may be shorter. list(chunks([1, 2, 3, 4, 5, 6, 7], 3)) is [[1, 2, 3], [4, 5, 6], [7]].
It must not read more than it needs: asking for the first chunk reads only size items. It must work on any iterable, including another generator.
No trailing empty list. If size is less than 1, raise ValueError when the generator is first used.

def chunks(iterable, size):
    # TODO: collect items into a list; yield it when it reaches size;
    # after the loop, yield what is left (if anything)
    pass

# print(list(chunks([1, 2, 3, 4, 5, 6, 7], 3)))   # [[1, 2, 3], [4, 5, 6], [7]]

Ctrl/⌘ + Enter runs it

Both exercises must be solved to finish this lesson.

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

What remains after list(g) consumes a finite generator g?

AA second list(g) returns an empty list.BThe same values again, because list(g) rewinds the generator before reading it.CA TypeError, because a generator can only be consumed with a for loop.

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

Reason about state ownership before adding abstraction. For a transformation f, repeated calls should have independent results unless shared state is explicitly intended. A lazy iterator retains only the state required for its next step; it does not imply that downstream consumers also use constant memory.

Worked example

An inventory starts with 5 items. reserve(2) leaves 3. A second independent inventory still contains 5. If both objects instead refer to the same list, mutating one changes what both observe. Draw object references as arrows to make this distinction explicit.

Reference code

The following example uses the Python standard library and does not call a remote service.

class Inventory:
    def __init__(self, count):
        self.count = count
    def reserve(self, n):
        if n > self.count:
            raise ValueError("insufficient stock")
        self.count -= n
first, second = Inventory(5), Inventory(5)
first.reserve(2)
assert (first.count, second.count) == (3, 5)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Type annotations are not validation. Catching Exception and continuing can hide corrupt state. Lazy iteration does not make a later list(...) memory-free.