Iteration
Table of Contents
1. Iterators
A container can provide an iterator that provides access to its elements in some order. Iterators are mutable values. The function iter(<iterable>) returns an iterator over the elements of an iterable value (such as any sequence), and the function next(<iterator>) returns the next element in an iterator. For example:
s = [3, 4, 5]
t = iter(s)
first = next(t) # 3
second = next(t) # 4
When the iterator reaches the end of the sequence, it throws a Stopiteration error.
An iterator is useful because it bundles together a sequence and it position within that sequence as one object. This allows you to retain the position while passing the object around, which is useful for ensuring that each element is processed only once.
1.1. Built-In Functions
Many built-in Python sequence functions return iterators that compute results lazily:
map(<func>, <iterable>) # Iterate over func(x) for x in iterable
filter(<func>, <iterable>) # Iterate over x in iterable if func(x)
zip(<first_iter>, <second_iter>) # Iterate over co-indexed (x, y) pairs
reversed(<sequence>) # Iterate over x in a sequence in reverse order
In particular, the zip() function returns an iterator over co-indexed tuples. In other words, it will take a series of iterables, and return an iterator over tuples in which each tuple contains values from the corresponding index in each iterable. Thus, the first tuple in the iterator, would contain the first element of each iterable, then the second for the second tuple, and so on:
l = list(zip([1, 2], [3, 4])) # [(1, 3), (2, 4)]
If one iterable is longer than the other, zip only iterates over matches and skips any remaining elements.
l = list(zip([1, 2], [3, 4, 5])) # [(1, 3), (2, 4)]
More than two iterables can be passed to zip:
l = list(zip([1, 2], [3, 4, 5], [6, 7])) # [(1, 3, 6), (2, 4, 7)]
To view the contents of an iterator, we can place the resulting elements into a container using functions such as list(), tuple(), or sorted().
1.2. Generators
A generator is a special type of iterator that is returned with a generator function. Instead of returning a value, generator functions use the yield keyword to "yield" values as next() is called on the generator that it returns. Unlike normal functions which can only return one value, generator functions can yield multiple values in succession, like so:
def plus_minus(x):
yield x
yield -x
t = plus_minus(3) # generator
a = next(t) # 3
b = next(t) # -3
We can think of a generator function as pausing execution after each yield, such that it retains its state when it needs to yield the next value. Generators can be useful for lazy evaluation, supporting infinite sequences, and memory efficiency.
Example: List partitions
We want to create a generator function partitions(n, m) that yields all of the unique ways we can partition n using numbers up to and including m using a string:
def partitions(n, m):
if n > 0 and m > 0:
if n == m:
yield str(m)
for p in partitions(n - m, m):
yield p + ' + ' + str(m)
yield from partitions(n, m - 1)
Here, using yield instead of returning all of the partitions at once means we can efficiently find part or just a few of the partitions without having to calculate all of them.
1.2.1. Yielding From Iterators
A generator can also yield directly from another iterator by using the yield from syntax:
def a_then_b(a, b):
yield from a
yield from b
l = list(a_then_b([3, 4], [5, 6])) # [3, 4, 5, 6]
2. while Statements
While statements contain statements that are repeated as long as some condition is true. The following is a while statement:
i, total = 0, 0
while i < 3:
i = i + 1
total = total + i
This loop calculates the total sum of the numbers from 1 through 3.
The Fibonacci sequence
We can write a function using a while loop to find the nth Fibonacci number:
def fib(n):
"""Compute the nth Fibonacci number, for N >= 1."""
pred, curr = 0, 1
k = 1
while k < n:
pred, curr = curr, pred + curr
k = k + 1
return curr
2.1. Procedure for while Statements
- Evaluate the header's expression.
- If it is a true value, execute the whole suite, then return to step 1.
Note that the while condition must eventually become a false value for the statement to end, otherwise you have an infinite loop.
3. for Statements
For statements allows us to iterate over an object that is iterable. For example, a sequence is iterable, so if we have a list, we can iterate over that list using a for loop. In general, a for statement is written like so:
for <name> in <expression>:
<suite>
3.1. Procedure for for Statements
- Evaluate the header's expression, which must yield an iterable value.
- For each element in that sequence, bind
<name>to that element in the current frame, and then execute the suite.
3.2. Sequence Unpacking
We can also do sequence unpacking in for statements. If we have a sequence of fixed-length sequences, then we can give a name for each element in a fixed-length sequence, similar to the syntax of multiple assignment:
pairs = [[1, 2], [2, 2], [3, 2], [4, 4]]
for x, y in pairs:
print(x, y)
3.3. Ranges
Since ranges are an iterable value, we can iterate over ranges in a for loop. This is especially helpful for controlling the number of times we iterate, or when we don't care what the element is. When we don't need to bind a name to an element, we can use the underscore _ to make our code more readable by telling other programmers that the name will not be used:
for _ in range(3):
print("Go Bears!")
3.4. Iterators
We can also use iterators in a for statement. However, it is important to note that the for statement will advance the iterator, which means you cannot use values that were already processed again.