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

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

>>> first(r)
______
>>> first(rest(rest(r)))
______
>>> first(first(rest(r)))
______

Question 2

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

[1, 3]
[1, 3]
"""
def alternate(r):
if r == empty:
return empty
elif rest(r) == empty:
return r
else:

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.