Iterators and Generators Quick Review

We’ve worked with for loops a lot, so now let’s break the abstraction barrier (haha) and see what’s actually going on when we iterate through something

Iterable = An object that has different elements that can be iterated through (lists, dictionaries, etc.)

Iterator = An object that iterates through the elements of a specific iterable and returns them one by one

an iterator’s process

Okay, so you have an iterable and you want to create an iterator to go through its elements and return them one by one. The first step is creating the actual iterator object, since the iterator can’t yield stuff if it doesn’t exist. To create an iterator, all you have to do is call the iter function on your iterable. Then, from there, you can repeatedly call the next function on the iterator object, which will yield a new element each time. If you call next more times than the number of elements in the iterable, you will get what’s called a StopIteration error. The key with iterators is that you can never go backwards, re-start from the beginning, or repeat elements; an iterator will iterate through an iterable once from beginning to end and do nothing else.

To summarize (maybe consider writing this diagram on your cheat sheet!):

Iterable ⇨ iter(iterable) ⇨ Iterator ⇨ next(iterator) ⇨ First element of iterable

As an additional note, there is also a list function that takes in an iterator object and returns a list containing all remaining elements of the iterable that have not already been returned.

Example:

In this example, lst is our iterable and lst_it is our iterator. Calling next() once gives us the first element of lst, which is 1, and then calling list() gives us the remaining 2 elements in list form, [2, 3]. Then, when we try to call next() again, we get a StopIteration Error because we’ve run out of elements, and an iterator will never start from the beginning again.

One last note about iterators is that when you create an iterator object, it is bound to a specific iterable object, not an iterable’s name. Even if you reassign the iterable variable’s name to a new iterable object, the iterator is still bound to the old iterable object.

Generator Function = A function that has one or more yield statements inside of it

Generator = A special type of iterator that iterates through a generator function

A Generator’s ProcesS

With generators, we always start with a generator function (which will always have at least one yield statement inside of it). In order to create the actual generator object, we call the generator function. Then, in order to actually run the body of the generator function, we call next() on the generator object. Our function will then run until the first yield statement, yield something, and then stop. The next time we call next(), we will start from the line after the yield statement and run until we either hit another yield, or we reach the end of the function.

To summarize (maybe consider writing this diagram on your cheat sheet!):

Generator function (has a yield statement) ⇨ call function ⇨ Generator object ⇨ next(generator object) ⇨ Generator function runs until first yield ⇨ next(generator object) ⇨ Generator function runs until next yield or end of function

Example:

Our generator function is gen_ftn, since it has a yield statement, and our generator object is gen_obj, since that’s the result of our call to gen_ftn. Each next() call runs gen_ftn until it hits a yield, and then picks up at the n-= 1 line on the next next() call.

recursive generators

The most common type of generator question you will see on a 61A exam is a recursive generator question. Let’s see an example of what I mean:

This is a very simple example of a recursive generator function. We can tell it’s recursive because it calls itself, and we can tell that it’s a generator function because it has several yield statements in it. I can tell you that this generator function will return a generator object that yields all numbers from 0 up to and including the passed in n. Now let’s think about how this function is actually working. The base case is pretty straightforward, so let’s take a look at the recursive case. Remember that when you call a generator function, it returns a generator object. Also, remember that generators are a special type of iterator, which means that we can loop through all the values in the generator object. And in fact, that’s all that’s going on here: we are recursively calling the generator function, which will give us a generator object. Using the recursive leap of faith, we know that recursive_gen(n - 1) will give us a generator object that will yield all numbers from 0 through n - 1. That means that all we have to do is yield all of the values in that generator object and then yield n, and we’ve successfully yielded all values up to and including n.