## Instructions

Download hw09.zip. Inside the archive, you will find starter files for the questions in this homework, along with a copy of the OK autograder.

Submission: When you are done, submit with `python3 ok --submit`. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on okpy.org.

Readings: This homework relies on following references:

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

``````class Link:
"""
>>> s
"""
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_str = ', ' + repr(self.rest)
else:
rest_str = ''

To check if a `Link` is empty, compare it against the class attribute `Link.empty`. For example, the below function prints out whether or not the link it is handed is empty:

``````def test_empty(link):
print('This linked list is empty!')
else:
print('This linked list is not empty!')``````

Note: Linked lists are recursive data structures! A linked list contains the first element of the list (`first`) and a reference to another linked list (`rest`) which contains the rest of the values in the list.

### Question 1: 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]
[88]
[]
"""
"*** YOUR CODE HERE ***"``````

Use OK to test your code:

``python3 ok -q link_to_list``

### Question 2: Every Other

Implement `every_other`, which takes a linked list `s`. It mutates `s` such that all of the odd-indexed elements (using 0-based indexing) are removed from the list. For example:

``````>>> s = Link('a', Link('b', Link('c', Link('d'))))
>>> every_other(s)
>>> s
>>> s.first
'a'
>>> s.rest.first
'c'
>>> s.rest.rest is Link.empty
True``````

If `s` contains fewer than two elements, `s` remains unchanged.

Do not return anything! `every_other` should mutate the original list.

``````def every_other(s):
"""Mutates a linked list so that all the odd-indiced elements are removed
(using 0-based indexing).

>>> every_other(s) # removes 2, 4
>>> s
>>> every_other(odd_length) # removes 3
>>> odd_length
>>> every_other(two_items) # removes 7
>>> two_items
>>> singleton = Link(4)
>>> every_other(singleton) # doesn't remove anything
>>> singleton
"""
"*** YOUR CODE HERE ***"``````

Use OK to test your code:

``python3 ok -q every_other``

### Question 3: 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 slicing a normal Python list.

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

>>> new
()
"""
"*** YOUR CODE HERE ***"``````

Use OK to test your code:

``python3 ok -q slice_link``

### Question 4: Deep Map

Implement `deep_map`, which takes a function `f` and a `link`. It returns a new linked list with the same structure as `link`, but with `f` applied to any element within `link` or any `Link` instance contained in `link`.

The `deep_map` function should recursively apply `fn` to each of that `Link`'s elements rather than to that `Link` itself.

Hint: You may find the built-in `isinstance` function useful.

``````def deep_map(f, link):
"""Return a Link with the same structure as link but with fn mapped over
its elements. If an element is an instance of a linked list, recursively
apply f inside that linked list as well.

<1 <2 3> 4>
>>> print_link(deep_map(lambda x: x * x, s))
<1 <4 9> 16>
>>> print_link(s) # unchanged
<1 <2 3> 4>
<<1 <2 3> 4> <<5>>>
>>> print_link(deep_map(lambda x: 2 * x, t))
<<2 <4 6> 8> <<10>>>
"""
"*** YOUR CODE HERE ***"``````

Use OK to test your code:

``python3 ok -q deep_map``

## Submit

Make sure to submit this assignment by running:

``python3 ok --submit``