# Lab 7: Recursive Objects

*Due at 11:59pm on Friday, 10/12/2018.*

*Lab Check-in 4 questions here.*

## 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 2 through 8 in lab07.py and submit through OK.
- Questions 9 through 12 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

## Check-Off

### Q1: A-Okay

Sign up for checkoffs in your lab if you'd like to get credit for this week's checkoff.

What happens in the following code? Make sure you can explain *why* each line works or breaks.

```
>>> class A:
... y = 1
... def __init__(self, y):
... self.y = y
... def f(self, x):
... self.y += x
...
>>> a = A(0) # Ok or not okay?
>>> a.f(6) # Ok or not okay?
>>> a.f(A, 9) # Ok or not okay?
>>> A.f(a, 4) # Ok or not okay?
>>> A.f(A, 4) # Ok or not okay?
```

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

- An empty linked list (
`Link.empty`

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

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

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

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

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;

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

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)

Recall that a tree is a recursive abstract 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).

We saw one way to implement the tree ADT -- using constructor and selector
functions that treat trees as lists. Another, more formal, way to implement the
tree ADT is with a class. Here is part of the class definition for `Tree`

,
which can be found in `lab07.py`

:

```
class Tree:
"""
>>> t = Tree(3, [Tree(2, [Tree(5)]), Tree(4)])
>>> t.label
3
>>> t.branches[0].label
2
>>> t.branches[1].is_leaf()
True
"""
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 tree ADT remains true. That means that solving problems involving trees as objects uses the same techniques that we developed when first studying the tree ADT (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 ADT implemented using functions and lists vs. implemented using a class:

- | Tree constructor and selector functions | Tree class |
---|---|---|

Constructing a tree | To construct a tree given a `label` and a list of `branches` , we call `tree(label, branches)` |
To construct a tree object given a `label` and a list of `branches` , we call `Tree(label, branches)` (which calls the `Tree.__init__` method) |

Label and branches | To get the label or branches of a tree `t` , we call `label(t)` or `branches(t)` respectively |
To get the label or branches of a tree `t` , we access the instance attributes `t.label` or `t.branches` respectively |

Mutability | The tree ADT is immutable because we cannot assign values to call expressions | The `label` and `branches` attributes of a `Tree` instance can be reassigned, mutating the tree |

Checking if a tree is a leaf | To check whether a tree `t` is a leaf, we call the convenience function `is_leaf(t)` |
To check whether a tree `t` is a leaf, we call the bound method `t.is_leaf()` . This method can only be called on `Tree` objects. |

# Required Questions

## What Would Python Display?

### Q2: 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>
```

### Q3: 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. Recall that`Tree`

instances will be displayed the same way they are constructed.

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

### Q4: 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
Video walkthrough: https://youtu.be/hdO9Ry8d5FU?t=25m6s
```

Use Ok to test your code:

`python3 ok -q link_to_list`

### Q5: 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`

### Q6: Cumulative Sum

Write a function `cumulative_sum`

that mutates the Tree `t`

so that each node's
label becomes the sum of all labels in the subtree rooted at the node.

```
def cumulative_sum(t):
"""Mutates t so that each node's label becomes the sum of all labels 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 b in t.branches:
cumulative_sum(b)
t.label = sum([b.label for b in t.branches]) + t.label
```

Use Ok to test your code:

`python3 ok -q cumulative_sum`

## Midterm Review (required)

### Q7: Is BST

Write a function `is_bst`

, which takes a Tree `t`

and returns `True`

if, and
only if, `t`

is a valid binary search tree, which means that:

- Each node has at most two children (a leaf is automatically a valid binary search tree)
- The children are valid binary search trees
- For every node, the entries in that node's left child are less than or equal to the label of the node
- For every node, the entries in that node's right child are greater than the label of the node

Note that, if a node has only one child, that child could be considered either
the left or right child. You should take this into consideration. **Do not use
the** `BST`

**constructor or anything from the** `BST`

**class.**

*Hint:* It may be helpful to write helper functions `bst_min`

and `bst_max`

that
return the minimum and maximum, respectively, of a Tree if it is a valid binary
search tree.

```
def is_bst(t):
"""Returns True if the Tree t has the structure of a valid BST.
>>> t1 = Tree(6, [Tree(2, [Tree(1), Tree(4)]), Tree(7, [Tree(7), Tree(8)])])
>>> is_bst(t1)
True
>>> t2 = Tree(8, [Tree(2, [Tree(9), Tree(1)]), Tree(3, [Tree(6)]), Tree(5)])
>>> is_bst(t2)
False
>>> t3 = Tree(6, [Tree(2, [Tree(4), Tree(1)]), Tree(7, [Tree(7), Tree(8)])])
>>> is_bst(t3)
False
>>> t4 = Tree(1, [Tree(2, [Tree(3, [Tree(4)])])])
>>> is_bst(t4)
True
>>> t5 = Tree(1, [Tree(0, [Tree(-1, [Tree(-2)])])])
>>> is_bst(t5)
True
>>> t6 = Tree(1, [Tree(4, [Tree(2, [Tree(3)])])])
>>> is_bst(t6)
True
>>> t7 = Tree(2, [Tree(1, [Tree(5)]), Tree(4)])
>>> is_bst(t7)
False
"""
"*** YOUR CODE HERE ***"
def bst_min(t):
"""Returns the min of t, if t has the structure of a valid BST."""
if t.is_leaf():
return t.label
return min(t.label, bst_min(t.branches[0]))
def bst_max(t):
"""Returns the max of t, if t has the structure of a valid BST."""
if t.is_leaf():
return t.label
return max(t.label, bst_max(t.branches[-1]))
if t.is_leaf():
return True
if len(t.branches) == 1:
c = t.branches[0]
return is_bst(c) and (bst_max(c) <= t.label or bst_min(c) > t.label)
elif len(t.branches) == 2:
c1, c2 = t.branches
valid_branches = is_bst(c1) and is_bst(c2)
return valid_branches and bst_max(c1) <= t.label and bst_min(c2) > t.label
else:
return False
```

Use Ok to test your code:

`python3 ok -q is_bst`

### Q8: In-order traversal

Write a function that returns a generator that generates an "in-order" traversal, in which we yield the value of every node in order from left to right, assuming that each node has either 0 or 2 branches.

```
def in_order_traversal(t):
"""
Generator function that generates an "in-order" traversal, in which we
yield the value of every node in order from left to right, assuming that each node has either 0 or 2 branches.
For example, take the following tree t:
1
2 3
4 5
6 7
We have the in-order-traversal 4, 2, 6, 5, 7, 1, 3
>>> t = Tree(1, [Tree(2, [Tree(4), Tree(5, [Tree(6), Tree(7)])]), Tree(3)])
>>> list(in_order_traversal(t))
[4, 2, 6, 5, 7, 1, 3]
"""
"*** YOUR CODE HERE ***"
if t.is_leaf():
yield t.label
else:
left, right = t.branches
yield from in_order_traversal(left)
yield t.label
yield from in_order_traversal(right)
```

Use Ok to test your code:

`python3 ok -q in_order_traversal`

# 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

### Q9: 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
Video walkthrough: https://youtu.be/hdO9Ry8d5FU?t=39m33s
```

Use Ok to test your code:

`python3 ok -q remove_all`

### Q10: 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`

### Q11: 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

### Q12: Reverse Other

Write a function `reverse_other`

that mutates the tree such that **labels** on
*every other* (odd-depth) level are reversed. For example,
`Tree(1,[Tree(2, [Tree(4)]), Tree(3)])`

becomes `Tree(1,[Tree(3, [Tree(4)]), Tree(2)])`

.
Notice that the nodes themselves are *not* reversed; only the labels are.

```
def reverse_other(t):
"""Mutates the tree such that nodes on every other (odd-depth) 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`