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

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.

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:
"""A linked list.
>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> len(s)
4
>>> s[2]
3
>>> s
Link(1, Link(2, Link(3, Link(4))))
"""
empty = ()
def __init__(self, first, rest=empty):
assert rest is Link.empty or isinstance(rest, Link)
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):
if self.rest is not Link.empty:
rest_str = ', ' + repr(self.rest)
else:
rest_str = ''
return 'Link({0}{1})'.format(repr(self.first), rest_str)
```

To check if a `Link`

is empty, compare it against the class attribute
`Link.empty`

:

```
if link is Link.empty:
print('This linked list is empty!')
```

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

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

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.
>>> link = Link(1, Link(2, Link(3)))
>>> insert(link, 9001, 0)
>>> link
Link(9001, Link(1, Link(2, Link(3))))
>>> insert(link, 100, 2)
>>> link
Link(9001, Link(1, Link(100, Link(2, Link(3)))))
>>> insert(link, 4, 5)
Index out of bounds!
"""
"*** YOUR CODE HERE ***"
if index == 0:
link.rest = Link(link.first, link.rest)
link.first = value
elif link.rest is Link.empty:
print('Index out of bounds!')
else:
insert(link.rest, value, index - 1)
# iterative solution
def insert(link, value, index):
while index > 0 and link.rest is not Link.empty:
link = link.rest
index -= 1
if index == 0:
link.rest = Link(link.first, link.rest)
link.first = value
else:
print('Index out of bounds!')
```

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

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

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)])
"""
"*** YOUR CODE HERE ***"
t.entry = t.entry ** 2
for subtree in t.branches:
square_tree(subtree)
```

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.

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.
>>> list_to_link([1, 2, 3])
Link(1, Link(2, Link(3)))
"""
"*** YOUR CODE HERE ***"
if not lst:
return Link.empty
else:
return Link(lst[0], list_to_link(lst[1:]))
```

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

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.
>>> reverse(Link(1))
Link(1)
>>> link = Link(1, Link(2, Link(3)))
>>> reverse(link)
Link(3, Link(2, Link(1)))
>>> link
Link(1, Link(2, Link(3)))
"""
"*** YOUR CODE HERE ***"
new = Link(link.first)
while link.rest is not Link.empty:
link = link.rest
new = Link(link.first, new)
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.
>>> link = Link(1)
>>> mutate_reverse(link)
>>> link
Link(1)
>>> link = Link(1, Link(2, Link(3)))
>>> mutate_reverse(link)
>>> link
Link(3, Link(2, Link(1)))
"""
"*** YOUR CODE HERE ***"
if link is Link.empty or link.rest is Link.empty:
return
mutate_reverse(link.rest)
while link.rest is not Link.empty:
link.first, link.rest.first = link.rest.first, link.first
link = link.rest
```

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]
"""
"*** YOUR CODE HERE ***"
if t.is_leaf():
return [t.entry]
all_leaves = []
for b in t.branches:
all_leaves += leaves(b)
return all_leaves
```

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)
"""
"*** YOUR CODE HERE ***"
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)
```

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
"""
"*** YOUR CODE HERE ***"
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):
if link is Link.empty:
return <Base case>
else:
return <Expression involving func(link.rest)>
```

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.

Write the left fold function by filling in the blanks.

```
def foldl(link, fn, z):
""" Left fold
>>> lst = Link(3, Link(2, Link(1)))
>>> 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
"""
if link is Link.empty:
return z
"*** YOUR CODE HERE ***"
return foldl(______, ______, ______)
return foldl(link.rest, fn, fn(z, link.first))
```

Now write the right fold function.

```
def foldr(link, fn, z):
""" Right fold
>>> lst = Link(3, Link(2, Link(1)))
>>> 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
"""
"*** YOUR CODE HERE ***"
if link is Link.empty:
return z
return fn(link.first, foldr(link.rest, fn, z))
```

Write `foldl`

using `foldr`

! You only need to fill in the `step`

function.

```
identity = lambda x: x
def foldl2(link, fn, z):
""" Write foldl using foldr
>>> list = Link(3, Link(2, Link(1)))
>>> foldl2(list, sub, 0) # (((0 - 3) - 2) - 1)
-6
>>> foldl2(list, add, 0) # (((0 + 3) + 2) + 1)
6
>>> foldl2(list, mul, 1) # (((1 * 3) * 2) * 1)
6
"""
def step(x, g):
"*** YOUR CODE HERE ***"
return lambda a: g(fn(a, x)) return foldr(link, step, identity)(z)
```