Python does not execute the body of a newly created function, but instead waits until that function is called. Defining a function creates the potential to compute results for any input, but the actual computation is delayed until requested.
This pattern of setting up potential computation, but only performing it upon request, can extend to other kinds of objects beyond functions. In this section, we extend this pattern to sequences, creating objects that can compute the items of a sequence in order, but don’t actually compute them until prompted.
Lazy Evaluation. Broadly, the term lazy evaluation describes setting up but then delaying computation until it is needed, which contrasts with eager evaluation, a term to describe computation that is performed as soon as it is described. Simple examples of each are the lazy_fib and eager_fib functions below, which both return Fibonacci numbers. (The item at index -2 is the second to last item in a list, and -1 is the last index.)
>>> eager_cache = [0, 1]
>>> for _ in range(2, 100):
eager_cache.append(eager_cache[-2] + eager_cache[-1])
>>> def eager_fib(n):
assert n < 100
return eager_cache[n]
>>> lazy_cache = [0, 1]
>>> def lazy_fib(n):
while len(lazy_cache) < n + 1:
lazy_cache.append(lazy_cache[-2] + lazy_cache[-1])
return lazy_cache[n]
>>> eager_fib(15), lazy_fib(15)
(610, 610)
>>> eager_fib(10), lazy_fib(10)
(55, 55)
>>> eager_fib(20), lazy_fib(20)
(6765, 6765)Lazy evaluation can be useful for both efficiency and interactivity. If a long list of values were created, but only a few were used to compute some final result of interest, then creating the rest would be inefficient. Also, when software is being used interactively, a user often makes a sequence of requests, and the software should be set up to answer each one, but not perform the computation until each request arrives. Lazy evaluation can also be more flexible, as in the example above, where eager_fib is constrained to n below 100 but lazy_fib is only constrained by the computer’s memory.
Implicit Sequences. A sequence can be represented without each item being stored explicitly in the memory of the computer. That is, we can construct an object that provides access to all of the items of some sequential dataset without computing the value of each item in advance. Instead, we compute items on demand.
An example of this idea arises in the range container type introduced in Section 2.2. A range represents a consecutive, bounded sequence of integers. However, it is not the case that each item of that sequence is represented explicitly in memory. Instead, when an item is requested from a range, it is computed. Hence, we can represent very large ranges of integers without using large blocks of memory. Only the end points of the range are stored as part of the range object.
>>> r = range(10000, 1000000000)
>>> r[45006230]
45016230In this example, not all 999,990,000 integers in this range are stored when the range instance is constructed. Instead, the range object adds the first item 10,000 to the index 45,006,230 to produce the item 45,016,230. Computing values on demand, rather than retrieving them from an existing representation, is another example of lazy evaluation.
Iterators¶
Python and many other programming languages provide a unified way to process items of a container value sequentially, called an iterator. An iterator is an object that provides sequential access to values, one by one.
The iterator abstraction is a mechanism for retrieving the next item in the sequence being processed, which advances the iterator. In Python an iterator can be obtained for any container, such as a list or range, by calling the built-in iter function. The contents of the iterator can be accessed by calling the built-in next function.
>>> primes = [2, 3, 5, 7]
>>> type(primes)
<class 'list'>
>>> iterator = iter(primes)
>>> type(iterator)
<class 'list_iterator'>
>>> next(iterator)
2
>>> next(iterator)
3
>>> next(iterator)
5In Python, calling next on an iterator that has already advanced past the last item in the sequence it represents is an error.
>>> next(iterator)
7
>>> next(iterator)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIterationAn iterator maintains local state to represent its position in a sequence. Each time next is called, that position advances. Two separate iterators can track two different positions in the same sequence. However, two names for the same iterator will share a position, because they are both names for the same iterator object.
>>> r = range(3, 13)
>>> s = iter(r) # 1st iterator over r
>>> next(s)
3
>>> next(s)
4
>>> t = iter(r) # 2nd iterator over r
>>> next(t)
3
>>> next(t)
4
>>> u = t # Alternate name for the 2nd iterator
>>> next(u)
5
>>> next(u)
6Advancing the second iterator does not affect the first. Since the last value returned from the first iterator was 4, it is positioned to return 5 next. On the other hand, the second iterator is positioned to return 7 next.
>>> next(s)
5
>>> next(t)
7Calling iter on an iterator will return that iterator, not a copy. This behavior is included in Python so that a programmer can call iter on a value to get an iterator without having to worry about whether it is an iterator or a container.
>>> v = iter(t) # Another alternate name for the 2nd iterator
>>> next(v)
8
>>> next(u)
9
>>> next(t)
10The usefulness of iterators is derived from the fact that the underlying series of data for an iterator may not be represented explicitly in memory. An iterator provides a mechanism for considering each of a series of values in turn, but all of those items do not need to be stored simultaneously. Instead, when the next item is requested from an iterator, that item may be computed on demand instead of being retrieved from memory, which is an example of lazy evaluation.
Ranges are able to compute the items of a sequence lazily because the sequence represented is uniform, and any item is easy to compute from the starting and ending bounds of the range. Iterators allow for lazy generation of a much broader class of underlying sequential datasets because they do not need to provide access to arbitrary items of the underlying sequence. Instead, iterators are only required to compute the next item of the sequence, in order, each time another item is requested. While not as flexible as accessing arbitrary items of a sequence (called random access), sequential access to sequential data is often sufficient for data processing applications.
Iterables¶
Any value that can produce iterators is called an iterable value. In Python, an iterable value is anything that can be passed to the built-in iter function. Iterables include sequence values such as strings and tuples, as well as other containers such as sets and dictionaries.
>>> d = {'one': 1, 'two': 2, 'three': 3}
>>> d
{'one': 1, 'two': 2, 'three': 3}
>>> k = iter(d)
>>> next(k)
'one'
>>> next(k)
'two'
>>> v = iter(d.values())
>>> next(v)
1
>>> next(v)
2Iterators are also iterables, because they can be passed to the iter function.
Built-in Iterators¶
Several built-in functions take as arguments iterable values and return iterators. These functions are used extensively for lazy sequence processing.
The map function is lazy: calling it does not perform the computation required to compute items of its result. Instead, an iterator object is created that can return results if queried using next. We can observe this fact in the following example, in which the call to print is delayed until the corresponding item is requested from the doubled iterator.
>>> def double_and_print(x):
print('***', x, '=>', 2*x, '***')
return 2*x
>>> s = range(3, 7)
>>> doubled = map(double_and_print, s) # double_and_print not yet called
>>> next(doubled) # double_and_print called once
*** 3 => 6 ***
6
>>> next(doubled) # double_and_print called again
*** 4 => 8 ***
8
>>> list(doubled) # double_and_print called twice more
*** 5 => 10 ***
*** 6 => 12 ***
[10, 12]The filter, zip, and reversed functions also return iterators.
For Statements¶
The for statement in Python operates on iterators. Any iterable object can be the value of the <expression> in the header of a for statement:
for <name> in <expression>:
<suite>To execute a for statement, Python evaluates the header <expression>, which must yield an iterable value. Then, iter is called on that value. Until a StopIteration exception is raised, Python repeatedly calls next on that iterator, binds the result to the <name> in the for statement, and executes the <suite>.
>>> counts = [1, 2, 3]
>>> for item in counts:
print(item)
1
2
3In the above example, the counts list provides a list iterator. The for statement then calls next on that iterator repeatedly, and assigns the returned value to item each time. This process continues until the iterator raises a StopIteration exception, at which point execution of the for statement concludes.
Generators and Yield Statements¶
A generator is an iterator returned by a special class of function called a generator function. Generator functions are distinguished from regular functions in that they use yield statements to produce the items of a sequence.
A generator controls the execution of its generator function, which runs until the next yield statement is executed each time next is called on the generator.
>>> def letters_generator():
current = 'a'
while current <= 'd':
yield current
current = chr(ord(current)+1)
>>> for letter in letters_generator():
print(letter)
a
b
c
dThe yield statement indicates that we are defining a generator function. When called, a generator function doesn’t return a particular yielded value, but instead a generator (which is a type of iterator) that can produce the yielded values. Calling next on the generator continues execution of the generator function from wherever it left off previously until another yield statement is executed.
The first time next is called, the program executes statements from the body of the letters_generator function until it encounters the yield statement. Then, it pauses and returns the value of current. The yield statement does not exit the generator function or remove its environment. Instead, executing the body of the generator function continues when next is called again, right from where it left off. The values of current and of any other bound names in the scope of letters_generator are preserved across subsequent calls to next.
We can walk through the generator by manually calling next:
>>> letters = letters_generator()
>>> type(letters)
<class 'generator'>
>>> next(letters)
'a'
>>> next(letters)
'b'
>>> next(letters)
'c'
>>> next(letters)
'd'
>>> next(letters)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIterationThe generator does not start executing any of the body statements of its generator function until the first time next is called on it. The generator raises a StopIteration exception whenever its generator function returns.
Generator functions enable lazy evaluation of arbitrary sequences. Any sequence of values can be defined using a generator function, but none of them are computed until next is called on their generator to request them.
Yielding from an iterable. A yield from statement yields all items in an iterable. It is equivalent to iterating over the iterable and yielding each one. The following two implementations of range_twice are equivalent.
>>> def range_twice(a, b):
yield from range(a, b)
yield from range(a, b)
>>> list(range_twice(2, 6))
[2, 3, 4, 5, 2, 3, 4, 5]
>>> def range_twice(a, b):
for x in range(a, b):
yield x
for x in range(a, b):
yield x
>>> list(range_twice(2, 6))
[2, 3, 4, 5, 2, 3, 4, 5]Multiple Generators. Multiple calls to the same generator function create multiple generators that each keep track of their own environment and position in the body of the function. The example below shows three generators and the result of calling next multiple times on each one.
>>> def squares_and_cubes(n):
while n < 5:
yield n * n
yield n * n * n
n = n + 1
>>> a = squares_and_cubes(3) # 9, 27, 16, 64
>>> next(a)
9
>>> b = squares_and_cubes(3) # 9, 27, 16, 64
>>> next(a)
27
>>> next(b) # b is unaffected by the calls to next(a)
9
>>> next(a)
16
>>> c = squares_and_cubes(2) # 4, 8, 9, 27, 16, 64
>>> next(c)
4
>>> for v in b:
print('the next item in b is', v)
the next item in b is 27
the next item in b is 16
the next item in b is 64
>>> list(c)
[8, 9, 27, 16, 64]
>>> list(c) # c has no items left
[]
>>> list(a)
[64]Infinite Generators. Because the body of a generator function is executed lazily, it can potentially compute and yield an infinite number of values without causing a program to run forever, as long as only a prefix of those values are ever requested using next or for.
For example, this function iterates over all squares of positive numbers.
>>> def squares(n):
while True:
yield n * n
n = n + 1
>>> all_squares = squares(1)
>>> [next(all_squares), next(all_squares), next(all_squares)]
[1, 4, 9]However, calling list(squares(1)) would initiate an infinite computation that would use up all available memory and then error.
Recursive Generators¶
A generator function can call itself. Every call to a generator function returns a generator, and so the result of the recursive call requires processing this generator, most often using a for statement.
The partitions function defined in Section 2.3 returned a list of partitions of n using parts of up to m. That function computes all partitions eagerly. The version below computes the same partitions lazily.
>>> def partitions_gen(n: int, m: int):
"""Yield partitions of n using parts of up to m.
Each partition is represented as a linked list.
"""
if n == 0:
yield () # the empty partition
elif n > 0 and m > 0:
for p in partitions_gen(n-m, m):
yield Link(m, p)
yield from partitions_gen(n, m-1)The partitions_gen function is both shorter and more efficient. Even when all partitions are needed, the generator function is more efficient because it does not copy the contents of shorter lists into longer lists (which is done in partitions using the expression with_m + without_m). However, the main efficiency advantage arises when only a subset of the partitions are needed. Instead of creating every possible partition, partitions_gen only creates the partitions needed.
Efficiency Comparison. Printing just the first 10 items in partitions(55, 20) takes about 5 seconds on a typical laptop because it creates a list of all 385,528 partitions and makes 5,475,736 recursive calls to partitions.
>>> for p in partitions(55, 20)[:10]:
print(p)
(20 20 15)
(20 20 14 1)
(20 20 13 2)
(20 20 13 1 1)
(20 20 12 3)
(20 20 12 2 1)
(20 20 12 1 1 1)
(20 20 11 4)
(20 20 11 3 1)
(20 20 11 2 2)The same 10 partitions can be printed by calling next 10 times on a generator returned by partitions_gen. This approach takes about 20 microseconds, more than 200,000 times faster. It creates only the 10 partitions of 55 requested and makes only 45 partitions in total (including partitions of smaller numbers) during only 135 recursive calls.
>>> parts = partitions_gen(55, 20)
>>> for _ in range(10):
print(next(parts))
(20 20 15)
(20 20 14 1)
(20 20 13 2)
(20 20 13 1 1)
(20 20 12 3)
(20 20 12 2 1)
(20 20 12 1 1 1)
(20 20 11 4)
(20 20 11 3 1)
(20 20 11 2 2)The table below summarizes the work required to print the first 10 partitions of 55 using parts up to size 20. Partitions created include the partitions of smaller numbers built along the way, counted as the number of Link instances constructed.
partitions | partitions_gen | |
|---|---|---|
| Time | about 5,000,000 microseconds | about 20 microseconds |
| Partitions created | 5,901,019 | 45 |
| Recursive calls | 5,475,736 | 135 |
This speedup grows as n and m grow, and inputs that would run out of memory and take billions of years for partitions run instantly with partitions_gen, as long as only a small number of partitions are requested using next.
>>> parts = partitions_gen(1000, 300)
>>> for _ in range(10):
print(next(parts))
(300 300 300 100)
(300 300 300 99 1)
(300 300 300 98 2)
(300 300 300 98 1 1)
(300 300 300 97 3)
(300 300 300 97 2 1)
(300 300 300 97 1 1 1)
(300 300 300 96 4)
(300 300 300 96 3 1)
(300 300 300 96 2 2)By contrast, partitions(1000, 300) would construct a list of all partitions of 1000 using parts up to size 300, creating about partitions in total during about recursive calls. Even with unlimited memory, at the rate measured above of about 1 microsecond per recursive call, that computation would take about years, which is billions of times longer than the age of the universe.