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