Lab 7: Recursive Objects

Due at 11:59pm on Friday, 10/14/2016.

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.

  • 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.

Linked Lists

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 link.py:

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.

Question 1: 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 lab07.py.

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

Question 2: List to Link

Write a function list_to_link that converts a Python list to a Link.

def list_to_link(lst):
    """Takes a Python list and returns a Link with the same elements.

    >>> link = list_to_link([1, 2, 3])
    >>> print_link(link)
    <1 2 3>
    """

    "*** YOUR CODE HERE ***"

    if not lst:
        return Link.empty
    else:
        return Link(lst[0], list_to_link(lst[1:]))

Use OK to test your code:

python3 ok -q list_to_link

Question 3: Link to List

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

Question 4: Remove All

Implement a function remove_all that takes a Link, and a value, and remove any 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_link(l1)
    <0 2 2 3 1 2 3>
    >>> remove_all(l1, 2)
    >>> print_link(l1)
    <0 3 1 3>
    >>> remove_all(l1, 3)
    >>> print_link(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

Trees (Again)

Just like Linked Lists, we can also represent Trees as objects.

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

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

    def is_leaf(self):
        return not self.branches

def print_tree(t, indent=0):
    """Print a representation of this tree in which each node is
    indented by two spaces times its depth from the entry.

    >>> print_tree(Tree(1))
    1
    >>> print_tree(Tree(1, [Tree(2)]))
    1
      2
    >>> numbers = Tree(1, [Tree(2), Tree(3, [Tree(4), Tree(5)]), Tree(6, [Tree(7)])])
    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    """
    print('  ' * indent + str(t.root))
    for b in t.branches:
        print_tree(b, indent + 1)

Question 5: WWPD: Trees

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

python3 ok -q trees -u

Hint: Remember for all WWPD questions, enter Function if you believe the answer is <function ...> and Error if it errors.

>>> from lab07 import *
>>> t = Tree(1, Tree(2))

______
Error

>>> t = Tree(1, [Tree(2)])
>>> t.root

______
1

>>> t.branches[0]

______
Tree(2)

>>> t.branches[0].root

______
2

>>> t.root = t.branches[0].root
>>> 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)])

Extra 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.

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 term, you'll be programming in Scheme, which is a programming language that uses linked lists for almost everything. During lecture, you know that certain operations are faster with linked lists comparing to python-lists. Here you will test out those theories in practice.

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

To test this, in your terminal, enter the following command: python3 timing.py insert 100000, which inserts 100,000 items into the beginning of both a linked list and a Python built-in list to compare the speed.

Now, say we want the item at index 3.

  • In the built-in list, you can simply grab the item from the container with 3 labeled on it;
  • In the linked list, you need to start at the first item, and go to its neighbor's neighbor's neighbor to finally reach the item at index 3.

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

Question 6: Reverse Other

Write a function reverse_other that mutates the tree such that every other (odd_indexed) level of the tree's roots are all reversed. For example Tree(1,[Tree(2), Tree(3)]) becomes Tree(1,[Tree(3), Tree(2)])

def reverse_other(t):
    """Reverse the roots of every other level of the tree using mutation.

    >>> 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(5, [Tree(7), Tree(8)]), Tree(6)]), Tree(3)])
    >>> reverse_other(t)
    >>> t
    Tree(1, [Tree(3, [Tree(5, [Tree(8), Tree(7)]), Tree(6)]), Tree(2)])
    """

    "*** YOUR CODE HERE ***"

    def reverse_helper(t, need_reverse):
        if t.is_leaf():
            return
        new_labs = [child.root 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.root = new_labs[i]
    reverse_helper(t, True)

Use OK to test your code:

python3 ok -q reverse_other

Question 7: Cumulative Sum

Write a function cumulative_sum that mutates the Tree t, where each node's root 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.root = sum([st.root for st in t.branches]) + t.root

Use OK to test your code:

python3 ok -q cumulative_sum

Question 8: 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_link(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

Question 9: 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

Extra question: This question is not worth extra credit and is entirely optional. It is designed to challenge you to think creatively!

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 == slow or fast.rest == 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