Lab 9: Linked Lists and Interfaces
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 Car
s and Train
s:
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 withpython3 -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 Link
s.
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