We've provided you with a starter file that contains the code you will be using throughout this lab. You can get it by logging onto your class account and running the command:
cp ~cs61a/lib/lab/lab03a/lab3a.py .
Don't forget the dot at the end!
Once you copy the file to your own account, you can open it up in your favorite text editor or Emacs, instead of typing all your code directly into the Python interpreter. This way, you can save your progress and quickly revise code.
Try to figure out what Python will display after the following lines are entered. Then type them into the interpreter 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 ______
>>> a = (2, 3, 4)
>>> for elem in a: # Q17
... print(elem)
______
>>> for item in a: # Q18
... print('hi')
______
>>> for elem in range(3) # Q19
... print(elem)
______
Problem 1: For each of the following, give the correct expression involving x to get 7.
>>> x = (1, 3, 5, 7) >>> x[-1] # example 7 >>> x = (1, 3, (5, 7), 9) >>> _______________ 7 >>> x = ((7,),) >>> _______________ 7 >>> x = (1, (2, (3, (4, (5, (6, (7,))))))) >>> _______________ 7
Problem 2: Write a function reverse which takes a tuple and returns the reverse. Write both an iterative and a recursive version. You may also 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_recursive((1, 2, 3, 4))
(4, 3, 2, 1)
"""
"*** YOUR CODE HERE ***"
Problem 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 ***"
Problem 4: A tuple that contains one or more tuples as elements is called a deeptuple. 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 a 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.
Problem 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 ***"
Problem 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 ***"
Problem 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!