Due at 11:59pm on 7/20/2017.

Starter Files

Download lab09.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

Submission

By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded.

  • Questions 1, 2, and 3 must be completed in order to receive credit for this lab. Starter code for question 1 is in lab09.py.
  • Question 7 is optional. It is recommended that you work on this should you finish the required section early, or if you are struggling with the required questions.
  • Questions 4, 5, 6, 8, and 9 (Coding) are optional. It is recommended that you complete these problems on your own time. Starter code for these questions is in lab09_extra.py.

Helpful Hints

OK has a new feature for the "What would Python display?" questions. As you go through the question's prompts OK may give you a hint based on your wrong answers. Our hope is these hints will help remind you of something important or push you in the right direction to getting the correct answer. For example:

Foo > Suite 1 > Case 1
(cases remaining: 1)

What would Python display? If you get stuck, try it out in the Python
interpreter!

>>> not False or False
? False

-- Helpful Hint --
What about the | not |?
------------------

-- Not quite. Try again! --

? 

Topics

Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.

Interfaces

In computer science, an interface is a shared set of attributes, along with a specification of the attributes' behavior. For example, an interface for vehicles might consist of the following methods:

  • def drive(self): Drives the vehicle if it has stopped.
  • def stop(self): Stops the vehicle if it is driving.

Data types can implement the same interface in different ways. For example, a Car class and a Train can both implement the interface described above, but the Car probably has a different mechanism for drive than the Train.

The power of interfaces is that other programs don't have to know how each data type implements the interface -- only that they have implemented the interface. The following travel function can work with both Cars and Trains:

def travel(vehicle):
    while not at_destination():
        vehicle.drive()
    vehicle.stop()

Linked List Class

A linked list is either an empty linked list (Link.empty) or a Link object containing a first value and the rest of the linked list. Here is a part of the Link class. The entire class can be found in the assignment's files:

class Link:
    """A linked list.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.first
    1
    >>> s.rest
    Link(2, Link(3))
    """
    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

    def __repr__(self):
        if self.rest is Link.empty:
            return 'Link({})'.format(self.first)
        else:
            return 'Link({}, {})'.format(self.first, repr(self.rest))

To check if a Link is empty, compare it against the class attribute Link.empty. For example, the below function prints out whether or not the link it is handed is empty:

def test_empty(link):
    if link is Link.empty:
        print('This linked list is empty!')
    else:
        print('This linked list is not empty!')

Note: Linked lists are recursive data structures! A linked list contains the first element of the list (first) and a reference to another linked list (rest) which contains the rest of the values in the list.

Required Questions

A New Interface: Iterables and Iterators

In lecture, we studied several Python object interfaces, or protocols. In this lab, we will study a new protocol, the iterator protocol. Implementing this protocol allows us to use our objects in for loops! Remember the for loop? (We really hope so!)

for elem in something_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! As it turns out, for loops are actually translated by the interpreter into the following code:

the_iterator = iter(something_iterable)
try:
    while True:
        elem = next(the_iterator)
        # do something
except StopIteration:
    pass

That is, it first calls the built-in iter function to create an iterator, saving it in some new, hidden variable (we've called it the_iterator here). It then repeatedly calls the built-in next function on this iterator to get values of elem and stops when that function raises StopIteration.

Iterators also allow us to represent infinite sequences, such as the sequence of natural numbers (1, 2, ...).

class Naturals:
    """
    >>> m = Naturals()
    >>> [next(m) for _ in range(5)]
    [1, 2, 3, 4, 5]
    """
    def __init__(self):
        self.current = 0

    def __iter__(self):
        return self

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

Coding Practice

Question 1: Scale

Implement an iterator class called ScaleIterator that scales elements in an iterable s by a number k.

class ScaleIterator:
    """An iterator the scales elements of the iterable s by a number k.

    >>> s = ScaleIterator([1, 5, 2], 5)
    >>> for elem in s:
    ...     print(elem)
    5
    25
    10
    >>> m = ScaleIterator([1, 2, 3, 4, 5, 6], 2)
    >>> [next(m) for _ in range(5)]
    [2, 4, 6, 8, 10]
    """
    def __init__(self, s, k):
"*** YOUR CODE HERE ***"
self.s = iter(s) self.k = k
def __iter__(self): return self def __next__(self):
"*** YOUR CODE HERE ***"
return next(self.s) * self.k

Use OK to test your code:

python3 ok -q ScaleIterator

Be careful! If your __next__ method never raises StopIteration, you might loop forever.

What Would Python Display?

Question 2: WWPD: Odds and Evens

So far, the __iter__ method of our iterators only returns self. What if we have called next a few times and then want to start at the beginning? Intuitively, we should create a new iterator that would start at the beginning. However, our current iterator implementations won't allow that.

Consider the following OddNaturalsIterator and EvenNaturalsIterator. Which implementation allows us to start a new iterator at the beginning?

class OddNaturalsIterator:
    def __init__(self):
        self.current = 1

    def __next__(self):
        result = self.current
        self.current += 2
        return result

    def __iter__(self):
        return self

class EvenNaturalsIterator:
    def __init__(self):
        self.current = 0

    def __next__(self):
        result = self.current
        self.current += 2
        return result

    def __iter__(self):
        return EvenNaturalsIterator()

Use OK to test your knowledge with the following conceptual questions:

python3 ok -q odds_evens -u
>>> odds = OddNaturalsIterator()
>>> odd_iter1 = iter(odds)
>>> odd_iter2 = iter(odds)
>>> next(odd_iter1)
______
1
>>> next(odd_iter1)
______
3
>>> next(odd_iter1)
______
5
>>> next(odd_iter2)
______
7
>>> next(odd_iter1)
______
9
>>> next(odd_iter2)
______
11
>>> evens = EvenNaturalsIterator()
>>> even_iter1 = iter(evens)
>>> even_iter2 = iter(evens)
>>> next(even_iter1)
______
0
>>> next(even_iter1)
______
2
>>> next(even_iter1)
______
4
>>> next(even_iter2)
______
0
>>> next(even_iter2)
______
2
>>> class DoubleIterator:
...     def __init__(self):
...         self.current = 2
...     def __next__(self):
...         result = self.current
...         self.current += result
...         return result
...     def __iter__(self):
...         return DoubleIterator()
>>> doubleI = DoubleIterator()
>>> dIter = iter(doubleI)
>>> next(doubleI)
______
2
>>> next(doubleI)
______
4
>>> next(dIter)
______
2
>>> next(dIter)
______
4
>>> next(doubleI)
______
8
>>> class ThreeIterator:
...     def __init__(self):
...         self.current = 10
...     def __next__(self):
...         result = self.current
...         self.current -= 3
...         return result
...     def __iter__(self):
...         return self
>>> threeI = ThreeIterator()
>>> tIter = iter(threeI)
>>> next(threeI)
______
10
>>> next(threeI)
______
7
>>> next(tIter)
______
4
>>> next(tIter)
______
1
>>> next(threeI)
______
-2

Question 3: WWPD: Linked Lists

Use OK to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q link -u

If you get stuck, try drawing out the diagram for the linked list on a piece of paper, or loading the Link class into the interpreter with python3 -i and the Python file you'd like to load.

>>> from link import *
>>> link = Link(1, Link(2, Link(3)))
>>> link.first
______
1
>>> link.rest.first
______
2
>>> link.rest.rest.rest is Link.empty
______
True
>>> link.first = 9001 >>> link.first
______
9001
>>> link.rest = link.rest.rest >>> link.rest.first
______
3
>>> link = Link(1) >>> link.rest = link >>> link.rest.rest.rest.rest.first
______
1
>>> link = Link(2, Link(3, Link(4))) >>> link2 = Link(1, link) >>> link2.first
______
1
>>> link2.rest.first
______
2
>>> print_link(link2) # Look at print_link in link.py
______
<1 2 3 4>

Optional Questions

More Fun with Linked Lists

Important: For these questions, edit the Link class in lab09_extra.py, not link.py.

Question 4: __add__

Let's implement a magic method for our Link class: __add__, which allows us to use the built-in + operator on two Links.

class Link:
    # previous stuff here

    def __add__(self, other):
        """Adds two Links, returning a new Link

        >>> Link(1, Link(2)) + Link(3, Link(4, Link(5)))
        Link(1, Link(2, Link(3, Link(4, Link(5)))))
        """
"*** YOUR CODE HERE ***"
result = Link.empty while self is not Link.empty: result = Link(self.first, result) self = self.rest while other is not Link.empty: result = Link(other.first, result) other = other.rest return reversed(result)

Use OK to test your code:

python3 ok -q add

Question 5: __reversed__

Implement the __reversed__ method in the Link class, which returns a linked list containing the elements of self in reverse order. The original link should be unchanged.

class Link:
    # previous stuff here

    def __reversed__(self):
        """Return a reversed version of the Link.

        >>> reversed(Link(1, Link(2, Link(3))))
        Link(3, Link(2, Link(1)))
        """
"*** YOUR CODE HERE ***"
result = Link.empty while self is not Link.empty: result = Link(self.first, result) self = self.rest return result

Use OK to test your code:

python3 ok -q reversed

Question 6: __str__

Let's implement the __str__ method for our Link class, which allows us to print out a human-readable version of our class using the built-in str function, rather than having to use print_link.

class Link:
    # previous stuff here

    def __str__(self):
        """Returns a human-readable string representation of the Link

        >>> s = Link(1, Link(2, Link(3, Link(4))))
        >>> str(s)
        '<1, 2, 3, 4>'
        >>> str(Link(1))
        '<1>'
        >>> str(Link.empty)  # empty tuple
        '()'
        """
"*** YOUR CODE HERE ***"
string = '<' while self.rest is not Link.empty: string += str(self.first) + ', ' self = self.rest return string + str(self.first) + '>'

Use OK to test your code:

python3 ok -q str

More Fun with Iterators

Question 7: Does it work?

Consider the following iterators. Which ones work and which ones don't? Why?

Use OK to test your knowledge with the following conceptual questions:

python3 ok -q does_it_work -u
class IteratorA:
    def __init__(self):
        self.start = 10

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

    def __iter__(self):
        return self

Does IteratorA work?

No problem, this is a beautiful iterator.

class IteratorB:
    def __init__(self):
        self.start = 5

    def __iter__(self):
        return self

Does IteratorB work?

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:
    def __init__(self):
        self.start = 5

    def __next__(self):
        if self.start == 10:
            raise StopIteration
        self.start += 1
        return self.start

Does IteratorC work?

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.

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

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

    def __iter__(self):
        return self

Does IteratorD work?

This is technically an iterator, because it implements both __iter__ and __next__. Notice that it's 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 8: Restart

Use OK to test your knowledge with the following What would Python display questions:

python3 ok -q restart -u
>>> class IteratorA:
...    def __init__(self):
...        self.start = 10
...    def __next__(self):
...        if self.start > 100:
...            raise StopIteration
...        self.start += 20
...        return self.start
...    def __iter__(self):
...        return self
>>> iterator = IteratorA()
>>> [num for num in iterator]
______
[30, 50, 70, 90, 110]
>>> [num for num in iterator]
______
[]
>>> class IteratorB:
...    def __init__(self):
...        self.start = -6
...    def __next__(self):
...        if self.start > 10:
...            raise StopIteration
...        self.start += 3
...        return self.start
...    def __iter__(self):
...        return self
>>> iterator = IteratorB()
>>> [num for num in iterator]
______
[-3, 0, 3, 6, 9, 12]
>>> [num for num in iterator]
______
[]

The outputs of the list comprehensions are like that because the instance variables are not reset each time a for loop is started. Therefore, when a StopIteration exception is raised at the end of the first list comprehension, it will be raised immediately at the beginning of the second. With that in mind, try writing an iterator that "restarts" every time it is run through a for loop.

class IteratorRestart:
    """
    >>> iterator = IteratorRestart(2, 7)
    >>> for num in iterator:
    ...     print(num)
    2
    3
    4
    5
    6
    7
    >>> for num in iterator:
    ...     print(num)
    2
    3
    4
    5
    6
    7
    """
    def __init__(self, start, end):
"*** YOUR CODE HERE ***"
self.start = start self.end = end self.current = start
def __next__(self):
"*** YOUR CODE HERE ***"
if self.current > self.end: raise StopIteration self.current += 1 return self.current - 1
def __iter__(self):
"*** YOUR CODE HERE ***"
self.current = self.start return self

Use OK to test your code:

python3 ok -q IteratorRestart

Question 9: Str

Write an iterator that takes a string as input and outputs the letters in order when iterated over.

class Str:
    def __init__(self, str):
        self.str = str
    def __iter__(self):
        return iter(self.str)

That works (why?), but just kidding.

class Str:
    """
    >>> s = Str("hello")
    >>> for char in s:
    ...     print(char)
    ...
    h
    e
    l
    l
    o
    >>> for char in s:    # a standard iterator does not restart
    ...     print(char)
    """
"*** YOUR CODE HERE ***"
def __init__(self, str): self.str = str self.i = -1 def __iter__(self): return self def __next__(self): self.i += 1 if self.i >= len(self.str): raise StopIteration return self.str[self.i]

Use OK to test your code:

python3 ok -q Str