CS61A: Generators

Generators

• A special form of an iterator that is returned from a generator function. The generator object iterates over all yielded values of a function.
  • In the generator funtion, we use the yield keyword to return subsequent values.
  • We may peruse through the generator using similar techniques to the iterator, such as next()
• Calling if a return statement is called, the generator would pre-emptively stop yielding new values.
• Ex:

def plus_minus(x):
    yield x
    yield -x
    return 1

plus_minus_4 = plus_minus(4)
print(type(plus_minus_4))
print(next(plus_minus_4))
print(next(plus_minus_4))

<class 'generator'>
4
-4

• A generator function is a function that yields values instead of returning them
• A normal function returns a value just once; a generator function can yield multiple times
• A generator is an iterator crated automatically by calling a generator function
• When a generator function is called, it returns a generator that iterates over its yields

def evens(start, end):
    even = start + (start % 2)
    while even < end:
        yield even
        even += 2

t = evens(2, 10)
print(type(t))
print(next(t))
print(next(t))
print(next(t))
print(next(t))

<class 'generator'>
2
4
6
8





range

• The body of a generator function is not executed until the next function is called on the generator object.
  • Execution of the function body pauses at the yield statement.
  • The generator still remembers all of the environment of the function execution.
• Generators enable us to customize the computation for each element in the iterator

Generators and Iterators

• Generators return generators but also process iterators

The yield from statement

• A generator may yield all values from an iterator using the yield from statement
• Ex: Write a generator to combine two lists

def a_then_b(a ,b):
    yield from a
    yield from b

list(a_then_b([1,2], [3,4]))

[1, 2, 3, 4]

• The yield from statement may also be used to retrieve all values generated by a generator
• Ex: Write a generator for a reversed, consecutive sequence of numbers

def countdown(k):
    if k > 0:
        yield k
        yield from countdown(k-1)
    else:
        yield 'Blast off!'

list(countdown(5))

[5, 4, 3, 2, 1, 'Blast off!']

• Ex: Write generators that obtains all prefixes of a word, and also another generator that includes all substrings of a word

def prefixes(s):
    if s:
        yield s
        yield from prefixes(s[:-1])

def substrings(s):
    if s:
        yield from prefixes(s)
        yield from substrings(s[1:])

print("prefixes of 'stop'", list(prefixes('stop')))
print("substrings of 'stop'", list(substrings('stop')))

prefixes of 'stop' ['stop', 'sto', 'st', 's']
substrings of 'stop' ['stop', 'sto', 'st', 's', 'top', 'to', 't', 'op', 'o', 'p']

Ex: Partitions

• A partition of positive integer n, using parts up to size m, is a way in which n can be expressed as the sum of positive integer parts up to m in increasing integer

def list_partitions(n, m):
    if n < 0 or m == 0:
        return []
    else:
        exact_matches = []
        if m == n:
            exact_matches = [str(m)]
        with_m = [str(m) + " + " + p for p in list_partitions(n-m,m)]
        without_m = list_partitions(n, m-1)
        return exact_matches + with_m + without_m
    
list_partitions(6, 4)

['4 + 2',
 '4 + 1 + 1',
 '3 + 3',
 '3 + 2 + 1',
 '3 + 1 + 1 + 1',
 '2 + 2 + 2',
 '2 + 2 + 1 + 1',
 '2 + 1 + 1 + 1 + 1',
 '1 + 1 + 1 + 1 + 1 + 1']

• We may reimplement this using yield statements

def partitions(n, m):
    if n > 0 and m > 0:
        if m == n:
            yield str(m)
        for methods in partitions(n-m, m):
            yield str(m) + " + " + methods
        yield from partitions(n, m-1)
    
list(partitions(6, 4))

['4 + 2',
 '4 + 1 + 1',
 '3 + 3',
 '3 + 2 + 1',
 '3 + 1 + 1 + 1',
 '2 + 2 + 2',
 '2 + 2 + 1 + 1',
 '2 + 1 + 1 + 1 + 1',
 '1 + 1 + 1 + 1 + 1 + 1']

## Problem: Recursive Generators for Sequences

### Task
Implement a generator function `fibonacci(n)` that yields the first `n` numbers in the Fibonacci sequence. The Fibonacci sequence is defined as follows:
- The first two numbers are 0 and 1.
- Each subsequent number is the sum of the previous two numbers.

### Example
```python
list(fibonacci(6))  # Output: [0, 1, 1, 2, 3, 5]

Requirements

• Use recursion to implement the generator.
• Do not use any loops (for, while, etc.).
• The generator should yield each Fibonacci number one by one.

Hints

• You may define a helper function within fibonacci(n) to handle the recursion.
• Remember to use the yield keyword to produce values from the generator. ```

# Rewrite this so that the generator yields in reverse order
def fibonacci(n):
    if n == 1:
        yield 0
    if n == 2:
        yield 1
        yield 0
    else:
        yield next(fibonacci(n-1)) + next(fibonacci(n-2))
        yield from fibonacci(n-1)

def fibonacci(n):
    def fib_helper(a, b, count):
        if count > 0:
            yield a
            yield from fib_helper(b, a + b, count - 1)
            

    return fib_helper(0, 1, n)
        
    
list(fibonacci(10))

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

import inspect
inspect.getmro(type(fibonacci(10)))

(generator, object)

def fib_generator():
    a, b=  0, 1
    while True:
        yield a
        a, b = b, a+b
    

t = fib_generator()

for i in range(10):
    print(next(t))

0
1
1
2
3
5
8
13
21
34