for elem in iterable:
    # do something

In general, an iterable is an object on which calling the built-in iter function returns an iterator. An iterator is an object on which calling the built-in next function returns the next value.

For example, a list is an iterable value.

>>> s = [1, 2, 3, 4]
>>> next(s)       # s is iterable, but not an iterator
TypeError: 'list' object is not an iterator
>>> t = iter(s)   # Creates an iterator
>>> t
<list_iterator object ...>
>>> next(t)       # Calling next on an iterator
1
>>> next(t)       # Calling next on the same iterator
2
>>> next(iter(t)) # Calling iter on an iterator returns itself
3
>>> t2 = iter(s)
>>> next(t2)      # Second iterator starts at the beginning of s
1
>>> next(t)       # First iterator is unaffected by second iterator
4
>>> next(t)       # No elements left!
StopIteration
>>> s             # Original iterable is unaffected
[1, 2, 3, 4]

You can also use an iterator in a for statement because all iterators are iterable. But note that since iterators keep their state, they're only good to iterate through an iterable once:

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

There are built-in functions that return iterators.

>>> m = map(lambda x: x * x, [3, 4, 5])
>>> next(m)
9
>>> next(m)
16
>>> f = filter(lambda x: x > 3, [3, 4, 5])
>>> next(f)
4
>>> next(f)
5
>>> z = zip([30, 40, 50], [3, 4, 5])
>>> next(z)
(30, 3)
>>> next(z)
(40, 4)

For example, let's consider the following generator function:

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

Calling countdown(k) will return a generator object that counts down from k to 0. Since generators are iterators, we can call iter on the resulting object, which will simply return the same object. Note that the body is not executed at this point; nothing is printed and no numbers are outputted.

>>> c = countdown(5)
>>> c
<generator object countdown ...>
>>> c is iter(c)
True

So how is the counting done? Again, since generators are iterators, we call next on them to get the next element! The first time next is called, execution begins at the first line of the function body and continues until the yield statement is reached. The result of evaluating the expression in the yield statement is returned. The following interactive session continues from the one above.

>>> next(c)
Beginning countdown!
5

Unlike functions we've seen before in this course, generator functions can remember their state. On any consecutive calls to next, execution picks up from the line after the yield statement that was previously executed. Like the first call to next, execution will continue until the next yield statement is reached. Note that because of this, Beginning countdown! doesn't get printed again.

>>> next(c)
4
>>> next(c)
3

The next 3 calls to next will continue to yield consecutive descending integers until 0. On the following call, a StopIteration error will be raised because there are no more values to yield (i.e. the end of the function body was reached before hitting a yield statement).

>>> next(c)
2
>>> next(c)
1
>>> next(c)
0
>>> next(c)
Blastoff!
StopIteration

Separate calls to countdown will create distinct generator objects with their own state. Usually, generators shouldn't restart. If you'd like to reset the sequence, create another generator object by calling the generator function again.

>>> c1, c2 = countdown(5), countdown(5)
>>> c1 is c2
False
>>> next(c1)
5
>>> next(c2)
5

Here is a summary of the above:

• A generator function has a yield statement and returns a generator object.
• Calling the iter function on a generator object returns the same object without modifying its current state.
• The body of a generator function is not evaluated until next is called on a resulting generator object. Calling the next function on a generator object computes and returns the next object in its sequence. If the sequence is exhausted, StopIteration is raised.

• A generator "remembers" its state for the next next call. Therefore,

  • the first next call works like this:

    1. Enter the function and run until the line with yield.
    2. Return the value in the yield statement, but remember the state of the function for future next calls.

  • And subsequent next calls work like this:

    1. Re-enter the function, start at the line after the yield statement that was previously executed, and run until the next yield statement.
    2. Return the value in the yield statement, but remember the state of the function for future next calls.
• Calling a generator function returns a brand new generator object (like calling iter on an iterable object).
• A generator should not restart unless it's defined that way. To start over from the first element in a generator, just call the generator function again to create a new generator.

Another useful tool for generators is the yield from statement. yield from will yield all values from an iterator or iterable.

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

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.

For example, let's say that we have the function get_x which is defined as follows:

def get_x(x):
    return x

get_x has one expression in it. That one expression takes the same amount of time to run, no matter what x is, or more importantly, how large x gets. This is called constant time.

The main two ways that a function in your program will get a running time different than just constant time is through either iteration or recursion. Let's start with some iteration examples!

The (simple) way you figure out the running time of a particular while loop is to simply count the cost of each operation in the body of the while loop, and then multiply that cost by the number of times that the loop runs. For example, look at the following method with a loop in it:

def foo(n):
    i, sum = 1, 0
    while i <= n:
        sum,i = sum + i, i + 1
    return sum

This loop has one statement in it sum, i = sum + i, i + 1. This statement is considered to run in constant time, as none of its operations rely on the size of the input. Individually, sum = sum + 1 and i = i + 1 are both constant time operations. However, when we're looking at order of growth, we take the maximum of those 2 values and use that as the running time. In 61A, we are not concerned with how long primitive functions, such as addition, multiplication, and variable assignment, take in order to run - we are mainly concerned with how many more times a loop is executed or how many more recursive calls occur as the input increases. In this example, we execute the loop n times, and for each iteration, we only execute constant time operations, so we get an order of growth of linear.

Here are a couple of basic functions, along with their running times. Try to understand why they have the given running time.

1. Constant

   def bar(n):
       i = 0
       while i < 10:
           n = n * 2
           i += 1
       return n

2. Logarithmic

   def bar(n):
       i = 1
       while n:
           i = i * 3
           n = n // 2
       return i

3. Linear

   def bar(n):
       i, a, b = 1, 1, 0
       while i <= n:
           a, b, i = a + b, a, i + 1
        return a

4. Quadratic

   def bar(n):
       sum = 0
       a, b = 0, 0
       while a < n:
           while b < n:
               sum += (a*b)
               b += 1
           b = 0
           a += 1
       return sum

5. Exponential

   def bar(n):
       if n == 0: 
           return 1
       else:
           return bar(n - 1) + bar(n - 1)