Com S 342 --- Principles of Programming Languages EXERCISE 06: RECURSION OVER LISTS (File $Date: 2004/02/10 05:44:50 $) The purpose of this exercise is for you to learn about recursion over lists and how it relates to the grammar of lists. 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. [insert-before] Read section 1.2 of "Essentials of Programming Languages" (2nd ed., 2001) by Friedman, Wand, and Haynes. Write a procedure insert-before : (-> (symbol symbol (list-of symbol)) (list-of symbol)) that takes two symbols, where and what, and a list of symbols, los, and returns a list of symbols that is just like los, except that the symbol what is inserted just before the first occurrence of the symbol where in los, if any. For example (insert-before 'x 'q '()) ==> () (insert-before 'x 'q '(x y z x)) ==> (q x y z x) (insert-before 'x 'q '(a x y z)) ==> (a q x y z) (insert-before 'bef 'this '(rif bam bif bef bop bef bef)) ==> (rif bam bif this bef bop bef bef) 2. [insert-before-all] Read section 1.2 of "Essentials of Programming Languages" (2nd ed., 2001) by Friedman, Wand, and Haynes. Write a procedure insert-before-all : (-> (symbol symbol (list-of symbol)) (list-of symbol)) that takes two symbols, where and what, and a list of symbols, los, and returns a list of symbols that is just like los, except that the symbol what is inserted just before the each occurrence of the symbol where in los, if any. For example (insert-before-all 'x 'q '()) ==> () (insert-before-all 'x 'q '(x y z x)) ==> (q x y z q x) (insert-before-all 'x 'q '(a x y z)) ==> (a q x y z) (insert-before-all 'bef 'this '(rif bam bif bef bop bef bef)) ==> (rif bam bif this bef bop this bef this bef) 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 5 of "The Little Schemer" (fourth ed.) by Friedman and Felleisen. Or start on homework 2.