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, and zip return 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 --unlock
Unlocking 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 next on t exactly n times. If you need to iterate through more than n items, 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_occurrences

Q3: 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 next on t only the minimum number of times required. If you are receiving a StopIteration exception, your repeated function is calling next too 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 repeated

Submit 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.


Back to Top

Accessibility Nondiscrimination

Copyright ©2026, Regents of the University of California and respective authors.

This site is built following the Berkeley Class Site template, which is generously based on the Just the Class, and Just the Docs templates.

View all course offerings