Due by 4pm on Monday, 2/13
You can grab a template for this homework either by downloading the file from the calendar or by running the following command in terminal on one of the school computers (the dot is significant: it denotes the current directory)
cp ~cs61a/lib/hw/hw4.py .
Readings. Chapter 2.3
Q1. [Held over from last week] Write three similar functions, each of which takes as an argument a sequence of intervals and returns the sum of the square of each interval that does not contain 0.
- sum_nonzero_with_for(seq) uses a for statement containing an if statement.
- sum_nonzero_with_map_filter_reduce(seq) uses map and filter and reduce.
- sum_nonzero_with_generator_reduce(seq) uses generator expression and reduce.
Rlists vs. Tuples. Python programmers generally use indexable tuples or lists instead of the rlists we've been studying recently. All of them represent sequences, however, and so there are natural correspondences between them. The next two questions concern these relationships.
Somewhat confusingly, we've been using tuples to represent rlists. This means that there is always a temptation to violate the abstraction barrier between them, and start treating rlists as tuples (bypassing first, rest,` and make_rlist). We'll eventually see ways in which this confusion can be avoided, but for now, we'll just have to be careful. The rlist-related exercises that follow will manipulate only integers, strings, the value None, and tuples containing these things. If a value (parameter or result) is supposed to be an rlist according to the problem, assume that all tuples and null values (None) in it are rlists. If a value is not supposed to contain rlists, then assume that the null value does not appear within it.
The following function might be useful when converting from rlists to tuples:
def could_be_rlist(x):
"""Return true iff x might represent an rlist."""
return x is None or type(x) is tuple
and when going in the opposite direction:
def is_tuple(x):
return type(x) is tuple
Q2. Write a function, to_rlist, that converts a tuple of values or the value None into a corresponding rlist. Any tuples among those values should also become rlists. This is an extension of one of the lab exercises:
def to_rlist(items):
"""The sequence of values in 'items', converted into a corresponding
rlist.
>>> to_rlist((1, (0, 2), (), 3))
(1, ((0, (2, None)), (None, (3, None))))
"""
Hint: Nobody says you have to construct your rlist from the front.
Q3. Now write the inverse of to_rlist, a function that takes an rlist as input and returns the corresponding tuple:
def to_tuple(L):
"""Assuming L is an rlist, returns a tuple containing the same
sequence of values.
>>> x = to_rlist((1, (0, 2), (), 3))
>>> to_tuple(x)
(1, (0, 2), (), 3)
"""
Q4. A subsequence of a sequence S is a sequence of elements from S, in the same order they appear in S, but possibly with elements missing. Thus, the tuple sequences (), (1, 3), (2,), and (1, 2, 3) are subsequences of (1, 2, 3). Write a function that takes an rlist and produces an rlist of rlists containing all subsequences of the input rlist. As a first step, write a function inserted_into_all that takes an item and an rlist of rlists and creates the rlist resulting from prepending the item into each of the lists:
def inserted_into_all(item, list_list):
"""Assuming that 'list_list' is an rlist of rlists, return the
rlist consisting of the rlists in 'list_list', but with
'item' prepended as the first item in each.
>>> L0 = to_rlist(((), (1, 2), (3,)))
>>> L1 = inserted_into_all(0, L0)
>>> to_tuple(L1)
((0,), (0, 1, 2), (0, 3))
"""
def subseqs(S):
"""Assuming that S is an rlist, return an rlist of all subsequences
of S (an rlist of rlists). The order in which the subsequences
appear is unspecified.
>>> seqs = subseqs(to_rlist((1, 2, 3)))
>>> show = list(to_tuple(seqs)) # Can only sort lists, not tuples
>>> show.sort()
>>> show
[(), (1,), (1, 2), (1, 2, 3), (1, 3), (2,), (2, 3), (3,)]
"""
Q5. Repeat Q4, but this time operate on tuples. Don't implement this by converting tuples to rlists, calling subseqs, and then converting back!:
def inserted_into_all_tuples(item, tuple_tuple): """Assuming that 'tuple_tuple' is a tuple of tuples, return the tuple consisting of the tuples in 'tuple_tuple', but with 'item' prepended as the first item in each. >>> inserted_into_all_tuples(0, ((), (1, 2), (3, ))) ((0,), (0, 1, 2), (0, 3)) """ def subseqs_tuples(S): """Assuming that S is a tuple, return tuple of all subsequences of S (a tuple of tuples). The order in which the subsequences appear is unspecified. >>> seqs = subseqs_tuples((1, 2, 3)) >>> show = list(seqs) >>> show.sort() >>> show [(), (1,), (1, 2), (1, 2, 3), (1, 3), (2,), (2, 3), (3,)] """
Q6. The Python library defines filter, map, and reduce, which operate on Python sequences just like filter_rlist, etc., from lecture. Devise a function that counts the number of palindromic words (those that read the same backwards as forwards) in a list of words using only these functions, lambda, basic operations on strings, and conditional expressions. Specifically, do not use recursion or any kind of loop:
def count_palindromes(L):
"""The number of palindromic words in the sequence of strings
L (ignoring case).
>>> count_palindromes(("acme", "madam", "pivot", "pip"))
2
"""
return ____________________________________________
Q7. Show how to implement filter using map, reduce, basic operations on tuples, and (possibly) lambda. Do not use filter, any kind of loop, recursion, def, or the special operations for generating sequences, such as (x*2 for x in ...):
def alt_filter(pred, L):
"""The tuple containing all elements, x, of L such that pred(x).
>>> alt_filter(lambda x: x%2 == 0, (0, 1, 3, 8, 4, 12, 13))
(0, 8, 4, 12)
"""
return ________________________________________________________
Hint: reduce is allowed to produce any kind of value, not just integers.
Q8. The map function in the Python library actually allows you to write things like this:
>>> from operator import add >>> tuple(map(add, (1, 7, 8), (3, 5, 2))) (4, 12, 10) >>> tuple(map(add, (1, 7, 8, 9), (3, 5, 2))) # Extra items ignored (4, 12, 10)
That is, it applies the function add (you could also have written lambda x,y: x+y) to pairs of arguments, one from the first list, and one from the second. Indeed, any number of sequences may be combined in this fashion. Show how to use this to take a text consisting of a sequence of words and to return the same words, but with the beginnings of sentences capitalized:
def capitalize_sentences(S):
"""The sequence of words (strings) S, with all initial words in
sentences capitalized, and all others unchanged. A word begins a
sentence if it is either the first word in S, or the preceding word
in S ends in a period.
>>> capitalize_sentences(("see", "spot", "run.", "run", "spot", "run."))
('See', 'spot', 'run.', 'Run', 'spot', 'run.')
"""
return ________________________________________________
Do not use any loops or recursion.
Q9. Implement the following function, just using reduce, map, filter, range, and lambda:
def repeat(f, x, n):
"""Apply f to x n times. When n is 0, the result is x; when n is
1, the result is f(x); when n is 2, f(f(x)), etc.
>>> repeat(lambda x: x+1, 1, 5)
6
"""
return _________________________________________________
Q10. Extra for experts: Implement a sorting function on tuples of strings, just using reduce, map, len, filter, lambda, and the repeat function. As in previous problems, no loops or recursion. You may use defs to break up the definition into manageable pieces, if desired:
def sortit(S):
"""The sequence of strings S sorted into lexicographic order
(the < operator)."""
return ______________________________________________________