CS61A Lab 4b: Mutable Recursive Lists and Type Dispatching

You can get starter code for this lab by typing this into your terminal:

cp ~cs61a/lib/lab/lab04b/lab4b.py .

Don't forget the dot at the end!

Recursive Lists

In lecture, we introduced the OOP version of an Rlist:

class Rlist(object):
    class EmptyList(object):
        def __len__(self):
            return 0

    empty = EmptyList()

    def __init__(self, first, rest=empty):
        self.first = first
        self.rest = rest

Just like before, these Rlists have a first and a rest. The difference is that, now, the Rlists are mutable.

A couple of things to notice:

  1. Empty Rlists: to check if an Rlist is empty, compare it against the class variable Rlist.empty:
    if rlist is Rlist.empty:
        return 'This rlist is empty!'
    Don't construct another EmptyList!
  2. By definition, Rlist.empty has a length of 0:
    >>> len(Rlist.empty)
    0

0) What would Python print?

>>> Rlist(1, Rlist.empty)
______
>>> Rlist(1)
______
>>> Rlist()
______

>>> rlist = Rlist(1, Rlist(2, Rlist(3)))
>>> rlist.first
______
>>> type(rlist.rest)
______
>>> rlist.rest.first
______
>>> rlist.first.rest
______
>>> rlist.rest.rest.rest is Rlist.empty
______

>>> rlist.first = 9001
>>> rlist.first
______
>>> rlist.rest = rlist.rest.rest
>>> rlist.rest.first
______
>>> rlist = Rlist(1)
>>> rlist.rest = rlist
>>> rlist.rest.rest.rest.rest.first
______

1) Write a function rlist_to_list that converts a given Rlist to a Python list.

def rlist_to_list(rlist):
    """Takes an RLIST and returns a Python list with the same
    elements.

    >>> rlist = Rlist(1, Rlist(2, Rlist(3, Rlist(4))))
    >>> rlist_to_list(rlist)
    [1, 2, 3, 4]
    >>> rlist_to_list(Rlist.empty)
    []
    """
    "*** YOUR CODE HERE ***"

2) In lecture, we learned about the special "underscore" methods for classes, two of which were __len__, which allows you to call the builtin function len on the object, and __getitem__, which allows you to use index notation on the object. Implement both of them for the Rlist class. Afterwards, the doctests for the Rlist class should pass.

class Rlist(object):
    """A mutable rlist class.

    >>> r = Rlist(3, Rlist(2, Rlist(1)))
    >>> len(r)
    3
    >>> len(r.rest)
    2
    >>> r[0]
    3
    >>> r[1]
    2
    """
    # previous stuff here

    def __len__(self):
        "*** YOUR CODE HERE ***"

    def __getitem__(self, index):
        "*** YOUR CODE HERE ***"

3) In addition, it would be nice if we could have a human-readable string representation of an Rlist, so that we don't have to stare at this all the time:

>>> Rlist(1, Rlist(2, Rlist(3)))
<Rlist object at ...>

Implement a __repr__ method to fix this. Write the __repr__ to match the following representations:

>>> Rlist(1, Rlist(2, Rlist(3)))
Rlist(1, Rlist(2, Rlist(3)))
>>> Rlist(1)
Rlist(1)
>>> repr(Rlist(1))
'Rlist(1)'

Remember, __repr__ should return a string!

class Rlist(object):

    # previous stuff here

    def __repr__(self):
        "*** YOUR CODE HERE ***"

4) Implement a function insert that takes an Rlist, a value, and an index, and inserts the value into the Rlist at the given index. You can assume the rlist already has at least one element. Do NOT return anything -- insert should mutate the rlist.

def insert(rlist, value, index):
    """Insert VALUE into the the RLIST at the given INDEX.

    >>> rlist = Rlist(1, Rlist(2, Rlist(3)))
    >>> insert(rlist, 9001, 0)
    >>> rlist
    Rlist(9001, Rlist(1, Rlist(2, Rlist(3))))
    >>> insert(rlist, 100, 2)
    >>> rlist
    Rlist(9001, Rlist(1, Rlist(100, Rlist(2, Rlist(3)))))
    """
    "*** YOUR CODE HERE ***"

5) Implement a function reverse that reverses a given Rlist. reverse should return the reversed Rlist (it doesn't matter if you created a new Rlist or mutated the original).

Extra for experts: Implement reverse without calling the Rlist constructor.

def reverse(rlist):
    """Returns an Rlist that is the reverse of the original.

    >>> Rlist(1).rest is Rlist.empty
    True
    >>> rlist = Rlist(1, Rlist(2, Rlist(3)))
    >>> reverse(rlist)
    Rlist(3, Rlist(2, Rlist(1)))
    >>> reverse(Rlist(1))
    Rlist(1)
    """
    "*** YOUR CODE HERE ***"

Type Dispatching

Recall the tag-based type-dispatching introduced in lecture:

def type_tag(x):
    return type_tag.tags[type(x)]

type_tag.tags = {
    <type1> : <tag1>
    <type2> : <tag2>
    ...
}

To create a function that would add different types together, we followed this pattern:

type_tag.tags = {
    ComplexRI : 'com',
    ComplexRA : 'com',
    Rational  : 'rat',
}

def add(z1, z2):
    types = (type_tag(z1), type_tag(z2))
    return add.impl[types](z1, z2)

add.impl = {}
add.impl[('com', 'com')] = lambda z1, z2: ...
add.impl[('rat', 'com')] = lambda z1, z2: ...
...

6) Using this pattern of type dispatching, write a function extend that takes two sequences, either Python lists or Rlists, and adds the elements of the second sequence to the first (this works like list.extend). In the extend.impl dictionary, you may use lambdas or actual functions (that you define yourself) as the values.

def type_tag(x):
    return type_tag.tags[type(x)]

# notice that type_tag is kind of unnecessary here
type_tag.tags = {
    list  : 'list',
    Rlist : 'Rlist',
}

def extend(seq1, seq2):
    """Takes the elements of seq2 and adds them to the end of seq1.

    >>> rlist = Rlist(4, Rlist(5, Rlist(6)))
    >>> lst = [1, 2, 3]
    >>> extend(lst, rlist)
    >>> lst
    [1, 2, 3, 4, 5, 6]
    >>> rlist
    Rlist(4, Rlist(5, Rlist(6)))
    >>> extend(rlist, [7, 8])
    >>> rlist
    Rlist(4, Rlist(5, Rlist(6, Rlist(7, Rlist(8)))))
    >>> extend(lst, [7, 8, 9])
    >>> lst
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    """
    "*** YOUR CODE HERE ***"

extend.impl = {
  ('list', 'list')   : "*** YOUR CODE HERE ***" ,
  ('list', 'Rlist')  : "*** YOUR CODE HERE ***" ,
  ('Rlist', 'list')  : "*** YOUR CODE HERE ***" ,
  ('Rlist', 'Rlist') : "*** YOUR CODE HERE ***" ,
}