Homework 8 Solutions | C88C Summer 2024

Inheritance

Question 1: Errors

It is often said that nothing in life is certain but death and taxes. For a programmer or data scientist, however, nothing is certain but encountering errors.

In Python, there are two primary types of errors, both of which you are likely familiar with: syntax errors and exceptions. Syntax errors occur when the proper structure of the language is not followed, while exceptions are errors that occur during the execution of a program. These include errors such as ZeroDivisionError, TypeError, NameError, and many more!

Under the hood, all exceptions are objects. If you're interested in more detailed explanations of the structure of exceptions as well as how to create your own, check out this article from the Python documentation! In the meantime, we'll implement our own version of an Error class

Complete the Error, SyntaxError, and ZeroDivisionError classes such that they create the correct messages when called.

The SyntaxError and ZeroDivisionError classes inherit from the Error class and add functionality that is unique to those particular errors. Their code is partially implemented for you.
The add_code method adds a new helpful message to your error, while the write method should print the output that you see when an error is raised. Do not worry if that code already is already defined; for this problem, it is safe to overwrite it.
You can access the parent class methods using the super() function

class Error:
    """
    >>> err1 = Error(12, "error.py")
    >>> err1.write()
    error.py:12
    """
    def __init__(self, line, file):
        self.line = line
        self.file = file

    def format(self):
        return self.file + ':' + str(self.line)

    def write(self):
        print(self.format())

class SyntaxError(Error):
    """
    >>> err1 = SyntaxError(17, "lab10.py")
    >>> err1.write()
    lab10.py:17 SyntaxError : Invalid syntax
    >>> err1.add_code(4, "EOL while scanning string literal")
    >>> err2 = SyntaxError(18, "lab10.py", 4)
    >>> err2.write()
    lab10.py:18 SyntaxError : EOL while scanning string literal
    """
    type = 'SyntaxError'
    msgs = {0 : "Invalid syntax", 1: "Unmatched parentheses", 2: "Incorrect indentation", 3: "missing colon"}

    def __init__(self, line, file, code=0):
        super().__init__(line, file)
        self.message = self.msgs[code]

    def format(self):
        return super().format() + ' ' + self.type + " : " + self.message # or SyntaxError.msgs[self.code]

    def add_code(self, code, msg):
        SyntaxError.msgs[code] = msg

class ZeroDivisionError(Error):
    """
    >>> err1 = ZeroDivisionError(273, "lab10.py")
    >>> err1.write()
    lab10.py:273 ZeroDivisionError : division by zero
    """
    type = 'ZeroDivisionError'

    def __init__(self, line, file, message='division by zero'):
        super().__init__(line, file)
        self.message = message

    def format(self):
        end = self.type + ' : ' + self.message
        return super().format() + " " + end

Use OK to test your code:

python3 ok -q Error

Use OK to test your code:

python3 ok -q SyntaxError

Use OK to test your code:

python3 ok -q ZeroDivisionError

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

    >>> 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)
    []
    """
    # 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

Use OK to test your code:

python3 ok -q link_to_list

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

IMPORTANT NOTES:

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

We refer to indexing in the problem statement to make it clear which elements should be removed, but remember that you cannot access elements from a linked list using indices

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)
    """
    if s is Link.empty or s.rest is Link.empty:
        return
    else:
        s.rest = s.rest.rest
        every_other(s.rest)

Use OK to test your code:

python3 ok -q every_other

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.

The isinstance function returns True if the first argument's type matches the second argument. For example:

>>> isinstance('hello', str)
True
>>> isinstance('hello', int)
False

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>>>
    """
    if link is Link.empty:
        return link
    if isinstance(link.first, Link):
        first = deep_map(f, link.first)
    else:
        first = f(link.first)
    return Link(first, deep_map(f, link.rest))

Use OK to test your code:

python3 ok -q deep_map