This lab is due at 11:59pm on 10/22/2014.
Please start at the beginning of the lab and work your way through, working and talking over Python's behavior in the conceptual questions with your classmates nearby. These questions are designed to help you experiment with the concepts on the Python interpreter. They are good tests for your understanding.
When you are done with this lab, submit Questions 2 and 3 (provided in the starter file lab07.py) to receive credit for this lab. The rest are questions that are considered extra practice — they can be found in the the lab07_extra.py file. It is recommended that you complete these problems in your own time.
By the end of this lab, you should have submitted the lab07
assignment using the command submit lab07
. You can check if we
received your submission by running glookup -t
. Click
here to see more complete
submission instructions.
In lecture, we introduced the OOP version of a linked list:
class Link:
"""A linked list.
>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> len(s)
4
>>> s[2]
3
>>> s
Link(1, Link(2, Link(3, Link(4))))
"""
empty = ()
def __init__(self, first, rest=empty):
self.first = first
self.rest = rest
def __getitem__(self, i):
if i == 0:
return self.first
else:
return self.rest[i-1]
def __len__(self):
return 1 + len(self.rest)
def __repr__(self):
if self.rest:
rest_str = ', ' + repr(self.rest)
else:
rest_str = ''
return 'Link({0}{1})'.format(repr(self.first), rest_str)
Just like before, these linked lists have a first and a rest. The difference is that, now, the linked lists are mutable.
To check if a Link
is empty, compare it against the class
variable Link.empty
:
if linked_list is Link.empty:
return 'This linked list is empty!'
Predict what Python will display when the following lines are typed into the interpreter:
>>> Link()
______TypeError
>>> 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
Implement a function insert
that takes a Link, a value, and an
index, and inserts the value into the Link at the given index. You
can assume the linked list already has at least one element. Do NOT return
anything — insert
should mutate the linked list.
def insert(link, value, index):
"""Insert a value into a Link at the given index.
>>> link = Link(1, Link(2, Link(3)))
>>> insert(link, 9001, 0)
>>> link
Link(9001, Link(1, Link(2, Link(3))))
>>> insert(link, 100, 2)
>>> link
Link(9001, Link(1, Link(100, Link(2, Link(3)))))
>>> insert(link, 4, 5)
Index out of bounds
"""
"*** YOUR CODE HERE ***"
# recursive solution
if index == 0:
link.rest = Link(link.first, link.rest)
link.first = value
elif link.rest is Link.empty:
print('Index out of bounds')
else:
insert(link.rest, value, index - 1)
# iterative solution
def insert(link, value, index):
while index > 0 and link.rest is not Link.empty:
link = link.rest
index -= 1
if index == 0:
link.rest = Link(link.first, link.rest)
link.first = value
else:
print('Index out of bounds')
In lecture, we learned about the special "underscore" methods for
classes, two of which were __len__
, which allows you to call the
built-in function len
on the object, and __getitem__
, which allows
you to use index notation on the object. These methods fall
under a category of generic functions called polymorphic functions,
named because they can operate on different types of data.
Let's implement one more method for our Link
class: __str__
,
which allows us to print out a human-readable version of our class
using the built-in str
function.
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) + '>'
Write a function link_to_list
that converts a given Link to a
Python list.
def link_to_list(link):
"""Takes a Link and returns a Python list with the same elements.
>>> link = Link(1, Link(2, Link(3, Link(4))))
>>> link_to_list(link)
[1, 2, 3, 4]
>>> rlist_to_list(Link.empty)
[]
"""
"*** YOUR CODE HERE ***"
# Recursive solution
if link is Link.empty:
return []
return [link.first] + link_to_list(link.rest)
# Iterative solution
def link_to_list(link):
result = []
while link is not Link.empty:
result.append(link.first)
link = link.rest
return result
Implement a function reverse
that reverses a given Link. reverse
should return a new Link that is the reverse of the original.
Extra for experts: Implement reverse
that mutates the Link,
without constructing a new Link. Hint: You might want to still
return something from this function.
def reverse(link):
"""Returns a Link that is the reverse of the original.
>>> Link(1).rest is Link.empty
True
>>> link = Link(1, Link(2, Link(3)))
>>> reverse(link)
Link(3, Link(2, Link(1)))
>>> reverse(Link(1))
Link(1)
"""
"*** YOUR CODE HERE ***"
# iterative solution
new = Link(link.first)
while link.rest is not Link.empty:
link = link.rest
new = Link(link.first, new)
return new
# recursive (and extra for experts)
def reverse(link):
if link.rest is not Link.empty:
second, last = link.rest, link
link = reverse(second)
second.rest, last.rest = last, Link.empty
return link
__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 ***"
ret = Link.empty
while self is not Link.empty:
ret = Link(self.first, ret)
self = self.rest
while other is not Link.empty:
ret = Link(other.first, ret)
other = other.rest
return reverse(ret)
__setitem__
for our Link class, which allows us
to assign to an index in a Link.
class Link:
#previous stuff here
def __setitem__(self, index, element):
"""Sets the value at the given index to the element
>>> s = Link(1, Link(2, Link(3)))
>>> s[1] = 5
>>> s
Link(1, Link(5, Link(3)))
>>> s[4] = 5
Traceback (most recent call last):
...
IndexError
"""
"*** YOUR CODE HERE ***"
if index == 0:
self.first = element
elif self.rest is Link.empty:
raise IndexError
else:
self.rest[index - 1] = element
Another approach to implementing generic functions that operate over multiple types of data is type dispatching, where we inspect the type of the argument to our function and dispatch to a function that can handle each type individually.
One way to implement type dispatching is by using a dictionary that maps
every type we're working with to an identifier, e.g. a string. For example,
we can tag the Link
class and built-in Python list class as follows:
def type_tag(x):
return type_tag.tags[type(x)]
type_tag.tags = {
list : 'list',
Link : 'link'
}
Now, we can ask for the tag corresponding to these two types:
>>> type_tag([1, 2, 3])
'list'
>>> type_tag(Link(1, Link(2, Link(3))))
'link'
Using this pattern of type dispatching, complete the implementation of
the function concat
that takes two sequences, either Python lists or
Link
s, and adds the elements of the two sequences together and
returns a new sequence of the type of the first sequence.
def type_tag(x):
return type_tag.tags[type(x)]
type_tag.tags = {
list : 'list',
Link : 'link'
}
def concat(seq1, seq2):
"""Takes the elements of seq1 and seq2 and adds them together.
>>> link = Link(4, Link(5, Link(6)))
>>> lst = [1, 2, 3]
>>> concat(lst, link)
[1, 2, 3, 4, 5, 6]
>>> concat(link, [7, 8])
Link(4, Link(5, Link(6, Link(7, Link(8)))))
>>> concat(lst, [7, 8, 9])
[1, 2, 3, 4, 5, 6, 7, 8, 9]
"""
if type_tag(seq1) == type_tag(seq2):
return seq1 + seq2
else:
types = (type_tag(seq1), type_tag(seq2))
if types in concat.adders:
return concat.adders[types](seq1, seq2)
def add_list_link(lst, link):
"*** YOUR CODE HERE ***"
return lst + link_to_list(link)
def add_link_list(link, lst):
"*** YOUR CODE HERE ***"
ret = Link.empty
while link is not Link.empty:
ret = Link(link.first, ret)
link = link.rest
while lst:
ret = Link(lst[0], ret)
lst = lst[1:]
return reverse(ret)
concat.adders = {
('list', 'link') : add_list_link,
('link', 'list') : add_link_list
}
When we write recursive functions acting on Link
s, we often find
that they have the following form:
def func(link):
if link is Link.empty:
return <Base case>
else:
return <Expression involving func(link.rest)>
In the spirit of abstraction, we want to factor out this commonly seen
pattern. It turns out that we can define an abstraction called fold
that do this.
A linked list can be represented as a series of Link
constructors, where Link.rest
is either another linked list or
the empty list.
We represent such a list in the diagram below:
In this diagram, the recursive list
Link(1, Link(2, Link(3, Link(4,Link(5)))))
is represented with :
as the constructor and []
as the empty list.
We define a function foldr
that takes in a function f
which takes
two arguments, and a value z
. foldr
essentially replaces the
Link
constructor with f, and the empty list with z
. It then
evaluates the expression and returns the result. This is equivalent to:
f(1, f(2, f(3, f(4, f(5, z)))))
We call this operation a right fold.
Similarily we can define a left fold foldl
that folds a list starting
from the beginning, such that the function f
will be applied this
way:
f(f(f(f(f(z, 1), 2), 3), 4), 5)
Also notice that a left fold is equivilant to python's reduce
with a
starting value.
Write the left fold function by filling in the blanks.
def foldl(link, fn, z):
""" Left fold
>>> lst = Link(3, Link(2, Link(1)))
>>> foldl(lst, sub, 0) # (((0 - 3) - 2) - 1)
-6
>>> foldl(lst, add, 0) # (((0 + 3) + 2) + 1)
6
>>> foldl(lst, mul, 1) # (((1 * 3) * 2) * 1)
6
"""
if link is Link.empty:
return z
"*** YOUR CODE HERE ***"
return foldl(______, ______, ______)
return foldl(link.rest, fn, fn(z, link.first))
Now write the right fold function.
def foldr(link, fn, z):
""" Right fold
>>> lst = Link(3, Link(2, Link(1)))
>>> foldr(lst, sub, 0) # (3 - (2 - (1 - 0)))
2
>>> foldr(lst, add, 0) # (3 + (2 + (1 + 0)))
6
>>> foldr(lst, mul, 1) # (3 * (2 * (1 * 1)))
6
"""
"*** YOUR CODE HERE ***"
if link is Link.empty:
return z
return fn(link.first, foldr(link.rest, fn, z))
Write foldl
using foldr
! You only need to fill in the step
function.
identity = lambda x: x
def foldl2(link, fn, z):
""" Write foldl using foldr
>>> list = Link(3, Link(2, Link(1)))
>>> foldl2(list, sub, 0) # (((0 - 3) - 2) - 1)
-6
>>> foldl2(list, add, 0) # (((0 + 3) + 2) + 1)
6
>>> foldl2(list, mul, 1) # (((1 * 3) * 2) * 1)
6
"""
def step(x, g):
"*** YOUR CODE HERE ***"
return lambda a: g(fn(a, x)) return foldr(link, step, identity)(z)