The program `handin21` will only submit files in the
cs21/homework/8 directory.

Your programs are graded on both correctness and style. Please review the comments regarding programming style on the main page

Some of the problems will have optional components that allow you to
further practice your skills in Python. Optional portions will not be
graded, but may be interesting for those wanting some extra challenges.

Recursion on lists

Complete each the following functions using a recursive
solution. (You can find similar examples in the
You should not use any of the methods in the `list`
class (such as `insert`, `append`,
`remove`, etc).

- Complete all the functions from the
`practice.py`program that we began working on in class. Be sure to copy that file to your`cs21/homework/8`directory. - Write a function called
`multiplyList(lst)`that takes a list of numbers (`lst`) and returns the product of all the numbers in the list. Return 1 if the list is empty. Save your implementation of`multiplyList(lst)`and the solution to all the other problems below in one file called`recurse.py`in your`homework/8`directory.Below are some test cases for the

`multiplyList`function you will write. You should add some more test cases. They need not be exhaustive, but they should check more than just a few basic test cases. In subsequent questions, you will write most or all of the test cases yourself. You should put your tests in a separate function called`test()`which is started below. The`assert`statement checks to be sure that the statement is true, and if not, raises an`AssertionError`.def test(): """ Tests the functions in this program. Be sure to verify that the answer your are expecting is the answer you get by using the assert statement. """ #Here are some tests for question 2 to get you started. res = multiplyList([1, 2, -5, 3]) assert res == -30 res = multiplyList([]) assert res == 1 print 'All tests passed'

- OPTIONAL DIFFICULT QUESTION: This problem may be challenging
and is optional. Be sure to complete the required questions
before attempting this one.
Write a new version of

`multiplyList(lst)`called`newMultiplyList(lst)`which defines the product of an empty list to be 0. Be sure to write your own test cases. For example:newMultiplyList([1, 2, -5, 3]) # returns -30 newMultiplyList([]) # returns 0

- Write test cases for the functions you wrote in Question 1 using the style shown in above.
- Write a function called
`addOne(lst)`which returns a list which has each element of`lst`increased by one. For example:addOne([]) # returns [] addOne([1, 2, -5, 3]) # returns [2, 3, -4, 4]

- Write a function called
`insertBeforeFirst(match, insert, lst)`which inserts an item (`insert`) into a list (`lst`) immediately before the first occurrence of a specified item (`match`). This function returns a list without changing the original list. For example:# inserts 'pea' before the first 'pod' in ['a','green','pod'] # should return ['a', 'green', 'pea', 'pod'] insertBeforeFirst('pod', 'pea', ['a','green','pod']) # inserts 'pea' before the first 'pod' in ['pod','pod','pod'] # should return res == ['pea', 'pod', 'pod', 'pod'] insertBeforeFirst('pod', 'pea', ['pod','pod','pod']) # since there is no occurrence of 'pod', we do not insert 'pea' # should return ['a','green','leaf'] insertBeforeFirst('pod', 'pea', ['a','green','leaf'])

- Write a function called
`collapseFirstPair(lst)`which locates the first time that the same symbol appears twice in a row in a list (`lst`) and removes one of them. Return a list with this pair removed, do not change the original list. Be sure to add your own test cases. Here is one to get you started:# should return ['a', 'b', 'c', 'd', 'd'] collapseFirstPair(['a', 'b', 'c', 'c', 'd', 'd'])

- Write a function called
`collapseAllPairs(lst)`which collapses all pairs found in a list. (As above, it returns a list and does not modify`lst`.) For an extra challenge, solve this by using the`collapseFirstPair`function you wrote above.Here is an example:

# should return ['a', 'b', 'c', 'd', 'e', 'f'] collapseAllPairs(['a', 'b', 'b', 'b', 'c', 'c', 'c', 'd', 'd', 'e', 'f', 'f'])

- Write a function called
`swap(x, y, lst)`that takes a symbol`x`, a symbol`y`, and a list (`lst`) and returns a list with all occurrences of`x`replaced by`y`and all occurrences of`y`replaced by`x`. Be sure to write your own test cases. For example:# should return ['blue', 'fish', 'red', 'fish', 'blue'] swap('red', 'blue', ['red', 'fish', 'blue', 'fish', 'red'])

- Write a function called
`listReplace(pairlst, lst)`that takes a list of pairs (`pairlst`) and a list (`lst`) and returns a list with the first element of each pair replaced by the second element of each pair. This problem is more difficult than it may initially seem. Be sure your function can handle both test cases below. (The second test case is the harder one.) Also, be sure to write your own test cases. For example:listReplace([('carrots', 'peas'), ('fork', 'spoon')],\ ['eat', 'your', 'carrots', 'with', 'a', 'fork']) # returns ['eat', 'your', 'peas', 'with', 'a', 'spoon'] listReplace([('carrots', 'peas'), ('peas', 'potatoes')],\ ['eat', 'your', 'carrots', 'and', 'peas']) # returns ['eat', 'your', 'peas', 'and', 'potatoes'] # NOTE: THE ANSWER IS NOT: ['eat', 'your', 'potatoes', 'and', 'potatoes']

- OPTIONAL (CONCEPTUALLY) DIFFICULT QUESTION: This
problem may be challenging and is optional. Be sure to complete
the required questions before attempting this one.
Suppose you wanted to write a function

`addTwo`similar to the function`addOne`you wrote above. There are three ways you could do this:- You could copy your solution to
`addOne`and replace the`1`with a`2`. (This is a bad solution: what if you also wanted`addThree`?) - You could modify
`addOne(lst)`to be`addN(lst, n)`so you'd never need to write`addTwo`or`addThree`. But if you really wanted`addThree`, it would just be this:def addThree(lst): return addN(lst, 3)

This is a much nicer solution, but it only works if you want to add things to the elements of the list. - The most generic solution would allow you to specify what you
wanted to do to each element of the list by passing it the name of a
function you'd like to perform on each element. This is exactly what
you did when you passed a comparator function to
`sort`, e.g.`lst.sort(cmp=comparator)`.

`listmap(fn, lst)`which takes a function (`fn`) and a list (`lst`) as parameters and returns a list where you have performed the`fn`on every element of the list.Here is an example:

def plusOne(x): return x + 1 # should return [1, 2, 3] listmap(plusOne, [0, 1, 2])

(Python has a built-in function called`map`which does exactly this! You can do`help(map)`for more information.) - You could copy your solution to
- OPTIONAL (CONCEPTUALLY) DIFFICULT QUESTION: This
problem may be challenging and is optional. Be sure to complete
the required questions before attempting this one.
Do

`help(filter)`to find out about the built-in function`filter`, then implement it using a recursive solution. Call your version`listfilter(fn, lst)`You can ignore what happens if the first argument is`None`.