Homework 9
Due at 11:59:59 pm on Thursday, 11/10/2022.

hw09.zip

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:

Linked Lists

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 = Link(1, Link(2, Link(3)))
    >>> s
    Link(1, Link(2, Link(3)))
    """
    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 = ''
        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. For example, the below function 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!')

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.

    >>> link = Link(1, Link(2, Link(3, Link(4))))
    >>> link_to_list(link)
    [1, 2, 3, 4]
    >>> link_to_list(Link(88))
    [88]
    >>> link_to_list(Link.empty)
    []
    """
    "*** 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
Link('a', Link('c'))
>>> 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).

    >>> s = Link(1, Link(2, Link(3, Link(4))))
    >>> every_other(s) # removes 2, 4
    >>> s
    Link(1, Link(3))
    >>> odd_length = Link(5, Link(3, Link(1)))
    >>> every_other(odd_length) # removes 3
    >>> odd_length
    Link(5, Link(1))
    >>> two_items = Link(6, Link(7))
    >>> every_other(two_items) # removes 7
    >>> two_items
    Link(6)
    >>> singleton = Link(4)
    >>> every_other(singleton) # doesn't remove anything
    >>> singleton
    Link(4)
    """
    "*** 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).

    >>> link = Link(3, Link(1, Link(4, Link(1, Link(5, Link(9))))))
    >>> new = slice_link(link, 1, 4)
    >>> new
    Link(1, Link(4, Link(1)))
    >>> link2 = slice_link(Link(1), 0, 1)
    >>> link2
    Link(1)
    >>> link3 = slice_link(Link.empty, 0, 0)
    >>> link3
    ()
    """
    "*** 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.

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