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_othermust be lazy: it should take an item fromtonly when a caller asks the returned iterator for an item that requires it. Callingevery_other(t)shouldn't take any items fromtat all. Python'szip,filter, andmapare 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_otherHint
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_indexQ3: 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
increasingfinds an item that is not larger than the item before it, it should returnFalsewithout taking any more items fromt. The examples check this by callingnext(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 increasingQ4: 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
nitems fromt, so that any items after those remain int. The examples check this by callingnext(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_nSubmit
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.