Lab 7: Recursive Objects

Due at 11:59pm on Friday, 03/09/2018.

Starter Files

Download lab07.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. Check that you have successfully submitted your code on okpy.org.

  • To receive credit for this lab, you must complete Questions 1, 2, 3, 4, and 5 in lab07.py and submit through OK.
  • Questions 6 through 9 are extra practice. They can be found in the lab07_extra.py file. It is recommended that you complete these problems on your own time.

Topics

Linked Lists

We've learned that a Python list is one way to store sequential values. Another type of list is a linked list. A Python list stores all of its elements in a single object, and each element can be accessed by using its index. A linked list, on the other hand, is a recursive object that only stores two things: its first value and a reference to the rest of the list, which is another linked list.

We can implement a class, Link, that represents a linked list object. Each instance of Link has two instance attributes, first and rest.

class Link:
    """A linked list.

    >>> s = Link(1)
    >>> s.first
    1
    >>> s.rest is Link.empty
    True
    >>> s = Link(2, Link(3, Link(4)))
    >>> s.second
    3
    >>> s.first = 5
    >>> s.second = 6
    >>> s.rest.rest = Link.empty
    >>> s                                    # Displays the contents of repr(s)
    Link(5, Link(6))
    >>> s.rest = Link(7, Link(Link(8, Link(9))))
    >>> s
    Link(5, Link(7, Link(Link(8, Link(9)))))
    >>> print(s)                             # Prints str(s)
    <5 7 <8 9>>
    """
    empty = ()

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

    @property
    def second(self):
        return self.rest.first

    @second.setter
    def second(self, value):
        self.rest.first = value

    def __repr__(self):
        if self.rest is not Link.empty:
            rest_repr = ', ' + repr(self.rest)
        else:
            rest_repr = ''
        return 'Link(' + repr(self.first) + rest_repr + ')'

    def __str__(self):
        string = '<'
        while self.rest is not Link.empty:
            string += str(self.first) + ' '
            self = self.rest
        return string + str(self.first) + '>'

A valid linked list can be one of the following:

  1. An empty linked list (Link.empty)
  2. A Link object containing the first value of the linked list and a reference to the rest of the linked list

What makes a linked list recursive is that the rest attribute of a single Link instance is another linked list! In the big picture, each Link instance stores a single value of the list. When multiple Links are linked together through each instance's rest attribute, an entire sequence is formed.

Note: This definition means that the rest attribute of any Link instance must be either Link.empty or another Link instance! This is enforced in Link.__init__, which raises an AssertionError if the value passed in for rest is neither of these things.

We've also defined a pseudo-attribute second with the @property decorator that will return the second element in the linked list as well as a corresponding setter. Note that the second element of a linked list is really just the first attribute of the Link instance stored in rest. Don't worry too much about the syntax of the setter function for now. See the docstring for a closer look at how to use this property.

To check if a linked list is empty, compare it against the class attribute Link.empty. For example, the function below 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!')

Motivation: Why linked lists

Since you are already familiar with Python's built-in lists, you might be wondering why we are teaching you another list representation. There are historical reasons, along with practical reasons. Later in the course, you'll be programming in Scheme, which is a programming language that uses linked lists for almost everything.

For now, let's compare linked lists and Python lists by looking at two common sequence operations: inserting an item and indexing.

Python's built-in list is like a sequence of containers with indices on them:

arraylist

Linked lists are a list of items pointing to their neighbors. Notice that there's no explicit index for each item.

linkedlist

Suppose we want to add an item at the head of the list.

  • With Python's built-in list, if you want to put an item into the container labeled with index 0, you must move all the items in the list into its neighbor containers to make room for the first item;

arraylist

  • With a linked list, you tell Python that the neighbor of the new item is the old beginning of the list.

arraylist

We can compare the speed of this operation by timing how long it takes to insert a large number of items to the beginning of both types of lists. Enter the following command in your terminal to test this:

python3 timing.py insert 100000

Now, let's take a look at indexing. Say we want the item at index 3 from a list.

  • In the built-in list, you can use Python list indexing, e.g. lst[3], to easily get the item at index 3.
  • In the linked list, you need to start at the first item and repeatedly follow the rest attribute, e.g. link.rest.rest.first. How does this scale if the index you were trying to access was very large?

To test this, enter the following command in your terminal

python3 timing.py index 10000

This program compares the speed of randomly accessing 10,000 items from both a linked list and a built-in Python list (each with length 10,000).

What conclusions can you draw from these tests? Can you think of situations where you would want to use one type of list over another? In this class, we aren't too worried about performance. However, in future computer science courses, you'll learn how to make performance tradeoffs in your programs by choosing your data structures carefully.

Trees (Again)

We've already seen trees as abstract data types. Recall that a tree is a recursive data type that has a label (the value stored in the root of the tree) and branches (a list of trees directly underneath the root).

The tree data type that we studied was simply an abstract representation of a tree structure. Behind the scenes, the tree ADT was implemented using Python lists.

Now, we'll be working with trees as actual objects with attributes and methods! Here is the class definition:

class Tree:
    def __init__(self, label, branches=[]):
        for c in branches:
            assert isinstance(c, Tree)
        self.label = label
        self.branches = list(branches)

    def __repr__(self):
        if self.branches:
            branches_str = ', ' + repr(self.branches)
        else:
            branches_str = ''
        return 'Tree({0}{1})'.format(self.label, branches_str)

    def is_leaf(self):
        return not self.branches

    def __eq__(self, other):
        return type(other) is type(self) and self.label == other.label \
               and self.branches == other.branches

    def __str__(self):
        def print_tree(t, indent=0):
            tree_str = '  ' * indent + str(t.label) + "\n"
            for b in t.branches:
                tree_str += print_tree(b, indent + 1)
            return tree_str
        return print_tree(self).rstrip()

    def copy_tree(self):
        return Tree(self.label, [b.copy_tree() for b in self.branches])

You'll see that the Tree class is pretty similar to the tree ADT, namely because the class is simple a formalization of the abstract data type into a real, user-defined data type. Here is a summary of the differences:

- Tree ADT Tree class
Constructing a tree Calling the constructor function tree(...) returns a tree ADT Calling the class constructor Tree(...) (which calls Tree.__init__(...)) returns a Tree object
Label and branches Returned by selector functions label(...) and branches(...) Stored in instance attributes label and branches
Mutability The tree ADT is immutable The label and branches attributes of a Tree instance can be reassigned, mutating the tree
Checking if a tree is a leaf The convenience function is_leaf(...) returns whether or not a tree ADT is a leaf. The bound method t.is_leaf() returns whether or not a Tree object is a leaf. This method can only be called on Tree objects.

Required Questions

What Would Python Display?

Q1: WWPD: Linked Lists

Read over the Link class in lab07.py. Make sure you understand the doctests.

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

python3 ok -q link -u

Enter Function if you believe the answer is <function ...>, Error if it errors, and Nothing if nothing is displayed.

If you get stuck, try drawing out the box-and-pointer diagram for the linked list on a piece of paper or loading the Link class into the interpreter with python3 -i lab07.py.

>>> from lab07 import *
>>> link = Link(1000)
>>> link.first
______
1000
>>> link.rest is Link.empty
______
True
>>> link = Link(1000, 2000)
______
AssertionError
>>> link = Link(1000, Link())
______
TypeError
>>> from lab07 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
>>> from lab07 import *
>>> link = Link(5, Link(6, Link(7)))
>>> link.second
______
6
>>> link.rest.second
______
7
>>> link.second = 10 >>> link # Look at the __repr__ method of Link
______
Link(5, Link(10, Link(7)))
>>> link.second = Link(8, Link(9)) >>> link.second.first
______
8
>>> print(link) # Look at the __str__ method of Link
______
<5 <8 9> 7>

Q2: WWPD: Trees

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

python3 ok -q trees -u

Enter Function if you believe the answer is <function ...>, Error if it errors, and Nothing if nothing is displayed.

>>> from lab07 import *
>>> t = Tree(1, Tree(2))
______
Error
>>> t = Tree(1, [Tree(2)]) >>> t.label
______
1
>>> t.branches[0]
______
Tree(2)
>>> t.branches[0].label
______
2
>>> t.label = t.branches[0].label >>> t
______
Tree(2, [Tree(2)])
>>> t.branches.append(Tree(4, [Tree(8)])) >>> len(t.branches)
______
2
>>> t.branches[0]
______
Tree(2)
>>> t.branches[1]
______
Tree(4, [Tree(8)])

Coding Practice

Q3: Link to List

Write a function link_to_list that takes in a linked list and returns the sequence as a Python list. You may assume that the input list is shallow; none of the elements is another linked list.

Try to find both an iterative and recursive solution for this problem!

def link_to_list(link):
    """Takes a linked list 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]
    >>> link_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

Use Ok to test your code:

python3 ok -q link_to_list

Q4: Store Digits

Write a function store_digits that takes in an integer n and returns a linked list where each element of the list is a digit of n.

def store_digits(n):
    """Stores the digits of a positive number n in a linked list.

    >>> s = store_digits(1)
    >>> s
    Link(1)
    >>> store_digits(2345)
    Link(2, Link(3, Link(4, Link(5))))
    >>> store_digits(876)
    Link(8, Link(7, Link(6)))
    """
"*** YOUR CODE HERE ***"
result = Link.empty while n > 0: result = Link(n % 10, result) n //= 10 return result

Use Ok to test your code:

python3 ok -q store_digits

Q5: Cumulative Sum

Write a function cumulative_sum that mutates the Tree t, where each node's label becomes the sum of all entries in the subtree rooted at the node.

def cumulative_sum(t):
    """Mutates t where each node's root becomes the sum of all entries in the
    corresponding subtree rooted at t.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> cumulative_sum(t)
    >>> t
    Tree(16, [Tree(8, [Tree(5)]), Tree(7)])
    """
"*** YOUR CODE HERE ***"
for st in t.branches: cumulative_sum(st) t.label = sum([st.label for st in t.branches]) + t.label

Use Ok to test your code:

python3 ok -q cumulative_sum

Optional Questions

The following questions are for extra practice -- they can be found in the the lab07_extra.py file. It is recommended that you complete these problems on your own time.

Linked List Practice

Q6: Remove All

Implement a function remove_all that takes a Link, and a value, and remove any linked list node containing that value. You can assume the list already has at least one node containing value and the first element is never removed. Notice that you are not returning anything, so you should mutate the list.

def remove_all(link , value):
    """Remove all the nodes containing value. Assume there exists some
    nodes to be removed and the first element is never removed.

    >>> l1 = Link(0, Link(2, Link(2, Link(3, Link(1, Link(2, Link(3)))))))
    >>> print(l1)
    <0 2 2 3 1 2 3>
    >>> remove_all(l1, 2)
    >>> print(l1)
    <0 3 1 3>
    >>> remove_all(l1, 3)
    >>> print(l1)
    <0 1>
    """
"*** YOUR CODE HERE ***"
if link is Link.empty or link.rest is Link.empty: return if link.rest.first == value: link.rest = link.rest.rest remove_all(link, value) else: remove_all(link.rest, value) # alternate solution if link is not Link.empty and link.rest is not Link.empty: remove_all(link.rest, value) if link.rest.first == value: link.rest = link.rest.rest

Use Ok to test your code:

python3 ok -q remove_all

Q7: Mutable Mapping

Implement deep_map_mut(fn, link), which applies a function fn onto all elements in the given linked list link. If an element is itself a linked list, apply fn to each of its elements, and so on.

Your implementation should mutate the original linked list. Do not create any new linked lists.

Hint: The built-in isinstance function may be useful.

>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> isinstance(s, Link)
True
>>> isinstance(s, int)
False
def deep_map_mut(fn, link):
    """Mutates a deep link by replacing each item found with the
    result of calling fn on the item.  Does NOT create new Links (so
    no use of Link's constructor)

    Does not return the modified Link object.

    >>> link1 = Link(3, Link(Link(4), Link(5, Link(6))))
    >>> deep_map_mut(lambda x: x * x, link1)
    >>> print(link1)
    <9 <16> 25 36>
    """
"*** YOUR CODE HERE ***"
if link is Link.empty: return elif isinstance(link.first, Link): deep_map_mut(fn, link.first) else: link.first = fn(link.first) deep_map_mut(fn, link.rest)

Use Ok to test your code:

python3 ok -q deep_map_mut

Q8: Cycles

The Link class can represent lists with cycles. That is, a list may contain itself as a sublist.

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

Implement has_cycle,that returns whether its argument, a Link instance, contains a cycle.

Hint: Iterate through the linked list and try keeping track of which Link objects you've already seen.

def has_cycle(link):
    """Return whether link contains a cycle.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.rest.rest.rest = s
    >>> has_cycle(s)
    True
    >>> t = Link(1, Link(2, Link(3)))
    >>> has_cycle(t)
    False
    >>> u = Link(2, Link(2, Link(2)))
    >>> has_cycle(u)
    False
    """
"*** YOUR CODE HERE ***"
links = [] while link is not Link.empty: if link in links: return True links.append(link) link = link.rest return False

Use Ok to test your code:

python3 ok -q has_cycle

As an extra challenge, implement has_cycle_constant with only constant space. (If you followed the hint above, you will use linear space.) The solution is short (less than 20 lines of code), but requires a clever idea. Try to discover the solution yourself before asking around:

def has_cycle_constant(link):
    """Return whether link contains a cycle.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.rest.rest.rest = s
    >>> has_cycle_constant(s)
    True
    >>> t = Link(1, Link(2, Link(3)))
    >>> has_cycle_constant(t)
    False
    """
"*** YOUR CODE HERE ***"
if link is Link.empty: return False slow, fast = link, link.rest while fast is not Link.empty: if fast.rest == Link.empty: return False elif fast is slow or fast.rest is slow: return True else: slow, fast = slow.rest, fast.rest.rest return False

Use Ok to test your code:

python3 ok -q has_cycle_constant

Tree Practice

Q9: Reverse Other

Write a function reverse_other that mutates the tree such that nodes on every other (even_indexed) level have the labels of their branches all reversed. For example Tree(1,[Tree(2), Tree(3)]) becomes Tree(1,[Tree(3), Tree(2)])

def reverse_other(t):
    """Mutates the tree such that nodes on every other (even_indexed) level
    have the labels of their branches all reversed.

    >>> t = Tree(1, [Tree(2), Tree(3), Tree(4)])
    >>> reverse_other(t)
    >>> t
    Tree(1, [Tree(4), Tree(3), Tree(2)])
    >>> t = Tree(1, [Tree(2, [Tree(3, [Tree(4), Tree(5)]), Tree(6, [Tree(7)])]), Tree(8)])
    >>> reverse_other(t)
    >>> t
    Tree(1, [Tree(8, [Tree(3, [Tree(5), Tree(4)]), Tree(6, [Tree(7)])]), Tree(2)])
    """
"*** YOUR CODE HERE ***"
def reverse_helper(t, need_reverse): if t.is_leaf(): return new_labs = [child.label for child in t.branches][::-1] for i in range(len(t.branches)): child = t.branches[i] reverse_helper(child, not need_reverse) if need_reverse: child.label = new_labs[i] reverse_helper(t, True)

Use Ok to test your code:

python3 ok -q reverse_other