# Lab 7: Recursive Objects

Due at 11:59pm on 03/12/2015.

## 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 2 and 4 in lab07.py and submit through OK.
• Questions 5 through 13 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.

A linked list is either an empty linked list (`Link.empty`) or a first value and the rest of the linked list.

``````class Link:

>>> len(s)
4
>>> s[2]
3
>>> s
"""
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):
rest_str = ', ' + repr(self.rest)
else:
rest_str = ''

To check if a `Link` is empty, compare it against the class attribute `Link.empty`:

``````if link is Link.empty:

### Question 1

Predict what Python will display when the following lines are typed into the interpreter:

``````>>> Link()
______TypeError
______1
______2
______True
______9001
______3
______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.

Index out of bounds!
"""
if index == 0:
print('Index out of bounds!')
else:

# iterative solution
index -= 1
if index == 0:
else:
print('Index out of bounds!')``````

## Trees

As we saw in lecture, we can also represent trees as objects.

``````class Tree:
def __init__(self, entry, branches=()):
self.entry = entry
for branch in branches:
assert isinstance(branch, Tree)
self.branches = branches

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

def is_leaf(self):
return not self.branches``````

### Question 3

Predict what Python will display when the following lines are typed into the interpreter:

``````>>> t = Tree(1, Tree(2))
______TypeError
>>> t = Tree(1, [Tree(2)])
>>> t.entry
______1
>>> t.branches[0]
______Tree(2)
>>> t.branches[0].entry
______2
>>> t.entry = t.branches[0].entry
>>> 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)])``````

### Question 4

Write a function `square_tree` that mutates a `Tree` with numerical entries so that each entry is squared.

``````def square_tree(t):
"""Mutates a Tree t by squaring all its elements.

>>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
>>> square_tree(t)
>>> t
Tree(1, [Tree(9, [Tree(25)]), Tree(49)])
"""
t.entry = t.entry ** 2
for subtree in t.branches:
square_tree(subtree)``````

## Extra Questions

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

### Question 5

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.

"""
if not lst:
else:

### Question 6

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.

[1, 2, 3, 4]
[]
"""
# Recursive solution
return []

# Iterative solution
result = []
return result``````

### Question 7

Implement a function `reverse` that reverses a given `Link`. `reverse` should return a new `Link` that is the reverse of the original, without modifying the original.

``````def reverse(link):
"""Returns a Link that is the reverse of the original.

"""
return new``````

Extra for experts: Implement `mutate_reverse`, a recursive mutating version of `reverse`. Have it mutate the original `Link` so that its elements are reversed.

``````def mutate_reverse(link):
"""Mutates the Link so that its elements are reversed.

"""
return

### Question 8

Write a function `leaves` that returns a list of all the entries of the leaf nodes of a `Tree`.

``````def leaves(t):
"""Returns a list of all the entries of the leaf nodes of the Tree t.

>>> leaves(Tree(1))
[1]
>>> leaves(Tree(1, [Tree(2, [Tree(3)]), Tree(4)]))
[3, 4]
"""
if t.is_leaf():
return [t.entry]
all_leaves = []
for b in t.branches:
all_leaves += leaves(b)
return all_leaves``````

### Question 9

Write a function `cumulative_sum` that returns a new `Tree`, where each entry is the sum of all entries in the corresponding subtree of the old `Tree`.

``````def cumulative_sum(t):
"""Return a new Tree, where each entry is the sum of all entries in the
corresponding subtree of t.

>>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
>>> cumulative = cumulative_sum(t)
>>> t
Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
>>> cumulative
Tree(16, [Tree(8, [Tree(5)]), Tree(7)])
>>> cumulative_sum(Tree(1))
Tree(1)
"""
branches = [cumulative_sum(st) for st in t.branches]
new_entry = sum(st.entry for st in branches) + t.entry
return Tree(new_entry, branches)``````

### Question 10

Write a function `same_shape` that returns `True` if two `Tree`s have the same shape. Two trees have the same shape if they have the same number of children and each of their children have the same shape.

``````def same_shape(t1, t2):
"""Returns whether two Trees t1, t2 have the same shape. Two trees have the
same shape if they have the same number of branches and each of their
children have the same shape.

>>> t, s = Tree(1), Tree(3)
>>> same_shape(t, t)
True
>>> same_shape(t, s)
True
>>> t = Tree(1, [Tree(2), Tree(3)])
>>> same_shape(t, s)
False
>>> s = cumulative_sum(t)
>>> same_shape(t, s)
True
"""
return len(t1.branches) == len(t2.branches) and \
all(same_shape(st1, st2) for st1, st2 in zip(t1.branches, t2.branches))``````

When we write recursive functions acting on `Link`s, we often find that they have the following form:

``````def func(link):
return <Base case>
else:

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:

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

Also notice that a left fold is equivalent to Python's `reduce` with a starting value.

### Question 11

Write the left fold function by filling in the blanks.

``````def foldl(link, fn, z):
""" Left fold
>>> 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
"""
return z
return foldl(______, ______, ______)

### Question 12

Now write the right fold function.

``````def foldr(link, fn, z):
""" Right fold
>>> 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
"""
return z

### Question 13: Extra for Experts

Write `foldl` using `foldr`! You only need to fill in the `step` function.

``````identity = lambda x: x