Discussion 6: Generators

Switch to Pensieve:

  • Everyone: Go to pensieve.co, log in with your @berkeley.edu email, and enter your group number (which was in the email that assigned you to this lab).

Once you're on Pensieve, you don't need to return to this page; Pensieve has all the same content (but more features). If for some reason Penseive doesn't work, return to this page and continue with the discussion.

Getting Started

To get help from a TA, If you do not have an in-person TA, you can reach your TA using this Zoom link.

If there are fewer than 3 people in your group, feel free to merge your group with another group in the room.

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

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

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

This generator function yields all of the Fibonacci numbers.

def gen_fib():
    n, add = 0, 1
    while True:
        yield n
        n, add = n + add, n

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 expression below by writing only names and parentheses in the blanks so that it evaluates to the smallest Fibonacci number that is larger than 2024.

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.

Your Answer
Run in 61A Code
Solution 
def gen_fib():
    n, add = 0, 1
    while True:
        yield n
        n, add = n + add, n

next(filter(lambda n: n > 2024, gen_fib()))

One solution has the form: next(____(lambda n: n > 2024, ____)) 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.

Your Answer
Run in 61A Code
Solution 
def differences(t):
    """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
    """
    last_x = next(t)
    for x in t:
        yield x - last_x
        last_x = x

Presentation Time. Work together to explain why differences will always yield n-1 times for an iterator t over n values. Pick someone who hasn't presented to the course staff recently to share your group's answer with your TA (in person or on Zoom).

Intermission

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

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

Switch roles: Whoever in your group helped type the answer to the last question should not type the answer to the next one. Instead, just ask questions and give suggestions; let other group members type the answer.

Q3: Partitions

Tree-recursive generator functions have a similar structure to regular tree-recursive functions. They are useful for iterating over all possibilities. Instead of building a list of results and returning it, just yield each result.

You'll need to identify a recursive decomposition: how to express the answer in terms of recursive calls that are simpler. Ask yourself what will be yielded by a recursive call, then how to use those results.

Definition. For positive integers n and m, a partition of n using parts up to size m is an addition expression of positive integers up to m in non-decreasing order that sums to n.

Implement partition_gen, a generator functon that takes positive n and m. It yields the partitions of n using parts up to size m as strings.

Reminder: For the partitions function we studied in lecture (video), the recursive decomposition was to enumerate all ways of partitioning n using at least one m and then to enumerate all ways with no m (only m-1 and lower).

Your Answer
Run in 61A Code
Solution 
def partition_gen(n, m):
    """Yield the partitions of n using parts up to size m.

    >>> for partition in sorted(partition_gen(6, 4)):
    ...     print(partition)
    1 + 1 + 1 + 1 + 1 + 1
    1 + 1 + 1 + 1 + 2
    1 + 1 + 1 + 3
    1 + 1 + 2 + 2
    1 + 1 + 4
    1 + 2 + 3
    2 + 2 + 2
    2 + 4
    3 + 3
    """
    assert n > 0 and m > 0
    if n == m:
        yield str(n)
    if n - m > 0:
        for p in partition_gen(n - m, m):
            yield p + ' + ' + str(m)
    if m > 1:
        yield from partition_gen(n, m-1)
Yield a partition with just one element, n. Make sure you yield a string.
The first recursive case uses at least one m, and so you will need to yield a string that starts with p but also includes m. The second recursive case only uses parts up to size m-1. (You can implement the second case in one line using yield from.)

Discussion Time. Work together to explain why this implementation of partition_gen does not include base cases for n < 0, n == 0, or m == 0 even though the original implementation of partitions from lecture (video) had all three.

Document the Occasion

Please all fill out the attendance form (one submission per person per week).