Discussion 11: Iterators
Attendance
Your TA will come around during discussion to check you in. You can start on the worksheet before being checked in; you don't need to wait for your TA to get started.
If you didn't attend for a good reason (such as being sick), fill out this form (within 2 weeks of your discussion): attendance form
Getting Started
Everybody say your name, and then figure out who is planning to travel outside of the Bay Area the soonest. Feel free to discuss your travel plans.
Iterators
An iterable is any value that can be iterated through, or gone through one
item at a time. One construct that we've used to iterate through an iterable
is a for statement:
for item in iterable:
# do something
In general, an iterable is an object on which calling the built-in iter
function returns an iterator. An iterator is an object on which calling
the built-in next function returns the next value.
For example, a list is an iterable value.
>>> s = [1, 2, 3, 4]
>>> next(s) # s is iterable, but not an iterator
TypeError: 'list' object is not an iterator
>>> t = iter(s) # Creates an iterator
>>> t
<list_iterator object ...>
>>> next(t) # Calling next on an iterator
1
>>> next(t) # Calling next on the same iterator
2
>>> next(iter(t)) # Calling iter on an iterator returns itself
3
>>> t2 = iter(s)
>>> next(t2) # Second iterator starts at the beginning of s
1
>>> next(t) # First iterator is unaffected by second iterator
4
>>> next(t) # No items left!
StopIteration
>>> s # Original iterable is unaffected
[1, 2, 3, 4]
You can also use an iterator in a for statement because all iterators are
iterable. But note that since iterators keep their state, they're only good to
iterate through an iterable once:
>>> t = iter([4, 3, 2, 1])
>>> for i in t:
... print(i)
4
3
2
1
>>> for i in t:
... print(i)
There are built-in functions that return iterators. These built-in Python sequence operations are said to compute results lazily.
>>> m = map(lambda x: x * x, [3, 4, 5])
>>> next(m)
9
>>> next(m)
16
>>> f = filter(lambda x: x > 3, [3, 4, 5])
>>> next(f)
4
>>> next(f)
5
>>> z = zip([30, 40, 50], [3, 4, 5])
>>> next(z)
(30, 3)
>>> next(z)
(40, 4)
Here are the iterator functions we use in this course:
| Function | Returns |
|---|---|
iter(iterable) |
An iterator over the items of iterable |
next(iterator) |
The next item in iterator |
map(func, iterable) |
An iterator over func(x) for each x in iterable |
filter(func, iterable) |
An iterator over each x in iterable for which func(x) is true |
zip(first, second) |
An iterator over co-indexed (x, y) pairs from first and second |
reversed(sequence) |
An iterator over the items of sequence in reverse order |
To view the contents of an iterator, place its items into a container with
list, tuple, or sorted.
>>> list(map(lambda x: x * x, [3, 4, 5]))
[9, 16, 25]
>>> tuple(reversed([3, 4, 5]))
(5, 4, 3)
>>> sorted(filter(lambda x: x != 4, [5, 4, 3]))
[3, 5]
Lazy or Eager?
Calling map doesn't call the function it's given. Instead, it returns an
iterator that calls the function on one item each time next is called. Here's
a function that prints a line each time it's called, so that you can see when
that happens (from Section 2.8
of Composing Programs):
>>> def double_and_print(x):
... print('***', x, '=>', 2 * x, '***')
... return 2 * x
>>> s = [3, 4, 5, 6]
>>> doubled = map(double_and_print, s)
>>> evens = filter(lambda y: y % 4 == 0, doubled)
>>> next(evens)
>>> list(doubled)
>>> list(evens)
As a group, predict what Python displays after each of the last three lines.
Then, discuss: what would be different if doubled were defined as the list
[double_and_print(x) for x in s] instead?
Questions
Q1: Half Evens
Implement half_evens, which takes an iterator t over integers and returns an
iterator over each even item of t divided by 2 (using //). Use map and
filter so that no items of t are used until items of the result are needed.
def half_evens(t):
"""Return an iterator over each even item of t divided by 2.
>>> list(half_evens(iter([1, 2, 3, 4, 5, 6])))
[1, 2, 3]
>>> list(half_evens(iter([7, 10, 0, -4, 9])))
[5, 0, -2]
>>> t = iter([3, 8, 5, 1, 12, 4])
>>> h = half_evens(t)
>>> next(h) # Uses 3 and 8 from t
4
>>> next(t) # 5 is still in t
5
>>> list(h)
[6, 2]
"""
Hint 1: Template (at the end)
Q2: Print Sums
Definition: The ith cumulative sum of a sequence s of numbers is the
sum of the first i items in s, starting with i of 1. For example, the
cumulative sums of [1, 2, 3, 4] are 1, 3, 6, and 10.
Implement print_sums, which takes an iterator t over integers and a
positive integer k. It prints the cumulative sums of the first k items of
t, one per line. If t has fewer than k items, it prints the cumulative
sums of all of them.
Important: Take at most
kitems fromt: stop as soon as you've printedkcumulative sums. The examples check this by callingnext(t)afterward.
def print_sums(t, k: int) -> None:
"""Print the cumulative sums of the first k items of t, or of all of its
items if t has fewer than k.
>>> t = iter([1, 2, 3, 4, 5])
>>> print_sums(t, 3) # 1, 1 + 2, 1 + 2 + 3
1
3
6
>>> next(t) # 3 was the last item taken from t
4
>>> print_sums(t, 1)
5
>>> print_sums(iter([4, 5]), 10) # t runs out after 2 items
4
9
>>> print_sums(map(lambda x: x * x, range(1, 1000000000)), 4) # 1, 4, 9, 16
1
5
14
30
"""
Hint 2: Template (at the end)
Q3: Take While
Implement take_while, which takes an iterator t and a one-argument function
f. It returns a list of the items at the front of t for which f returns a
true value, stopping at the first item for which f returns a false value.
That item is not included in the list. If t runs out of items first,
take_while returns all of them.
def take_while(t, f) -> list[int]:
"""Return a list of the items at the front of t for which f returns a true
value, stopping at (and consuming) the first item for which it doesn't.
>>> t = iter([2, 4, 6, 7, 8, 9])
>>> take_while(t, lambda x: x % 2 == 0)
[2, 4, 6]
>>> next(t) # 7 was consumed by take_while
8
>>> take_while(t, lambda x: x > 10) # 9 is consumed
[]
>>> list(t)
[]
>>> take_while(iter([1, 2, 3]), lambda x: x < 10) # t runs out
[1, 2, 3]
>>> squares = map(lambda x: x * x, range(1, 1000000000))
>>> take_while(squares, lambda x: x < 50)
[1, 4, 9, 16, 25, 36, 49]
>>> next(squares)
81
"""
Hint 3: Template (at the end)
Q4: Only Up
This is adapted from Question 2(b) on the Spring 2024 61A Final.
Definition: The increasing sublist of a sequence of numbers s is a list
containing each element of s that is larger than all previous elements. For
example, the increasing sublist of [3, 1, 2, 5, 4, 5, 7, 6, 12, 11] is [3, 5, 7, 12].
Implement upiter, which takes a finite iterator over numbers t and
returns its increasing sublist.
The for statement in the skeleton never gets past its first item, since the body of the for statement returns.
Discuss: what does for x in t: do if t has no items left? Why is that useful?
def upiter(t) -> list[int]:
"""Return the increasing sublist of iterator t.
>>> upiter(iter([3, 1, 2, 5, 4, 5, 7, 6, 12, 11]))
[3, 5, 7, 12]
>>> upiter(iter([5, 4, 3]))
[5]
>>> upiter(iter([]))
[]
>>> upiter(map(abs, [-1, 2, -3, 3, -4]))
[1, 2, 3, 4]
"""
for x in t:
return ____ + ____(filter(____, t))
____
Hint 4: Template (at the end)
Hints
Hint 1: Template
First filter the even items of t, then map a function over the result
that divides each one by 2.
def half_evens(t):
return map(____, filter(____, t))
Hint 2: Template
Use for x in t: to go through the items of t, and keep count of how many
you've used and the total so far.
def print_sums(t, k):
total, count = 0, 0
for x in t:
total, count = ____, ____
print(total)
if ____:
return
Hint 3: Template
A for statement calls next repeatedly and stops when the iterator runs out
of items. You can return from inside a for statement as soon as you find the
item that stops the list.
def take_while(t, f):
result = []
for x in t:
if ____:
return result
____
return result
Hint 4: Template
The first item x of t is always in the increasing sublist. The rest of the
increasing sublist is the increasing sublist of the remaining items of t that
are larger than x. Calling filter on t returns an iterator over just those
items without computing any of them yet.
def upiter(t):
for x in t:
return [_____] + upiter(filter(lambda y: _____, t))
return []