Discussion 7: Mutable Trees, Linked Lists

• disc07.pdf

This is an online worksheet that you can work on during discussions. Your work is not graded and you do not need to submit anything.

Mutable Trees

We define a tree to be a recursive data abstraction that has a label (the value stored in the root of the tree) and branches (a list of trees directly underneath the root).

Previously we implemented trees by using a functional data abstraction, with the tree constructor function and the label and branches selector functions. Now we implement trees by creating the Tree class. Here is part of the class included in the lab.

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

    def is_leaf(self):
        return not self.branches

Even though this is a new implementation, everything we know about the functional tree data abstraction remains true. That means that solving problems involving trees as objects uses the same techniques that we developed when first studying the functional tree data abstraction (e.g. we can still use recursion on the branches!). The main difference, aside from syntax, is that tree objects are mutable.

Here is a summary of the differences between the tree data abstraction implemented as a functional abstraction vs. implemented as class:

Q1: WWPD: Trees

What would Python display?

>>> t = Tree(1, Tree(2))

Your Answer:

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

Your Answer:

>>> t.label *= 4
>>> t

Your Answer:

>>> t.branches[0]

Your Answer:

>>> t.branches[0].label

Your Answer:

>>> t.label = t.branches[0].label
>>> t

Your Answer:

>>> t.branches.append(Tree(4, [Tree(8)]))
>>> len(t.branches)

Your Answer:

>>> t.branches[0]

Your Answer:

>>> t.branches[1]

Your Answer:

Q2: Cumulative Mul

Write a function cumulative_mul that mutates the Tree t so that each node's label becomes the product of its label and all labels in the subtrees rooted at the node.

Think carefully about whether the mutation of tree should happen before or after processing the subtrees!

Run in 61A Code

Q3: Prune Small

Complete the function prune_small that takes in a Tree t and a number n and prunes t mutatively. If t or any of its branches has more than n branches, the n branches with the smallest labels should be kept and any other branches should be pruned, or removed, from the tree.

Run in 61A Code

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

To check if a linked list is empty, compare it against the class attribute Link.empty.

Q4: WWPD: Linked Lists

What would Python display? If you get stuck, try drawing out or visualizing the box-and-pointer diagram!

>>> link = Link(1, Link(2, Link(3)))
>>> link.first

Your Answer:

>>> link.rest.first

Your Answer:

>>> link.rest.rest.rest is Link.empty

Your Answer:

>>> link.rest = link.rest.rest
>>> link.rest.first

Your Answer:

>>> link = Link(1)
>>> link.rest = link
>>> link.rest.rest.rest.rest.first

Your Answer:

>>> link = Link(2, Link(3, Link(4)))
>>> link2 = Link(1, link)
>>> link2.rest.first

Your Answer:

>>> link = Link(1000, 2000)

Your Answer:

>>> link = Link(1000, Link())

Your Answer:

>>> link = Link(Link("Hello"), Link(2))
>>> link.first

Your Answer:

>>> link = Link(Link("Hello"), Link(2))
>>> link.first.rest is Link.Empty

Your Answer:

Q5: Convert Link

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

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

Challenge: Use the type built-in to implement a solution for the case where the list may not be shallow!

Run in 61A Code

Q6: Duplicate Link

Write a function duplicate_link that takes in a linked list link and a value. duplicate_link will mutate link such that if there is a linked list node that has a first equal to value, that node will be duplicated. Note that you should be mutating the original link list link; you will need to create new Links, but you should not be returning a new linked list.

Note: In order to insert a link into a linked list, you need to modify the .rest of certain links. We encourage you to draw out a doctest to visualize!

Run in 61A Code

Q7: 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.

Note: Can you create a recursive and iterative solution for remove_all?

Run in 61A Code