CS61A Lab 10: RLists and Nonlocal

Week 5, 2012

RLists implemented with Python’s Object notation

Here is the RList class. This file, in full, and with docstrings, is in the the ~cs61a/lib directory. You can copy it to your local directory by running
cp ~cs61a/lib/rlist.py .
class RList: 
    class EmptyRList: 
        """A special class for defining the "base case" of the data structure. 
        This should NEVER be instantiated outside the class, instead use the 
        RList empty method. 
        """ 
        # BODY OMITTED
    the_empty_rlist = EmptyRList() 
    
    @staticmethod 
    def empty(): 
        return RList.the_empty_rlist 
    
    def __init__(self, first, rest=the_empty_rlist): 
        self.first = first 
        self.rest = rest 
    
    def __len__(self): 
        return 1 + len(self.rest) 
    
    def __getitem__(self, i): 
        if i == 0: 
            return self.first 
        return self.rest[i - 1] 
        
    def __setitem__(self, i, new_val): 
        if i == 0: 
            self.first = new_val 
        else: 
            self.rest[i - 1] = new_val  
 
    def __repr__(self): 
        f = repr(self.first) 
        if self.rest is RList.empty(): 
            return 'RList({0})'.format(f) 
        else: 
            return 'RList({0}, {1})'.format(f, repr(self.rest)) 
    
    def __str__(self): 
        cur = self 
        result = "<" 
        while cur is not RList.empty(): 
            if type(cur.first) is RList or cur.first is RList.empty(): 
                result += str(cur.first) 
            else: 
                result += repr(cur.first) 
            # Move forward and add comma if necessary 
            cur = cur.rest 
            if cur is not RList.empty(): 
                result += ", " 
        return result + ">" 

Question 1. It would be convenient to have a procedure tuple_to_rlist, which takes a tuple and converts it to the equivalent RList. Finish the implementation below.

def tuple_to_rlist(tup):
    """Takes an input tuple, tup, and returns the equivalent representation of the sequence using an rlist.
    Arguments:
    tup -- A sequence represented as a tuple.
    >>> str(tuple_to_rlist((1, 2, 3, 4, 5, 6)))
    '<1, 2, 3, 4, 5, 6>'
    """
    "*** Your code here. ***"
    

Nonlocal

Question 2. Predict the result of evaluating the following calls in the interpreter. Then try them out yourself!
>>> def make_funny_adder(n):
        def adder(x):
            if x == 'new':
                nonlocal n
                n = n + 1
            else:
                return x + n
        return adder

>>> h = make_funny_adder(3)

>>> h(5)
...

>>> j = make_funny_adder(7)

>>> j(5)
...


>>> h('new')

>>> h(5)
...

>>> j(5)  
Question 3. Write a function make_fib that returns a function that itself returns the next Fibonacci number each time it is called. See the following examples:
 
>>> fib = make_fib()

>>> fib()
1

>>> fib()
1

>>> fib()
2

>>> fib()
3

>>> fib()
5
def make_fib():
    ***YOUR CODE HERE***

As an exercise, draw the environment diagram (on a piece of paper) that results from executing the following statements:

>>> fib = make_fib()
>>> fib()
>>> fib()
>>> fib()

Compare with a neighbor (or show your TA) to verify you have done it correctly.

We have now covered all the material you need to complete project 3. Survey results indicate that labs are a bit too long, so we will cut this one a little bit short. Feel free to use the rest of this lab to work on the project or practice with more environment diagrams! Ask your TA if you need help.