Due at 11:59pm on 07/21/2015.

## Starter Files

Download lab09.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, 3, 4, and 5 in lab09.py and submit through OK. You must also unlock Question 1 (What would Python print?) using OK.
• Questions 6, 7, and 8 are extra practice. They can be found in the lab09_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:

empty = ()

def __init__(self, first, rest=empty):
self.first = first
self.rest = rest``````

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

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

### Question 1: What would Python print?

Use OK to answer this "What would Python print?" question:

``python3 ok -q wwpp -u``

If you get stuck, try typing the lines into an interactive Python session.

``````>>> link = Link(1, Link(2, Link(3)))
______1
______2
______True
______9001
______3
______1``````

### Question 2: 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.

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

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

Use OK to test your code:

``python3 ok -q link_to_list``

### Question 3: 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.

<1 2 3>
"""
if not lst:
else:

Use OK to test your code:

``python3 ok -q list_to_link``

Traits - Represented with custom object, `Link`
- Has methods and attributes
- Mutable
- Represented with abstract data type
- Has selector functions
- Not mutable
Examples
``````>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> s
>>> s.first = 9
>>> s
``````
``````>>> s = link(1, link(2, link(3, link(4))))
>>> s
[1, [2, [3, [4, 'empty']]]]
>>> first(s) = 9
File "", line 1
SyntaxError: can't assign to function call
``````
Explanations `Link` is mutable because we have created an object `Link` with attributes that allow direct access to the elements inside of it. This allows us to change the elements, thus mutating the `Link` `link` is not mutable because its selector functions only return to us the values of its elements. We are not able to change or reassign these values.

### Question 4: 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.

Hint: The built-in `isinstance` function may be useful.

``````>>> s = Link(1, Link(2, Link(3, Link(4))))
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

Does not return the modified Link object.

>>> deep_map_mut(lambda x: x * x, link1)
<9 <16> 25 36>
"""
return
else:

Use OK to test your code:

``python3 ok -q deep_map_mut``

### Question 5: Insert

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.

Note: If the index is out of bounds, raise an `IndexError`

``````def insert(link, value, index):
"""Insert a value into a Link at the given index.

<9001 1 2 3>
<9001 1 100 2 3>
IndexError
"""
if index == 0:
raise IndexError
else:

# iterative solution
index -= 1
if index == 0:
else:
raise IndexError``````

Use OK to test your code:

``python3 ok -q insert``

## Extra Questions

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

### Question 6: Reverse

Implement `reverse`, which takes a linked list `link` and returns a linked list containing the elements of `link` in reverse order. The original `link` should be unchanged.

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

<1>
<3 2 1>
<1 2 3>
"""
return new

# Recursive solution
return t
else:

Use OK to test your code:

``python3 ok -q reverse``

Let's implement a method in order to add together items of `link1` and `link2`. Do not assume that the links are the same length.

Hint: Think about using your `reverse` function here.

``````def add_links(link1, link2):

<1 2 3 4 5>
"""
return reverse(result)``````

Use OK to test your code:

``python3 ok -q add_links``

### Question 8: Slice

Implement a function `slice_link` that slices a given `link`. `slice_link` should slice the `link` starting at `start` and ending one element before `end`, as with a normal Python list.

``````def slice_link(link, start, end):
"""Slices a Link from start to end (as with a normal Python list).

``python3 ok -q slice_link``