Lab 7: Linked List Class and Generic Functions

Table of Contents

Submission

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.

Mutable Linked Lists

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!'

Question 1

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

Question 2

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')

Generic Functions

Question 3

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) + '>'

Extra Questions

Question 4

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

Question 5

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

Question 6

Let's implement one more special "underscore" 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 ***"
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)

Question 7

Let's also implement __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

Generic Functions, revisited

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'

Question 8

Using this pattern of type dispatching, complete the implementation of the function concat that takes two sequences, either Python lists or Links, 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 }

List folding

When we write recursive functions acting on Links, 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:

Right fold

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)

Left fold

Also notice that a left fold is equivilant to python's reduce with a starting value.

Question 9

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))

Question 10

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))

Question 11: Extra for Experts

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)