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 k items from t: stop as soon as you've printed k cumulative sums. The examples check this by calling next(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 []