Recursive Lists: exam-level questions

If you need help reviewing Recursive Lists, take a look at these resources:

We will be using the following implementation of immutable linked lists. Keep in mind that your code should not depend on the assumption that links are implemented as lists — preserve data abstraction!

empty = None

def link(first, rest=empty):
    return [first, rest]

def first(s):
    return s[0]

def rest(s):
    return s[1]

Each question has a "Toggle Solution" button -- click it to reveal that question's solution.

What would Python print?

Question 1

>>> r = link(1, link(link(2, empty), link(4, empty)))
>>> first(r)
______
>>> first(rest(rest(r)))
______
>>> first(first(rest(r)))
______

Question 2

>>> r = link(link(1, link(2, empty)), link(3, link(4, empty)))
>>> first(rest(r))
______
>>> first(rest(first(r)))
______
>>> first(first(rest(r)))
______

Code-Writing questions

Question 3

Implement a function alternate which takes a linked list and returns a new linked list that contains every other element in the original linked list.

def alternate(lst):
    """Returns a new linked list that contains every other element
    of the original.

    >>> r = link(1, link(2, link(3, empty)))
    >>> link_to_list(alternate(r))
    [1, 3]
    >>> r = link(1, link(2, link(3, link(4, empty))))
    >>> link_to_list(alternate(r))
    [1, 3]
    """
    "*** YOUR CODE HERE ***"
def alternate(r):
    if r == empty:
        return empty
    elif rest(r) == empty:
        return r
    else:
        return link(first(r), alternate(rest(rest(r)))

Question 4

Implement a function filter_link which takes a linked list and returns a new linked list that contains only elements that satisfy the given predicate.

def filter(pred, lst):
    """Returns a new link that contains elements of lst that
    satisfy the predicate.

    >>> r = link(1, link(2, link(3, empty)))
    >>> link_to_list(filter_link(lambda x: x % 2 == 1, r))
    [1, 3]
    >>> r = link(1, link(2, link(3, link(4, empty))))
    >>> link_to_list(filter_link(lambda x: x % 3 == 1, r))
    [1, 4]
    """
    "*** YOUR CODE HERE ***"
def filter(pred, lst):
    if r == empty:
        return empty
    elif pred(first(lst)):
        return link(first(lst), filter(pred, rest(lst)))
    else:
        return filter(pred, rest(lst))