CS61A Homework 9

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

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 hw9.py. Follow the instructions here to submit the electronic copy.

If you would like, you can use the template file hw9.py. To copy this file to your lab account you can run the command:

      cp ~cs61a/lib/hw/hw09/hw9.py .
      

to copy it into your current directory.

This homework also makes use of the rlist.py library for implementing mutable recursive lists as a Python class.

In homeworks, we have three different categories of questions:

• Core Questions — Questions that we believe test a core concept of the course and should be your highest priority when attempting the homework.
• Reinforcement Questions — Questions that we believe have material that is either covered by other questions in this homework or in past homeworks, and can therefore be considered second priority after the core questions have been completed.
• Extra for Experts — As in earlier homeworks, these problems are completely optional. You are encouraged to try these questions once you have completed questions from the other two categories. However, these are questions that we consider either more difficult than what we would ask you on an exam or that focus on ideas we are not concerned with in this course, so please do not be discouraged if you do not solve them.

It is our hope that these categories will help guide you in deciding how to divide your time when working on the homeworks.

Core Questions

Q1. Write the function deep_map_mut that takes a Python list and mutates all of the elements (including elements of sublists) to be the result of calling the function given, fn, on each element. Note that the function does not return the mutated list!

Q2. Memoization is a relatively common trick in computer science to help avoid repeating operations that take a long time to compute. The idea behind memoization is relatively simple: remember the value of a call and reuse it after you compute it once. We can do this by keeping a dictionary that maps every input that has ever been handed to the function to the result that was computed. We can then use this dictionary to return pre-computed values if we are handed arguments we have already handled for a previous call. We can call the dictionary of previous computations a "memo" for the function.

Using this idea, write memoized_fib, which uses a globally defined memo, FIB_MEMO, to remember previously computed fibonacci numbers.

You might notice that our tests use a decorator function, which is a higher order function that takes a function as an argument and returns a modified version of that function. We can use the same "@" notation as we saw for staticmethod in lecture for any decorator function. In this case, the prints_calls decorator transforms a function to print every call to the function it decorates. We will write our own decorator in question 5.

Q3. In rlist.py, we have provided a class which implements a mutable recursive list data type (similar to IRLists, but you can modify the first and rest of the list). Write the function rlist_deep_map_mut, which takes a RList instance and mutates all the items (even in nested RLists) to be the result of calling the function fn on each item.

Do this without creating any new RLists. This means you can not use the RList constructor, the plus operator (+), or RList.populate.

Hint: To check the type of a variable, you can do something similar to what is_tuple did in homework 5.

Reinforcement Questions

Q4. Write the function deep_filter_mut, which takes a predicate function, pred, and a (possibly deeply nested) Python list and mutates the list to remove all items (including those in nested Python lists) for which pred returns False.

As with question 1, do not create any new lists in your solution.

Hint: You might want to use the del operator that was briefly mentioned in lecture. You can delete an item of a Python list by using the following notation:

      >>> L = [1, 2, 3, 4, 5] # Example list
      >>> del L[1] # Deletes the 2nd element of Python list L
      >>> L
      [1, 3, 4, 5]
      

Q5. Write the decorator memoized, which takes a function and returns a memoized version of the function given, fn. We will acheive this by defining a dictionary fn_memo outside the new function we create, which maps arguments to previously computed results for the function fn, instead of writing a new global dictionary for every single function we would like to memoize.

Q6. When dealing with a textual interface, it is often convenient to be able to abbreviate command names -- using "con" instead of "continue", for example. We would like a class that provides this feature. The class is instantiated with a list of command names. It has a method complete that takes an input cmnd and, if possible, returns the full command name of which cmnd is an abbreviation. It succeeds if either cmnd is already the full name of a command in the original list, or cmnd is a prefix of exactly one command in the list. Another method, minimal_abbreviation, takes as input the full name of a command from the original list and returns the shortest string that uniquely abbreviates the command:

      class Abbrev:
          """An abbreviation map."""

          def __init__(self, full_names):
              """Initialize self to handle abbreviations for the words
              in the sequence of strings full_names.  It is an error if
              a name appears twice in full_names."""
              # YOUR CODE HERE

          def complete(self, cmnd):
              """The member of my word list that the string cmnd
              abbreviates, if it exists and is unique.  cmnd abbreviates
              a string S in my word list if cmnd == S, or cmnd is a
              prefix of S and of no other command in my word list.
              Raises ValueError if there is no such S.
              >>> a = Abbrev(['continue', 'catch', 'next',
              ...             'st', 'step', 'command'])
              >>> a.complete('ne')
              'next'
              >>> a.complete('co')
              Traceback (most recent call last):
                 ...
              ValueError: not unique: 'co'
              >>> a.complete('st')
              'st'
              >>> a.complete('foo')
              Traceback (most recent call last):
                 ...
              ValueError: unknown command: 'foo'
              """
              # YOUR CODE HERE

          def minimal_abbreviation(self, cmnd):
              """The string, S, of shortest length such that
              self.complete(S) == cmnd.
              >>> a = Abbrev(['continue', 'catch', 'next',
              ...             'st', 'step', 'command'])
              >>> a.minimal_abbreviation('continue')
              'con'
              >>> a.minimal_abbreviation('next')
              'n'
              >>> a.minimal_abbreviation('step')
              'ste'
              >>> a.minimal_abbreviation('ste')
              Traceback (most recent call last):
                 ...
              ValueError: unknown command: 'ste'
              """
              # YOUR CODE HERE
      

As in the last homework, you will need to raise an error in some cases. ValueError objects are instantiated the same exact way as a BaseException, where you provide the error message as the argument to the constructor.

For this question, you might want to use the try ... except ... syntax that Python provides for handling errors, although it is completely possible to solve this question without it. Here's an example of the syntax:

      try:
          # Possibly buggy code here
      except ValueError:
          # Code for handling the case where the buggy code resulted in a
          # ValueError.
      

The way it works is that you can wrap a piece of code that might error in a try clause and can provide code in the except block to execute if a given type of error does occur. One thing to note is that if an error does occur, all code after that point in the try clause is not executed and you immediately jump down to the appropriate except clause. Here is an example:

      >>> try:
      ...     print("Prints")
      ...     1 / 0
      ...     print("Doesn't Print")
      ... except ZeroDivisionError:
      ...     print("Prints because we divided by 0 in the try")
      ...
      Prints
      Prints becausse we divided by 0 in the try
      >>>
      

Hint: Python strings have a method called startswith which takes another string and returns True if that string matches the beginning of the string before the dot. Here's an example:

      >>> x = "foo"
      >>> x.startswith("fo")
      True
      >>> x.startswith("fa")
      False
      >>> x.startswith("fo")
      True
      >>> "foobar".startswith(x)
      True
      

Extra for Experts

Q7. Consider the RList C in the following example, using a mutable RList type as defined in rlist.py:

      >>> C = RList(1, RList(2, RList(3)))
      >>> C.rest.rest.rest = C
      >>> C.rest.rest.rest.first
      1
      >>> C.rest.rest.rest.rest.first
      2
      

We say this list is circular. Circular lists can be useful, but they require tweaks to the usual implementations of some routines. For example, the to_tuple function from HW5 would go into an infinite loop on C if we weren't careful while rewriting it to handle our RList type.

Write a function that determines whether an RList is circular without using more than constant space, meaning that you can not use data structures like lists or dictionaries to remember every item you have seen so far:

      >>> C = RList(1, RList(2, RList(3)))
      >>> detect_cycle(C)
      False
      >>> C.rest.rest.rest = C
      >>> detect_cycle(C)
      True
      >>> C = RList(0, C)
      >>> detect_cycle(C)
      True