Lab 11: Iterators
- Due: Friday 11/20 @ 11:59pm
- Points: 1
- Download: lab11.zip
Attendance
You need to submit the lab problems in addition to attending to get credit for lab. Students in mega lab only need to submit the lab problems. Preceptor interviews are highly recommended but not required for lab submissions.
If you are in regular lab, your TA will come around during lab to check you in. If you didn't attend for a good reason (such as being sick), fill out this form (within 2 weeks of your lab): attendance form.
Readings: This lab relies on the following reading from Composing Programs:
Required Questions
Iterators
Consult the drop-down if you need a refresher on iterators.
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]
Q1: WWPD: Iterators
Important: Python's built-in functions
map,filter, andzipreturn iterators, not lists.
Predict what Python will display when the following lines are entered into an
interactive session, then unlock the test to check your answers. Type ERROR
if it errors (including a StopIteration error):
python3 -m pytest -k iterators_wwpd --unlockUnlocking Examples
>>> s = [1, 2, 3, 4]
>>> t = iter(s)
>>> next(s)
______
>>> next(t)
______
>>> next(t)
______
>>> next(iter(s))
______
>>> next(iter(s))
______
>>> u = t
>>> next(u)
______
>>> next(t)
______
>>> r = range(6)
>>> r_iter = iter(r)
>>> next(r_iter)
______
>>> [x + 1 for x in r]
______
>>> [x + 1 for x in r_iter]
______
>>> next(r_iter)
______
>>> map_iter = map(lambda x : x + 10, range(5))
>>> next(map_iter)
______
>>> next(map_iter)
______
>>> list(map_iter)
______
>>> for e in filter(lambda x : x % 4 == 0, range(1000, 1008)):
... print(e)
______
______
>>> [x + y for x, y in zip([1, 2, 3], [4, 5, 6])]
______
Q2: Count Occurrences
Implement count_occurrences, which takes an iterator t, an integer n, and
a value x. It returns the number of items in the first n items of t
that are equal to x.
You can assume that t has at least n items.
Important: You should call
nextontexactlyntimes. If you need to iterate through more thannitems, think about how you can optimize your solution.
from collections.abc import Iterator # t: Iterator[int] means t is an iterator that yields integers
def count_occurrences(t: Iterator[int], n: int, x: int) -> int:
"""Return the number of times that x is equal to one of the
first n items of iterator t.
>>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
>>> count_occurrences(s, 10, 9)
3
>>> t = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
>>> count_occurrences(t, 3, 10)
2
>>> u = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
>>> count_occurrences(u, 1, 3) # Only iterate over 3
1
>>> count_occurrences(u, 3, 2) # Only iterate over 2, 2, 2
3
>>> list(u) # Ensure that the iterator has advanced the right amount
[1, 2, 1, 4, 4, 5, 5, 5]
>>> v = iter([4, 1, 6, 6, 7, 7, 6, 6, 2, 2, 2, 5])
>>> count_occurrences(v, 6, 6)
2
"""
"*** YOUR CODE HERE ***"
python3 -m pytest -k count_occurrencesQ3: Repeated
Implement repeated, which takes in an iterator t and an integer k greater
than 1. It returns the first value in t that appears k times in a row. You
may assume that there is an item of t repeated at least k times in a row.
Important: Call
nextontonly the minimum number of times required. If you are receiving aStopIterationexception, yourrepeatedfunction is callingnexttoo many times.
from collections.abc import Iterator # t: Iterator[int] means t is an iterator that yields integers
def repeated(t: Iterator[int], k: int) -> int:
"""Return the first value in iterator t that appears k times in a row,
calling next on t as few times as possible.
>>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
>>> repeated(s, 2)
9
>>> t = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
>>> repeated(t, 3)
8
>>> u = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
>>> repeated(u, 3)
2
>>> repeated(u, 3)
5
>>> v = iter([4, 1, 6, 6, 7, 7, 8, 8, 2, 2, 2, 5])
>>> repeated(v, 3)
2
"""
assert k > 1
"*** YOUR CODE HERE ***"
python3 -m pytest -k repeatedSubmit Assignment
Submit this assignment by running Provenance: Prepare Submission Bundle from the VS Code command palette and uploading the resulting zip to Gradescope. The zip already contains the files you've edited. Lab 00 has detailed instructions.
Your responses to WWPD questions are not submitted, and they do not need to be. Lab credit is based on the code writing questions.