Due: &recursion-preconditions-due; Summary: Write several procedures that safely and efficiently accomplish tasks by recursing over lists. Purposes: To further practice writing recursive procedures, documenting procedures, and verifying preconditions. Expected Time: Two to three hours. Collaboration: We encourage you to work in groups of size three. You may, however, work alone or work in a group of size two or size four. You may discuss this assignment with anyone, provided you credit such discussions when you submit the assignment. Submitting: Email your answer to &grader-email;. The title of your email should have the form &recursion-preconditions-subject; and should contain your answers to all parts of the assignment. Scheme code should be in the body of the message. Warning: So that this assignment is a learning experience for everyone, we may spend class time publicly critiquing your work.

a. Using the 6 P's, document the reverse procedure. b. Suppose the reverse procedure were not included in Scheme. Could you write it yourself? Certainly! It should be possible to implement reverse recursively. One strategy is to use the standard recursive formulation of (define my-reverse (lambda (lst) (if (null? lst) base-case (combine (car lst) (my-reverse (cdr lst)))))) Finish this implementation. When using this strategy, you'll need to think about this question: Suppose I've reversed the cdr of a list. What do I do with the car to get the reversal of the complete list? c. Of course, you've seen more than one strategy for writing recursive procedures. Another possibility is to use a helper that includes a what I've done so far parameter. For example, (define my-other-reverse (lambda (lst) (my-other-reverse-helper null lst))) (define my-other-reverse-helper (lambda (reversed-so-far remaining-elements) (if (null? remaining-elements) base-case (my-other-reverse-helper (modify reversed-so-far) (cdr remaining-elements))))) Finish this implementation. d. Take one of the versions of reverse that you just wrote and modify it so that it verifies its preconditions.

The the lab on verifying preconditions offers the following definition of the index-of procedure, which finds the index of a value in a list. a. What preconditions should index-of have? b. Rewrite index-of using tail recursion and a husk and kernel. It should verify its preconditions.

Note: This problem appears as Extra 1 in the lab on verifying preconditions. Consider a procedure, (list-substitute lst old new), that builds a new list by substituting new for old whenever old appears in lst. > (list-substitute (list "black" "red" "green" "blue" "black") "black" "white") (list "white" "red" "green" "blue" "white") > (list-substitute (list "black" "red" "green" "blue" "black") "yellow" "white") (list "black" "red" "green" "blue" "black") > (list-substitute null "yellow" "white") () a. Document this procedure, making sure to carefully consider the preconditions. b. Implement this procedure, making sure to check the preconditions.

Note: This problem appears as Extra 2 in the lab on verifying preconditions. Consider a procedure, (spots-substitute spots old new), that, given a list of spots and two colors, makes a new copy of spots by using the color new whenever old appeared in the original spots. a. What preconditions does this procedure have? b. Implement this procedure, using the husk-and-kernel structure to ensure that old and new are rgb colors and that spots is a list of spots, before starting the recursion.

Define and test a Scheme procedure, (unriffle lst), that takes a list as argument and returns a list of two lists, one comprising the elements in even-numbered positions in the given list, the other comprising the elements in odd-numbered-positions. > (unriffle (list 'a 'b 'c 'd 'e 'f 'g 'h 'i)) ((a c e g i) (b d f h)) > (unriffle (list)) (() ()) > (unriffle (list 'a)) ((a) ()) > (unriffle (list 'b)) ((b) ()) > (unriffle (list 'a 'b)) ((a) (b)) Hint: There are many ways to solve this problem. Before writing code, try solving it by hand to develop your algorithm.

Students who provide correct procedures for each question will earn a check. Students who provide exceptionally elegant solutions may receive a higher grade. Students who provide oddly formatted or inelegant solutions to the problems may be publicly critiqued for their odd formatting and inelegance, and will also receive a grade penalty.