Homework 8: Iterators

  • Due: Monday 11/30 @ 11:59pm
  • Points: 1
  • Download: hw08.zip

To receive credit, you must solve each problem and then complete a short checkoff interview about your solution. You may use Preceptor for the interview or come to office hours to be interviewed by a member of the course staff. If the interviews are not working, please still submit your working code on time or request an extension by the deadline. Staff will be doing in-person checkoffs for up to 3 business days after the assignment deadline (including any approved extension). If a checkoff happens more than 3 business days after the regular deadline, staff may ask to confirm your extended deadline via Flextensions. You will submit a Provenance bundle that includes a record of how you used VS Code, including interactions with Preceptor. Please do not use AI tools other than Preceptor for this assignment.

Readings: This homework relies on the following reading from Composing Programs:

Required Questions

Q1: Every Other

Implement every_other, which takes an iterator t and returns an iterator over every other item of t: the items at indices 0, 2, 4, and so on.

To find out the index of each item, zip t with count(). The count function from Python's itertools module (already imported for you) takes no arguments and returns an iterator over the integers 0, 1, 2, 3, ... that never runs out. So zip(count(), t) is an iterator over (index, item) pairs, one for each item of t:

>>> pairs = zip(count(), iter(['a', 'b', 'c']))
>>> next(pairs)
(0, 'a')
>>> next(pairs)
(1, 'b')

Then keep only the pairs with even indices, and turn each pair back into its item.

Important: every_other must be lazy: it should take an item from t only when a caller asks the returned iterator for an item that requires it. Calling every_other(t) shouldn't take any items from t at all. Python's zip, filter, and map are lazy in exactly this way, so build your answer from them instead of building a list.

from collections.abc import Iterator  # t: Iterator[int] means t is an iterator that yields integers
from itertools import count


def every_other(t: Iterator[int]) -> Iterator[int]:
    """Return an iterator over the items of t at even indices: the first,
    third, fifth, ... items.

    >>> def noisy(x):  # Print each item as it is taken from t
    ...     print('took', x)
    ...     return x
    >>> t = map(noisy, [10, 11, 12, 13, 14, 15])
    >>> s = every_other(t)  # Nothing is taken from t yet
    >>> next(s)             # Only 10 is taken from t
    took 10
    10
    >>> next(s)             # 11 and 12 are taken from t
    took 11
    took 12
    12
    >>> next(t)             # 13 has not been taken by every_other
    took 13
    13
    >>> list(every_other(iter([5, 6, 7, 8, 9])))
    [5, 7, 9]
    >>> list(every_other(iter([1, 2, 3, 4])))
    [1, 3]
    >>> list(every_other(iter([])))
    []
    """
    indexed = zip(count(), t)
python3 -m pytest -k every_other
Hint

filter(lambda pair: ____, pairs) keeps the pairs for which the lambda returns a true value, and map(lambda pair: ____, ...) turns each pair into something else. For a pair (i, x), pair[0] is i and pair[1] is x.

Q2: Filter by Index

Implement filter_by_index, which takes a one-argument function f and an iterator t. It returns an iterator over every item of t for which f(i) is a true value, where i is the index of that item in t (starting with 0). For example, filter_by_index(lambda i: i % 2 == 0, t) is an iterator over the same items as every_other(t) from the previous question.

Like every_other, filter_by_index must be lazy: it should take an item from t only when a caller asks the returned iterator for an item that requires it.

from collections.abc import Iterator  # t: Iterator[int] means t is an iterator that yields integers
from itertools import count


def filter_by_index(f, t: Iterator[int]) -> Iterator[int]:
    """Return an iterator over each item of t for which f(i) is a true value,
    where i is the index of that item in t (starting with 0).

    >>> def noisy(x):  # Print each item as it is taken from t
    ...     print('took', x)
    ...     return x
    >>> t = map(noisy, [20, 21, 22, 23, 24, 25])
    >>> s = filter_by_index(lambda i: i == 1 or i == 2, t)  # Nothing is taken from t yet
    >>> next(s)
    took 20
    took 21
    21
    >>> next(s)
    took 22
    22
    >>> next(t)  # 23 has not been taken by filter_by_index
    took 23
    23
    >>> t = iter([10, 11, 12, 13, 14, 15, 16])
    >>> list(filter_by_index(lambda i: i % 3 == 0, t))  # Indices 0, 3, and 6
    [10, 13, 16]
    >>> list(filter_by_index(lambda i: i > 2, iter([5, 4, 3, 2, 1])))
    [2, 1]
    >>> list(filter_by_index(lambda i: False, iter([1, 2, 3])))
    []
    >>> squares = map(lambda x: x * x, iter(range(10)))
    >>> list(filter_by_index(lambda i: i in [2, 3, 5, 7], squares))
    [4, 9, 25, 49]
    """
    return ____
python3 -m pytest -k filter_by_index

Q3: Increasing

Implement increasing, which takes an iterator t over integers. It returns whether each item in t after the first is larger than the item just before it. If t has zero or one items, increasing returns True.

Important: As soon as increasing finds an item that is not larger than the item before it, it should return False without taking any more items from t. The examples check this by calling next(t) afterward.

from collections.abc import Iterator  # t: Iterator[int] means t is an iterator that yields integers


def increasing(t: Iterator[int]) -> bool:
    """Return whether each item in t after the first is larger than the item
    before it.

    >>> increasing(iter([1, 3, 4, 8]))
    True
    >>> increasing(iter([1, 3, 3, 8]))  # 3 is not larger than 3
    False
    >>> increasing(iter([5, 4]))
    False
    >>> increasing(iter([7]))
    True
    >>> increasing(iter([]))
    True
    >>> t = iter([2, 5, 9, 6, 7, 8])
    >>> increasing(t)  # Stops as soon as it reaches 6, which is not larger than 9
    False
    >>> next(t)        # 7 has not been taken by increasing
    7
    >>> s = map(lambda x: x % 5, range(20))  # 0, 1, 2, 3, 4, 0, 1, 2, ...
    >>> increasing(s)  # Stops as soon as it reaches the second 0
    False
    >>> next(s)
    1
    """
    "*** YOUR CODE HERE ***"
python3 -m pytest -k increasing

Q4: Map Up to N

Implement map_up_to_n, which takes a one-argument function f, an iterator t, and a positive integer n. It returns a list of f(x) for up to n items x from t. If t has fewer than n items, it returns a list of f(x) for all of them.

Important: Take at most n items from t, so that any items after those remain in t. The examples check this by calling next(t) afterward.

from collections.abc import Iterator  # t: Iterator[int] means t is an iterator that yields integers


def map_up_to_n(f, t: Iterator[int], n: int) -> list:
    """Return a list of f(x) for up to n items x from t: the next n items of t,
    or all the rest of them if t has fewer than n items left.

    >>> t = iter([1, 2, 3, 4, 5, 6])
    >>> map_up_to_n(lambda x: x * x, t, 3)
    [1, 4, 9]
    >>> next(t)  # 4 has not been taken by map_up_to_n
    4
    >>> map_up_to_n(lambda x: x * x, t, 5)  # Only 5 and 6 are left in t
    [25, 36]
    >>> map_up_to_n(abs, iter([-1, -2]), 1)
    [1]
    >>> map_up_to_n(lambda x: x + 1, iter(range(10, 20)), 4)
    [11, 12, 13, 14]
    >>> def noisy(x):
    ...     print('took', x)
    ...     return x
    >>> t = map(noisy, [7, 8, 9, 10])
    >>> map_up_to_n(lambda x: -x, t, 2)
    took 7
    took 8
    [-7, -8]
    >>> map_up_to_n(lambda x: -x, t, 1)
    took 9
    [-9]
    >>> next(t)  # 10 has not been taken by map_up_to_n
    took 10
    10
    """
    "*** YOUR CODE HERE ***"
python3 -m pytest -k map_up_to_n

Submit

Run Provenance: Prepare Submission Bundle from the VS Code command palette to create your submission zip, and upload that zip to Gradescope. For a refresher on how to do this, refer to Lab 00.


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