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!

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 ______

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.

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 *i*th 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!

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:

- You can iterate over the
*characters*of strings with for loops. This does not iterate over the words! - You can cast things into strings by using the str constructor, like so: str(123) returns '123'.
- 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.

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

**map**: applies a function to each element in a sequence**filter**: keeps elements in a sequence only if they satisfy a given predicate function**reduce**: combines elements in a function using a given combiner

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!') ______