Herring Cove
Midterm 2

These problems are designed to be around exam difficulty. For more basic problems, see the topic-based guides and practice problems!

Nonlocal and Higher Order Functions

Draw the environment diagram for the following code:

def what(a, b):
    x = a
    def ha(ha):
        nonlocal x
        x = ha * 2
        return x
    return b(ha(x), x)

what(4, lambda x, y : x)

TOGGLE SOLUTION

What makes what a higher order function?

  • a. it returns a function (what function?)
  • b. it takes in a function as an argument
  • c. both a and b
b, what takes in a function as its second argument. It is not actually returning a function, but rather a function call to b, so a is not correct.

TOGGLE SOLUTION

Write the simplest function possible (1-2 lines) that does the exact same thing as what for any input a, b.

def foo(a, b):
    a *= 2
    return b(a, a)

TOGGLE SOLUTION

List Mutability

Draw the environment diagram for the following code.

wow = [0, 'c', 's']

def f(x):
    omg = []
    y = lambda : x - 5
    def g():
        nonlocal x
        while x > len(omg):
            x = y()
            omg.append(x)
        return omg[0:2]
    return g()

lol = f(11)
wow.extend(lol)
lol = wow + ['a']
wow = lol[1:]

TOGGLE SOLUTION

Mutable Linked Lists

Implement multiply, which takes in a Linked List and mutates it so that each link is duplicated by the amount of its entry. See the doctests for examples.

def multiply(link):
    """ 
    >>> link = Link(2, Link(3))
    >>> multiply(link)
    >>> link
    Link(2, Link(2, Link(3, Link(3, Link(3)))))
    >>> link = Link(4, Link(1, Link(2)))
    >>> multiply(link)
    >>> link
    Link(4, Link(4, Link(4, Link(4, Link(1, Link(2, Link(2)))))))
    """ 
    "*** YOUR CODE HERE ***"

TOGGLE SOLUTION

def multiply(link):
    def helper(link, count):
        if count == 1 and link.rest != Link.empty:
            multiply(link.rest)
        elif count != 1 and link != Link.empty:
            link.rest = Link(link.first, link.rest)
            helper(link.rest, count - 1)
    helper(link, link.first)

Iterables and Iterators

  1. Implement mimic_list so that it behaves like Python’s built-in list constructor.
def mimic_list(iterable):
    """ 
    >>> mimic_list((1, 2, 3, 4))
    [1, 2, 3, 4]
    >>> def perf_squares(n): # generates perfect squares
    ...     i = 1
    ...     while i <= n:
    ...         yield i * i
    ...         i += 1
    >>> mimic_list(perf_squares(10))
    [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
    >>> mimic_list("cs61a")
    ['c', 's', '6', '1', 'a']
    """
    "*** YOUR CODE HERE ***"

TOGGLE SOLUTION

def mimic_list(iterable):  
    i = iter(iterable) # get iterable's iterator object
    lst = []  # create an empty list
    try:
        while True:   # add every elem in sequence to lst
            lst.append(next(i))
    except StopIteration: # return lst when the sequence is done
        return lst

2. Recall that all __iter__ methods must return an iterator type. Well, a generator is an iterator, so you can write __iter__ to be a generator function! Write the __iter__ method for BinaryTree such that it returns a generator. Calling next on this generator will return the elements of the BinaryTree in ascending order. Assume that all instances of BinaryTree fall under the constraints of a binary search tree:

  • the root entry is greater than or equal to all entries in the left side of the BinaryTree
  • the root entry is lses than or equal to all entries in the right side of the BinaryTree
class BinarySearchTree:
    empty = ()

    def __init__(self, entry, left=empty, right=empty):
        self.entry = entry
        if left: assert isinstance(left, BinaryTree) 
        if right: assert isinstance(right, BinaryTree)
        self.left = left
        self.right = right

    def __iter__(self):
        """
        >>> tree = BinaryTree(4, BinaryTree(2), BinaryTree(7, BinaryTree(5)))
        >>> for entry in tree:
        ...     print(entry)
        2
        4
        5
        7
        """
        "*** YOUR CODE HERE ***"

TOGGLE SOLUTION

def __iter__(self):
    for value in self.left:
        yield value

    yield self.entry

    for value in self.right:
        yield value