Lab 24 - Iterators and Generators

Due by 11:59pm on December 4, 2025

Starter Files

Download lab24.zip. Inside the archive, you will find starter files for the questions in this lab.

Topics

Iterators

An iterable is any object that can be iterated through, or gone through one element at a time. One construct that we’ve used to iterate through an iterable is a for loop:

for elem in iterable:
    # do something

for loops work on any object that is iterable. We previously described it as working with any sequence – all sequences are iterable, but there are other objects that are also iterable! We define an iterable as an object on which calling the built-in function iter function returns an iterator. An iterator is another type of object that allows us to iterate through an iterable by keeping track of which element is next in the sequence.

To illustrate this, consider the following block of code, which does the exact same thing as the for statement above:

iterator = iter(iterable) # 1
    try:
        while True:
            elem = next(iterator) # 2
            # do something
    except StopIteration: # 3
        pass

Here’s a breakdown of what’s happening:

  1. First, the built-in iter function is called on the iterable to create a corresponding iterator.
  2. To get the next element in the sequence, the built-in next function is called on this iterator.
  3. When next is called but there are no elements left in the iterator, a StopIteration error is raised. In the for loop construct, this exception is caught and execution can continue.

Calling iter on an iterable multiple times returns a new iterator each time with distinct states (otherwise, you’d never be able to iterate through a iterable more than once). You can also call iter on the iterator itself, which will just return the same iterator without changing its state. However, note that you cannot call next directly on an iterable.

Let’s see the iter and next functions in action with an iterable we’re already familiar with – a list.

>>> lst = [1, 2, 3, 4]
>>> next(lst)             # Calling next on an iterable
TypeError: 'list' object is not an iterator
>>> list_iter = iter(lst) # Creates an iterator for the list
>>> list_iter
<list_iterator object ...>
>>> next(list_iter)       # Calling next on an iterator
1
>>> next(list_iter)       # Calling next on the same iterator
2
>>> next(iter(list_iter)) # Calling iter on an iterator returns itself
3
>>> list_iter2 = iter(lst)
>>> next(list_iter2)      # Second iterator has new state
1
>>> next(list_iter)       # First iterator is unaffected by second iterator
4
>>> next(list_iter)       # No elements left!
StopIteration
>>> lst                   # Original iterable is unaffected
[1, 2, 3, 4]

Since you can call iter on iterators, this tells us that that they are also iterables! Note that while all iterators are iterables, the converse is not true - that is, not all iterables are iterators. You can use iterators wherever you can use iterables, but note that since iterators keep their state, they’re only good to iterate through an iterable once:

>>> list_iter = iter([4, 3, 2, 1])
>>> for e in list_iter:
...     print(e)
4
3
2
1
>>> for e in list_iter:
...     print(e)

Analogy: An iterable is like a book (one can flip through the pages) and an iterator for a book would be a bookmark (saves the position and can locate the next page). Calling iter on a book gives you a new bookmark independent of other bookmarks, but calling iter on a bookmark gives you the bookmark itself, without changing its position at all. Calling next on the bookmark moves it to the next page, but does not change the pages in the book. Calling next on the book wouldn’t make sense semantically. We can also have multiple bookmarks, all independent of each other.

Iterable Uses

We know that lists are one type of built-in iterable objects. You may have also encountered the range(start, end) function, which creates an iterable of ascending integers from start (inclusive) to end (exclusive).

>>> for x in range(2, 6):
...     print(x)
...
2
3
4
5

Ranges are useful for many things, including performing some operations for a particular number of iterations or iterating through the indices of a list.

There are also some built-in functions that take in iterables and return useful results:

  • map(f, iterable) - Creates an iterator over f(x) for x in iterable. In some cases, computing a list of the values in this iterable will give us the same result as [func(x) for x in iterable]. However, it’s important to keep in mind that iterators can potentially have infinite values because they are evaluated lazily, while lists cannot have infinite elements.
  • filter(f, iterable) - Creates an iterator over x for each x in iterable if f(x)
  • zip(iterables*) - Creates an iterator over co-indexed tuples with elements from each of the iterables
  • reversed(iterable) - Creates an iterator over all the elements in the input iterable in reverse order
  • list(iterable) - Creates a list containing all the elements in the input iterable
  • tuple(iterable) - Creates a tuple containing all the elements in the input iterable
  • sorted(iterable) - Creates a sorted list containing all the elements in the input iterable
  • reduce(f, iterable) - Must be imported with functools. Apply function of two arguments f cumulatively to the items of iterable, from left to right, so as to reduce the sequence to a single value.

Generators

We can define custom iterators by writing a generator function, which returns a special type of iterator called a generator.

A generator function must have at least one yield statement and returns a generator object when we call it, without evaluating the body of the generator function itself.

You can think of yield sort of like a return statement, except instead of exiting the function, it just pauses it to give a value, then continues running.

When we first call next on the returned generator, then we will begin evaluating the body of the generator function until an element is yielded or the function otherwise stops (such as if we return). The generator remembers where we stopped, and will continue evaluating from that stopping point on the next time we call next.

As with other iterators, if there are no more elements to be generated, then calling next on the generator will give us a StopIteration.

For example, here’s a generator function:

def countdown(n):
    print("Beginning countdown!")
    while n >= 0:
        yield n
        n -= 1
    print("Blastoff!")

To create a new generator object, we can call the generator function. Each returned generator object from a function call will separately keep track of where it is in terms of evaluating the body of the function. Notice that calling iter on a generator object doesn’t create a new bookmark, but simply returns the existing generator object!

>>> c1, c2 = countdown(2), countdown(2)
>>> c1 is iter(c1)  # a generator is an iterator
True
>>> c1 is c2
False
>>> next(c1)
Beginning countdown!
2
>>> next(c2)
Beginning countdown!
2

In a generator function, we can also have a yield from statement, which will yield each element from an iterator or iterable.

>>> def gen_list(lst):
...     yield from lst
...
>>> g = gen_list([1, 2])
>>> next(g)
1
>>> next(g)
2
>>> next(g)
StopIteration

Required Questions

Q1: What Would Python Do? Iterators

Type the following expressions into the python interpreter and try to predict the output. If you ever get stuck, execute the code and try to find what is happening.

>>> s = [1, 2, 3, 4]
>>> t = iter(s)
>>> next(s)
______
>>> next(t)
______
>>> next(t)
______
>>> iter(s)
______
>>> next(iter(s))
______
>>> next(iter(t))
______
>>> next(iter(s))
______
>>> next(iter(t))
______
>>> next(t)
______
>>> r = range(6)
>>> r_iter = iter(r)
>>> next(r_iter)
______
>>> [x + 1 for x in r]
______
>>> [x + 1 for x in r_iter]
______
>>> next(r_iter)
______
>>> list(range(-2, 4))   # Converts an iterable into a list
______
>>> map_iter = map(lambda x : x + 10, range(5))
>>> next(map_iter)
______
>>> next(map_iter)
______
>>> list(map_iter)
______
>>> for e in filter(lambda x : x % 2 == 0, range(1000, 1008)):
...     print(e)
______
______
______
______
>>> [x + y for x, y in zip([1, 2, 3], [4, 5, 6])]
______

Q2: Count Occurences

Implement count_occurrences, which takes in an iterator t and returns the number of times the value x appears in the first n elements of t. A value appears in a sequence of elements if it is equal to an entry in the sequence.

Note: You can assume that t will have at least n elements.

def count_occurrences(t, n, x):
    """Return the number of times that x appears in the first n elements of iterator t.

    >>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> count_occurrences(s, 10, 9)
    3
    >>> s2 = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> count_occurrences(s2, 3, 10)
    2
    >>> s = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
    >>> count_occurrences(s, 1, 3)
    1
    >>> count_occurrences(s, 4, 2)
    3
    >>> next(s)
    2
    >>> s2 = iter([4, 1, 6, 6, 7, 7, 8, 8, 2, 2, 2, 5])
    >>> count_occurrences(s2, 6, 6)
    2
    """
    """*** YOUR CODE HERE ***"""

Q3: Filter-Gen

Implement a generator function called filter_gen(iterable, fn) that only yields elements of iterable for which fn (a function) returns True.

def filter_gen(iterable, fn):
    """
    >>> is_even = lambda x: x % 2 == 0
    >>> list(filter_gen(range(5), is_even)) # a list of the values yielded from the call to filter_gen
    [0, 2, 4]
    >>> all_odd = (2*y-1 for y in range(5))
    >>> list(filter_gen(all_odd, is_even))
    []
    >>> naturals = (n for n in range(1, 100))
    >>> s = filter_gen(naturals, is_even)
    >>> next(s)
    2
    >>> next(s)
    4
    """
    """*** YOUR CODE HERE ***"""

Q4: Prime Numbers Generator

Create an infinite generator that yields all the prime numbers starting at 2. In other words, whenever next() is called on the returned generator object, it should always yield a prime number. Use the is_prime(n) function at the bottom of the lab24.py file in your prime_numbers_gen.

def prime_numbers_gen():
    """
    >>> gen = prime_numbers_gen()
    >>> next(gen)
    2
    >>> next(gen)
    3
    >>> next(gen)
    5
    >>> next(gen)
    7
    >>> next(gen)
    11
    """
    """*** YOUR CODE HERE ***"""
def is_prime(n):
    if n == 1:
        return False

    for i in range(2, int(n/2)+1):
        if (n % i) == 0:
            return False

    return True

Q5: Merge

Write a generator function merge that takes in two infinite generators a and b that are in increasing order without duplicates and returns a generator that has all the elements of both generators, in increasing order, without duplicates.

def merge(a, b):
    """
    >>> def sequence(start, step):
    ...     while True:
    ...         yield start
    ...         start += step
    >>> a = sequence(2, 3) # 2, 5, 8, 11, 14, ...
    >>> b = sequence(3, 2) # 3, 5, 7, 9, 11, 13, 15, ...
    >>> result = merge(a, b) # 2, 3, 5, 7, 8, 9, 11, 13, 14, 15
    >>> [next(result) for _ in range(10)]
    [2, 3, 5, 7, 8, 9, 11, 13, 14, 15]
    """
    """*** YOUR CODE HERE ***"""

Submit

Once the pytests are all passing, your assignment is complete and ready to submit. Submit your lab24.py file to Gradescope to receive credit. Submissions will be in Canvas.

Extra Practice

Q6: Repeated

Implement repeated, which takes in an iterator t and returns the first value in t that appears k times in a row.

Note: You can assume that the iterator t will have a value that appears at least k times in a row. If you are receiving a StopIteration, your repeated function is likely not identifying the correct value.

Your implementation should iterate through the items in a way such that if the same iterator is passed into repeated twice, it should continue in the second call at the point it left off in the first. An example of this behavior is in the doctests.

def repeated(t, k):
    """Return the first value in iterator T that appears K times in a row.
    Iterate through the items such that if the same iterator is passed into
    the function twice, it continues in the second call at the point it left
    off in the first.

    >>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> repeated(s, 2)
    9
    >>> s2 = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> repeated(s2, 3)
    8
    >>> s = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
    >>> repeated(s, 3)
    2
    >>> repeated(s, 3)
    5
    >>> s2 = iter([4, 1, 6, 6, 7, 7, 8, 8, 2, 2, 2, 5])
    >>> repeated(s2, 3)
    2
    """
    assert k > 1
    """*** YOUR CODE HERE ***"""