Com S 342 --- Principles of Programming Languages EXERCISE 02: FLAT RECURSION WITH CONDITIONALS (File $Date: 2004/01/26 17:58:22 $) The purpose of this exercise is for you to learn some basic ideas about flat recursion over lists, with conditionals. As with all exercises, this is to be done individually. And it is due the day this topic is planned to be discussed in class, unless specified otherwise (see the syllabus at: http://www.cs.iastate.edu/~cs342/syllabus.shtml). As with all exercises, you have two choices for doing the work. You can either: - complete it as specified or - write down questions or problems that you had in trying to complete it. If you write down questions or problems you have, these should be detailed enough so that we can tell that you have read the materials and thought about them. (Don't just write: "I didn't understand how to do it". Instead, say what you tried and what you didn't understand.) During the class where this exercise is discussed, you should ask about these difficulties, and clear them up. Don't be shy; there will be other people with the same problem, and everyone can learn by discussing these issues. And you'll most likely see similar things on the homework, so it's best to understand them now. 1. [delete-even] Read chapter 3 of the "Little Schemer" (4th ed., 1996) by Friedman and Felleisen. Write a procedure, delete-even : (-> ((list-of number)) (list-of number)) that takes a list of numbers, lon, and returns the a list that is just like lon except that it does not have the even elements of lon. (Hint: Scheme has a predicate even? that tests to see if a number is even.) For example: (delete-even '(1 2 3 4)) ==> (1 3) (delete-even '(2 3 4)) ==> (3) (delete-even '(3 4)) ==> (3) (delete-even '(4)) ==> () (delete-even '()) ==> () (delete-even '(12 6 5 20 12 6 3 10 1 342 541 641 8)) ==> (5 3 1 541 641) (delete-even '(6 5 20 12 6 3 10 1 342 541 641 8)) ==> (5 3 1 541 641) (delete-even '(5 20 12 6 3 10 1 342 541 641 8)) ==> (5 3 1 541 641) (delete-even '(20 12 6 3 10 1 342 541 641 8)) ==> (3 1 541 641) Do this in Scheme and hand in a printout of your code and a transcript of your testing, showing the results on the tests above. (In the notation used above ==> separates the test from the expected result; to perform a test you run the code on the left of the ==>). 2. [Flat Recursion over Lists] Read chapter 3 of the "Little Schemer" (4th ed., 1996) by Friedman and Felleisen. Without Scheme's built-in procedures "list-ref" or "length", define a procedure nth-elt : (forall (T) (-> ((list-of T) number) T)) that, for all types T, when given a list of elements of type T, lst, and a number that is non-negative, n, returns the nth element of lst, starting at index 0, or prints an error when the list is too short. For example, (nth-elt '(a b c) 0) ==> a (nth-elt '(a b c) 1) ==> b (nth-elt '(b c) 0) ==> b (nth-elt '(a b c) 2) ==> c (nth-elt '(b c) 1) ==> c (nth-elt '(c) 0) ==> c (nth-elt '("astr" "bstr" "cstr" "dstr" "estr") 0) ==> "astr" (nth-elt '("astr" "bstr" "cstr" "dstr" "estr") 4) ==> "estr" (nth-elt '("bstr" "cstr" "dstr" "estr") 3) ==> "estr" (nth-elt '("cstr" "dstr" "estr") 2) ==> "estr" (nth-elt '("dstr" "estr") 1) ==> "estr" (nth-elt '("estr") 0) ==> "estr" Do this in Scheme and hand in a printout of your code and a transcript of your testing, showing the results on the tests above. (In the notation used above ==> separates the test from the expected result; to perform a test you run the code on the left of the ==>). WHAT TO HAND IN You should have at the beginning of class, written answers to the above questions (or written out questions and problems you encountered for each part). Make sure your name is on these. Attach the printouts, if any, requested above. ADDITIONAL READINGS If you have time, read chapter 4 of the "Little Schemer" (4th ed., 1996) by Friedman and Felleisen.