Discussion 7: Generators🖨️

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

If you get stuck, there are walkthrough videos (@berkeley.edu login to YouTube required).

Getting Started

Say your name and share a favorite place on the Berkeley campus or surrounding city that you've discovered. Try to pick a place that others might not have been yet. (But if the room you're in now is your favorite place on campus, that's ok too.)

Hint

McCone Hall has a nice view from the 5th floor balcony.

This emoticon of a guy in a cowboy hat is valid Python: o[:-D]

>>> o = [2, 0, 2, 6]
>>> [ o[:-D] for D in range(1, 4) ]
[[2, 0, 2], [2, 0], [2]]

🤠

Generators

A generator is an iterator that is returned by calling a generator function, which is a function that contains yield statements instead of return statements. The ways to use an iterator are to call next on it or to use it as an iterable (for example, in a for statement).

Q1: Big Fib

The generator function gen_fib (in the code below) yields all of the Fibonacci numbers.

Explain the following expression to each other so that everyone understands how it works. (It creates a list of the first 10 Fibonacci numbers.)

(lambda t: [next(t) for _ in range(10)])(gen_fib())

Then, complete the return expression of big_fib below by writing only names and parentheses in the blanks so that it evaluates to the smallest Fibonacci number that is larger than 2026.

Talk with each other about what built-in functions might be helpful, such as map, filter, list, any, all, etc. (Click on these function names to view their documentation.) Try to figure out the answer without using Python. Only run the code when your group agrees that the answer is right. This is not the time for guess-and-check.

def gen_fib() -> Iterator[int]:
    n, add = 0, 1
    while True:
        yield n
        n, add = n + add, n


def big_fib() -> int:
    """Return the smallest Fibonacci number that is larger than 2026.

    >>> big_fib()
    2584
    """
    return next(____(lambda n: n > 2026, ____))

Hint

One solution has the form: next(____(lambda n: n > 2026, ____)) where the first blank uses a built-in function to create an iterator over just large numbers and the second blank creates an iterator over all Fibonacci numbers.

Q2: Something Different

Implement differences, a generator function that takes t, a non-empty iterator over numbers. It yields the differences between each pair of adjacent values from t. If t iterates over a positive finite number of values n, then differences should yield n-1 times.

def differences(t: Iterator[int]) -> Iterator[int]:
    """Yield the differences between adjacent values from iterator t.

    >>> list(differences(iter([5, 2, -100, 103])))
    [-3, -102, 203]
    >>> next(differences(iter([39, 100])))
    61
    """
    "*** YOUR CODE HERE ***"

Hint

Add to the following implementation by initializing and updating previous_x so that it is always bound to the value of t that came before x.

for x in t:
    yield x - previous_x

Discussion Time. Work together to explain why differences will always yield n-1 times for an iterator t over n values. If you get stuck, ask a TA for help.

Intermission

We're lazy (like an iterator) and used ChatGPT to generate a generator joke...

Why did the Python function become a chef?

Because it was skilled at knowing when to "return" to the recipe and when to "yield" to improvisation!

Recursive Generators

Tree reminder

A Tree has a label and a list of branches, each of which is a Tree.

@dataclass
class Tree[T]:
    label: T
    branches: list[Tree[T]] = field(default_factory=list)  # branches defaults to []

Q3: Yield Paths

Define a generator function yield_paths which takes in a tree t and a value value, and yields each path from the root of t to a node that has a label equal to value. Each path should be returned as a list of labels from the root to that matching node.

The paths may be yielded in any order.

def yield_paths[T](t: Tree[T], value: T) -> Iterator[list[T]]:
    """Yield all possible paths from the root of t to a node with the label
    value as a list.

    >>> t = Tree(1, [Tree(2, [Tree(3), Tree(4, [Tree(6)]), Tree(5)]), Tree(5)])
    >>> print(t)
    1
      2
        3
        4
          6
        5
      5
    >>> next(yield_paths(t, 6))
    [1, 2, 4, 6]
    >>> path_to_5 = yield_paths(t, 5)
    >>> sorted(list(path_to_5))
    [[1, 2, 5], [1, 5]]

    >>> u = Tree(0, [Tree(2, [t])])
    >>> print(u)
    0
      2
        1
          2
            3
            4
              6
            5
          5
    >>> path_to_2 = yield_paths(u, 2)
    >>> sorted(list(path_to_2))
    [[0, 2], [0, 2, 1, 2]]
    """
    if t.label == value:
        yield ____
    for b in t.branches:
        for ____ in ____:
            yield ____

Q4: Stair Ways

Imagine that you want to go up a staircase that has n steps, where n is a positive integer. You can take either one or two steps each time you move.

Write a generator function stair_ways that yields all the different ways you can climb the staircase. Each "way" of climbing a staircase can be represented by a list of 1s and 2s, where each number indicates whether you take one step or two steps at a time.

For example, for a staircase with 3 steps, there are three ways to climb it:

You can take one step each time: [1, 1, 1].
You can take two steps then one step: [2, 1].
You can take one step then two steps: [1, 2].

Therefore, stair_ways(3) should yield [1, 1, 1], [2, 1], and [1, 2]. These can be yielded in any order.

Hint: Think about the problem recursively. If you're on some step n, which steps could you have just been on?

def stair_ways(n: int) -> Iterator[list[int]]:
    """Yield all the ways to climb a set of n stairs taking
    1 or 2 steps at a time.

    >>> list(stair_ways(0))
    [[]]
    >>> s_w = stair_ways(4)
    >>> sorted([next(s_w) for _ in range(5)])
    [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]]
    >>> list(s_w) # Ensure you're not yielding extra
    []
    """
    "*** YOUR CODE HERE ***"