*Due by 11:59 PM on (that is, the end of) Friday, 7/6*

**This homework must be submitted online.** We do not
require a paper copy. If you would like a reader to give you written feedback
on your homework, submit a paper copy to the homework box.

**To turn in the electronic copy**, submit all of your
answers in a file named `hw5.py`. Follow the instructions here to submit the electronic copy.

**Readings.** All problems in this homework can be solved
with the subset of Python 3 introduced in sections 1-2.4 of the
lecture notes.

If you would like, you can use the template file `hw5.py`

.
To copy this file to your lab account you can run the command:

cp ~cs61a/lib/hw/hw05/hw5.py .

to copy it into your current directory.

In this homework we will be using the irlist and idict abstract data
types. The files `irlist.py`

and `idict.py`

define these
ADTs along with some useful utility functions for manipulating them. On the
lab computers, you should be able to import from these modules without any
additional setup.

**IRLists vs. Tuples.** Python programmers generally use
indexable tuples or lists instead of the irlists 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 irlists.
This means that there is always a temptation to *violate the abstraction
barrier* between them, and start treating irlists as tuples (bypassing `irlist_first,` `irlist_rest,` and `make_irlist`).
We'll eventually see ways in which this confusion can be avoided, but for now,
we'll just have to be careful. The irlist-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 irlist according
to the problem, assume that *all* tuples in it are also irlists.

The `could_be_irlist` function in
`irlist.py`

might be useful for converting irlists to tuples.
Similarly, the following function might be useful when converting from tuples to
irlists:

def is_tuple(x): return type(x) is tuple

**Q1.** Write a function `to_irlist` that converts a tuple of values into a corresponding
irlist. **Unlike irlist_populate** in

`irlist.py`

, any tuples
among the items given should also become irlists. def to_irlist(items): """The sequence of values in 'items', converted into a corresponding irlist. >>> irlist_str(to_irlist((1, (0, 2), (), 3))) '<1, <0, 2>, <>, 3>' """

**Q2.** Now write the inverse of `to_irlist`, a function that takes an irlist as input and returns the
corresponding tuple:

def to_tuple(L): """Assuming L is an irlist, returns a tuple containing the same sequence of values. >>> x = to_irlist((1, (0, 2), (), 3)) >>> to_tuple(x) (1, (0, 2), (), 3) """

**Q3.** Implement the function `count_words` which takes a tuple of words and produces an idict
mapping each different word to the number of times that it appeared in the
tuple.

def count_words(words): """Returns an idict mapping each unique word to the number of times it occurred in the tuple of words. >>> counts = count_words(('the', 'best', 'the', 'best', 'the', 'worst')) >>> idict_select(counts, 'the') 3 >>> idict_select(counts, 'worst') 1 >>> idict_select(counts, 'best') 2 """

Code for the idict abstract data type can be found in
`idict.py`

.

**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 irlist and produces an irlist of irlists containing all
subsequences of the input irlist. As a first step, write a function `inserted_into_all` that takes an item and an irlist
of irlists and creates the irlist resulting from prepending the item into each of
the lists:

def inserted_into_all(item, list_list): """Assuming that 'list_list' is an irlist of irlists, return the irlist consisting of the irlists in 'list_list', but with 'item' prepended as the first item in each. >>> L0 = to_irlist(((), (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 irlist, return an irlist of all subsequences of S (an irlist of irlists). The order in which the subsequences appear is unspecified. >>> seqs = subseqs(to_irlist((1, 2, 3))) >>> tuple(sorted(to_tuple(seqs))) ((), (1,), (1, 2), (1, 2, 3), (1, 3), (2,), (2, 3), (3,)) """

**Q5.** Repeat Q4, but this time operate on tuples.
Do **not** implement this by converting tuples to irlists, 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)) >>> tuple(sorted(seqs)) ((), (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 `irlist_filter`, etc., from lecture.
Devise a function that counts the number of palindromic words (those that read
the same backwards as forwards) in a tuple of words using only
`lambda`, basic operations on strings, the tuple
constructor, conditional expressions, and the functions
`filter`, `map`,
and `reduce`. 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 ____________________________________________

*Hint*: The easiest way to get the reversed version of a string
`s` is to use the Python slicing notation trick
`s[::-1]`. Also, the function
`lower`, when called on strings, converts all of
the characters in the string to lowercase. For instance, if the variable
`s` contains the string
"`PyThoN`", the expression
`s.lower()` evaluates to
"`python`".

**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.') """

Do **not** use any loops or recursion.

*Hint*: Our solution maps over two (slightly different) copies
of the input sequence `S`. Also, the function
`capitalize`, when called on strings, converts
the first character to uppercase. For instance, if the variable
`s` contains the string
"`python`", the expression
`s.capitalize()` evaluates to
"`Python`". Finally, remember that,
just as with tuples, we can use the expression
`s[-1]` to get the last character of a string
`s`.

**Q9.** Implement the following function 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 _________________________________________________

**Extra for Experts**

*Note*: "Extra for Experts" problems are completely
optional. You are encouraged to try these questions. However, these are
questions which either we consider more difficult than what we would consider asking
you on an exam or focus on ideas we are not concerned with in this course, so
please don't be discouraged if you don't solve them.

**Q10.** 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 `def`s to break up the definition into manageable pieces, if
desired:

def sortit(S): """The sequence of strings S sorted into lexicographic order (the < operator). >>> sortit((4, 2, 3, 5, 1)) (1, 2, 3, 4, 5) """