**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 ______________________________________________________