Lab 9: Iterators and Generators

Table of Contents

Deadline

By the end of this lab, you should have submitted the lab09 assignment using the command submit lab09.

This lab is due by 11:59pm on 7/24/2014.

Here is a lab09.py starter file for this lab.

Iterators

Question 1

Try running each of the given iterators in a for loop. Why does each work or not work? 
class IteratorA(object):
    def __init__(self):
        self.start = 5

    def __next__(self):
        if self.start == 100:
            raise StopIteration
        self.start += 5
        return self.start

    def __iter__(self):
        return self
No problem, this is a beautiful iterator. 
class IteratorB(object):
    def __init__(self):
        self.start = 5

    def __iter__(self):
        return self
Oh no! Where is __next__? This fails to implement the iterator interface because calling __iter__ doesn't return something that has a __next__ method. 
class IteratorC(object):
    def __init__(self):
        self.start = 5

    def __next__(self):
        if self.start == 10:
            raise StopIteration
        self.start += 1
        return self.start
This also fails to implement the iterator interface. Without the __iter__ method, the for loop will error. The for loop needs to call __iter__ first because some objects might not implement the __next__ method themselves, but calling __iter__ will return an object that does.

Watch out on this one. Remember that Ctrl-C is how you stop an infinite loop.

class IteratorD(object):
    def __init__(self):
        self.start = 1

    def __next__(self):
        self.start += 1
        return self.start

    def __iter__(self):
        return self
This is an infinite sequence! Sequences like these are the reason iterators are useful. Because iterators delay computation, we can use a finite amount of memory to represent an infinitely long sequence.

Question 2

For one of the above iterators that works, try this: 
>>> i = Iterator() # Replace with an iterator that works
>>> for item in i:
...     print(item)

Then again:

>>> for item in i:
...     print(item)

Make sure you understand why you get the output that you get. With that in mind, try writing an iterator that "restarts" every time it is run through a for loop.

class IteratorRestart(object):
    """
    >>> i = IteratorRestart(2, 6)
    >>> for item in i:
    ...     print(item)
    2
    3
    4
    5
    >>> for item in i:
    ...     print(item)
    2
    3
    4
    5
    """
    def __init__(self, start, end):
        "*** YOUR CODE HERE ***"

    def __next__(self):
        "*** YOUR CODE HERE ***"

    def __iter__(self):
        "*** YOUR CODE HERE ***"
class IteratorRestart(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.current = start
    def __next__(self):
        if self.current > self.end:
            raise StopIteration
        self.current += 1
        return self.current - 1
    def __iter__(self):
        self.current = self.start
        return self

Generators

A generator is a special type of iterator that can be written using a yield statement:

def <generator_function>():
    <somevariable> = <something>
    while <predicate>:
        yield <something>
        <increment variable>

A generator function can also be run through a for loop:

def generator():
    i = 0
    while i < 6:
        yield i
        i += 1

for i in generator():
    print(i)

To better figure out what is happening, try this:

def generator():
    print("Starting here")
    i = 0
    while i < 6:
        print("Before yield")
        yield i
        print("After yield")
        i += 1

>>> g = generator()
>>> g
___ # what is this thing?
>>> g.__iter__()
___
>>> g.__next__()
___
>>> g.__next__()
____

Trace through the code and make sure you know where and why each statement is printed.

You might have noticed from the Iterators section that the Iterator defined without a __next__ method failed to run in the for loop. However, this is not always the case.

class IterGen(object):
    def __init__(self):
        self.start = 5

    def __iter__(self):
        while self.start < 10:
            self.start += 1
            yield self.start

for i in IterGen():
    print(i)

Think for a moment about why that works.

Think more.

Longer.

Okay, I'll tell you.

The for loop only expects the object returned by __iter__ to have a __next__ method, and the __iter__ method is a generator function in this case. Therefore, when __iter__ is called, it returns a generator object, which you can call __next__ on.

Question 3

Write a generator that counts down to 0.

Write it in both ways: using a generator function on its own, and within the __iter__ method of a class.

def countdown(n):
    """
    >>> for number in countdown(3):
    ...     print(number)
    ...
    3
    2
    1
    0
    """
    "*** YOUR CODE HERE ***"
    while n >= 0:
        yield n
        n = n - 1
class Countdown(object):
    """
    >>> counter = Countdown(3)
    >>> hasattr(counter, '__next__')
    False
    >>> for number in counter:
    ...     print(number)
    ...
    3
    2
    1
    0
    """
    "*** YOUR CODE HERE ***"
    def __init__(self, cur):
        self.cur = cur

    def __iter__(self):
        while self.cur > 0:
            yield self.cur
            self.cur -= 1

Question 4

Write a generator function that outputs the hailstone sequence from homework 1.

def hailstone(n):
    """
    >>> type(hailstone(10))
    <class 'generator'>
    >>> for num in hailstone(10):
    ...     print(num)
    ...
    10
    5
    16
    8
    4
    2
    1
    """
    "*** YOUR CODE HERE ***"
    i = n
    while i > 1:
        yield i
        if i % 2 == 0:
            i //= 2
        else:
            i = i * 3 + 1
    yield i

Question 5

Write a generator function pairs that takes a list and yields all the possible pairs of elements from that list.

Note that this means that you should be yielding a tuple.

def pairs(lst):
    """
    >>> type(pairs([3, 4, 5]))
    <class 'generator'>
    >>> for x, y in pairs([3, 4, 5]):
    ...     print(x, y)
    ...
    3 3
    3 4
    3 5
    4 3
    4 4
    4 5
    5 3
    5 4
    5 5
    """
    "*** YOUR CODE HERE ***"
    for i in lst:
        for j in lst:
            yield i, j

Optional Problems

Question 6

Now write an iterator that does the same thing. You are only allowed to use a linear amount of space - so computing a list of all of the possible pairs is not a valid answer. Notice how much harder it is - this is why generators are useful.

class PairsIterator:
    """
    >>> for x, y in PairsIterator([3, 4, 5]):
    ...     print(x, y)
    ...
    3 3
    3 4
    3 5
    4 3
    4 4
    4 5
    5 3
    5 4
    5 5
    """
    def __init__(self, lst):
        "*** YOUR CODE HERE ***"

    def __next__(self):
        "*** YOUR CODE HERE ***"

    def __iter__(self):
        "*** YOUR CODE HERE ***"
    def __init__(self, lst):
        self.lst = lst
        self.i = 0
        self.j = 0

    def __next__(self):
        if self.i == len(self.lst):
            raise StopIteration
        result = self.lst[self.i], self.lst[self.j]
        if self.j == len(self.lst) - 1:
            self.i += 1
            self.j = 0
        else:
            self.j += 1
        return result

    def __iter__(self):
        return self