CS61A Homework 5

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 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).
          >>> sortit((4, 2, 3, 5, 1))
          (1, 2, 3, 4, 5) 
          """