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.


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.

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:

    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        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:
    print('This linked list is 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)))
>>> link.first
>>> link.rest.first
>>> link.rest.rest.rest is Link.empty
>>> link.first = 9001 >>> link.first
>>> link.rest = link.rest.rest >>> link.rest.first
>>> link = Link(1) >>> link.rest = link >>> link.rest.rest.rest.rest.first

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

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.

    >>> link = list_to_link([1, 2, 3])
    >>> print_link(link)
    <1 2 3>
"*** YOUR CODE HERE ***"
if not lst: return Link.empty else: return Link(lst[0], list_to_link(lst[1:]))

Use OK to test your code:

python3 ok -q list_to_link

Mutable Linked Lists

Mutable Linked Lists Regular Linked Lists
Traits - Represented with custom object, Link
- Has methods and attributes
- Mutable
- Represented with abstract data type
- Has selector functions
- Not mutable
>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> s
Link(1, Link(2, Link(3, Link(4))))
>>> s.first = 9
>>> s
Link(9, Link(2, Link(3, Link(4))))
>>> 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.

Your implementation should mutate the original linked list. Do not create any new linked lists.

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

>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> isinstance(s, Link)
>>> isinstance(s, int)
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
    no use of Link's constructor)

    Does not return the modified Link object.

    >>> link1 = Link(3, Link(Link(4), Link(5, Link(6))))
    >>> deep_map_mut(lambda x: x * x, link1)
    >>> print_link(link1)
    <9 <16> 25 36>
"*** YOUR CODE HERE ***"
if link is Link.empty: return elif isinstance(link.first, Link): deep_map_mut(fn, link.first) else: link.first = fn(link.first) deep_map_mut(fn, link.rest)

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.

    >>> link = Link(1, Link(2, Link(3)))
    >>> insert(link, 9001, 0)
    >>> print_link(link)
    <9001 1 2 3>
    >>> insert(link, 100, 2)
    >>> print_link(link)
    <9001 1 100 2 3>
    >>> insert(link, 4, 5)
"*** YOUR CODE HERE ***"
if index == 0: link.rest = Link(link.first, link.rest) link.first = value elif link.rest is Link.empty: raise IndexError 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: 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.

    >>> print_link(reverse(Link(1)))
    >>> link = Link(1, Link(2, Link(3)))
    >>> new = reverse(link)
    >>> print_link(new)
    <3 2 1>
    >>> print_link(link)
    <1 2 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 # Recursive solution def reverse(link): def reverse_to(link, t): if link is Link.empty: return t else: return reverse_to(link.rest, Link(link.first, t)) return reverse_to(link, Link.empty)

Use OK to test your code:

python3 ok -q reverse

Question 7: Add Links

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.

def add_links(link1, link2):
    """Adds two Links, returning a new Link

    >>> l1 = Link(1, Link(2))  
    >>> l2 = Link(3, Link(4, Link(5)))
    >>> new = add_links(l1,l2)
    >>> print_link(new)
    <1 2 3 4 5>
"*** YOUR CODE HERE ***"
if link1 is not Link.empty: return Link(link1.first, add_links(link1.rest, link2)) elif link2 is not Link.empty: return Link(link2.first, add_links(link1, link2.rest)) else: return Link.empty # Iterative version (using reverse) def add_links(link1, link2): result = Link.empty while link1 is not Link.empty: result = Link(link1.first, result) link1 = link1.rest while link2 is not Link.empty: result = Link(link2.first, result) link2 = link2.rest 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).

    >>> link = Link(3, Link(1, Link(4, Link(1, Link(5, Link(9))))))
    >>> new = slice_link(link, 1, 4)
    >>> print_link(new)
    <1 4 1>
"*** YOUR CODE HERE ***"
if end == 0: return Link.empty elif start == 0: return Link(link.first, slice_link(link.rest, 0, end-1)) else: return slice_link(link.rest, start-1, end-1)

Use OK to test your code:

python3 ok -q slice_link