CS61A Lab 5: Tuples, Recursive Lists, and Strings

Week 6, 2013

You can get the starter file for this lab by typing this command into your terminal:

cp ~cs61a/lib/lab/lab05/lab5.py .

Don't forget the dot at the end!

Warm up: What would Python print?

Predict what Python will display when you type the following into the interpreter. Then try it to check your answers.

>>> x = (1, 2, 3)
>>> x[0]     # Q1
______
>>> x[3]     # Q2
______

>>> x[-1]    # Q3
______
>>> x[-3]    # Q4
______
>>> x[:2]        # Q5
______
>>> x[1:3]       # Q6
______
>>> x[-2:3]      # Q7
______

>>> x[::2]       # Q8
______
>>> x[::-1]      # Q9
______
>>> x[-1:0:-1]   # Q10
______
>>> y = (1,)
>>> len(y)       # Q11
______
>>> 1 in y       # Q12
______

>>> y + (2, 3)   # Q13
______
>>> (0,) + y     # Q14
______
>>> y * 3        # Q15
______

>>> z = ((1, 2), (3, 4, 5))
>>> len(z)       # Q16
______

Tuples

1.) For each of the following, give the correct expression to get 7.

>>> x = (1, 3, 5, 7)
>>> x[-1]    # example
7

>>> x = (1, 3, (5, 7), 9)
>>> # YOUR EXPRESSION INVOLVING x HERE
7

>>> x = ((7,),)
>>> # YOUR EXPRESSION INVOLVING x HERE
7

>>> x = (1, (2, (3, (4, (5, (6, (7,)))))))
>>> # YOUR EXPRESSION INVOLVING x HERE
7

2.) Write a function reverse which takes a tuple and returns the reverse. Write both a iterative and a recursive version. You may use slicing notation, but don't use tup[::-1].

def reverse_iter(tup):
    """Returns the reverse of the given tuple.

    >>> reverse_iter((1, 2, 3, 4))
    (4, 3, 2, 1)
    """
    "*** YOUR CODE HERE ***"

def reverse_recursive(tup):
    """Returns the reverse of the given tuple.

    >>> reverse_revursive((1, 2, 3, 4))
    (4, 3, 2, 1)
    """
    "*** YOUR CODE HERE ***"

3.) Write a function merge which takes 2 sorted tuples tup1 and tup2, and returns a new tuple that contains all the elements in the two tuples in sorted order. Write both a recursive and an iterative version

def merge_iter(tup1, tup2):
    """Merges two sorted tuples.

    >>> merge_iter((1, 3, 5), (2, 4, 6))
    (1, 2, 3, 4, 5, 6)
    >>> merge_iter((), (2, 4, 6))
    (2, 4, 6)
    >>> merge_iter((1, 2, 3), ())
    (1, 2, 3)
    """
    "*** YOUR CODE HERE ***"

def merge_recursive(tup1, tup2):
    """Merges two sorted tuples.

    >>> merge_recursive((1, 3, 5), (2, 4, 6))
    (1, 2, 3, 4, 5, 6)
    >>> merge_recursive((), (2, 4, 6))
    (2, 4, 6)
    >>> merge_recursive((1, 2, 3), ())
    (1, 2, 3)
    """
    "*** YOUR CODE HERE ***"

4.) A tuple that contains one or more tuples as elements is called a deep tuple. For example, (1, (2, 3), 4) is a deep tuple.

Write a function deep_len that takes a tuple and reports its deep length. See the doctests for the function's behavior. You may write this function iteratively or recursively.

Hint: you can check if something is a tuple by using the built-in type function. For example,

>>> type(3) == tuple:
False
>>> type((1, 2, 3)) == tuple:
True
def deep_len(tup):
    """Returns the deep length of the tuple.

    >>> deep_len((1, 2, 3))      # normal tuple
    3
    >>> x = (1, (2, 3), 4)       # deep tuple
    >>> deep_len(x)
    4
    >>> y = ((1, (1, 1)), 1, (1, 1))  # deep tuple
    >>> deep_len(y)
    6
    """
    "*** YOUR CODE HERE ***"

One last thing about tuples: they're immutable data structures. This means that once they are created, they can't be changed. For example, try this:

>>> x = (1, 2, 3)
>>> x[0] = 4

This will cause TypeError complaining that tuples don't "support item assignment." In other words, you can't change the elements in a tuple because tuples are immutable. Later in the course, we'll see the opposite -- mutable data structures.

Recursive Lists

Recall that the constructor and selectors for rlists are as follows:

empty_rlist = None

def rlist(first, rest=empty_rlist):
    return (first, rest)

def first(rlist):
    return rlist[0]

def rest(rlist):
    return rlist[1]

As you do the questions below, keep in mind that an rlist is an abstract data type! In other words, your code should not assume that rlists are implemented as tuples.

5.) It would be convenient if we had a way to convert from tuples to rlists. Write a function tup_to_rlist that does exactly that.

Hint: if you are writing the function iteratively, it might be helpful to reverse the tuple first.

def tup_to_rlist(tup):
    """Converts a tuple to an rlist.

    >>> tup = (1, 2, 3, 4)
    >>> r = tup_to_rlist(tup)
    >>> first(r)
    1
    >>> first(rest(rest(r)))
    3
    >>> r = tup_to_rlist(())
    >>> r is empty_rlist
    True
    """
    "***YOUR CODE HERE ***"

6.) Recall the sequence abstraction: a sequence has a finite length and supports element selection. Implement the len_rlist(lst) function, which calculates the length of an rlist, and the getitem_rlist(i, lst) function, which gets the ith item in the rlist.

def len_rlist(lst):
    """Returns the length of the rlist.

    >>> lst = tup_to_rlist((1, 2, 3, 4))
    >>> len_rlist(lst)
    4
    >>> lst = tup_to_rlist(())
    >>> len_rlist(lst)
    0
    """
    "*** YOUR CODE HERE ***"

def getitem_rlist(i, lst):
    """Returns the ith item in the rlist. If the index exceeds the
    length of the rlist, return 'Error'.

    >>> lst = tup_to_rlist((1, 2, 3, 4))
    >>> getitem_rlist(0, lst)
    1
    >>> getitem_rlist(3, lst)
    4
    >>> getitem_rlist(4, lst)
    'Error'
    """
    "*** YOUR CODE HERE ***"

7.) At this point, we want to test your code for any data abstraction violations. Change the constructors and selectors for rlists to the following:

empty_rlist = lambda x: x

def rlist(first, rest=empty_rlist):
    return lambda x: first if x == 'hi' else rest

def first(lst):
    return lst('hi')

def rest(lst):
    return lst('lol')

After the changes, try running the doctests again. Do your solutions for Q5 and Q6 still work? If so, you have preserved abstraction!

Strings

8.) What would Python print?

>>> s = 'hello world!'
>>> s[0]     # Q1
______
>>> s[-1]    # Q2
______
>>> s[100]   # Q3
______

>>> s[1:-1]  # Q4
______
>>> s[::-1]  # Q5
______
>>> 'hello ' + 'world!'  # Q6
______
>>> 'hello ' * 3         # Q7
______

>>> 'ello' in s    # Q8
______
>>> len(s)         # Q9
______
>>> tuple(s)       # Q10
______
>>> s.upper()      # Q11
______
>>> s.split()      # Q12
______

9.) Write expressions so that the following results occur:

>>> s = 'hello world!'
>>> s[:5]    # example
'hello'
>>> EXPRESSION INVOLVING s HERE
'world'
>>> EXPRESSION INVOLVING s HERE
'olleh'
>>> EXPRESSION INVOLVING s HERE
'hlowrd'
>>> EXPRESSION INVOLVING s HERE
'world hello!'

A couple of cool things about strings:

  1. You can iterate over the characters of strings with for loops. This does not iterate over the words!
  2. You can cast things into strings by using the str constructor, like so: str(123) returns '123'.
  3. Strings have lots of handy methods (methods are sort of like functions -- we'll talk more about them later). You can find out what methods strings have by typing dir(str). You can then use the methods using dot notation. For example, 'Hi There'.swapcase() calls the swapcase method.

Sequences

Python has some functions that are useful for working with sequences like tuples and strings:

map and filter don't actually return tuples -- instead, map returns a map object, and filter returns a filter object, neither of which you can index. You can however convert each one into a tuple by using the tuple constructor, as demonstrated below.

Try these out!

>>> map(lambda x: x**2, (1, 2, 3, 4))
______
>>> tuple(map(lambda x: x**2, (1, 2, 3, 4)))
______

>>> filter(lambda x: x % 2 == 0, (1, 2, 3, 4))
______
>>> tuple(filter(lambda x: x % 2 == 0, (1, 2, 3, 4)))
______

>>> from functools import reduce
>>> reduce(lambda a, b: a + b, (1, 2, 3, 4, 5))
______
>>> reduce(lambda a, b: b + a, 'hello world!')
______