CSE 341 -- Assignment 2

October 2, 1995
Due in quiz sections October 17, 1995


  1. Make sure you are familiar with recursion, and in particular the recursion templates described in Chapter 8. Do exercises 8.17, 8.18, 8.20, 8.24, 8.29, 8.43. Don't hand in anything for this question, though (since the answers are all in the back of the book).

  2. Make sure you are familiar with applicative programming, as described in Chapter 7. Do exercises 7.1, 7.3, 7.5, 7.17, and 7.19. Again, don't hand in anything for this question.

  3. Write a recursive function twice that takes a list of atoms (which may be empty), and returns a new list of the same length, where each element in the new list is a list of length two, with the original element repeated. Examples: (twice '(x y z)) evaluates to ((X X) (Y Y) (Z Z)) (twice '(fred)) evaluates to ((FRED FRED)) (twice '()) evaluates to NIL

  4. Write another version of twice, which should use one of the applicative operators instead. This version should not be recursive.

  5. Write a variation of the twice function, called flat-twice, that takes a list of atoms (which may be empty), and returns a new list with each atom repeated. You can use either recursion or applicative programming (but no side effects). Examples: (flat-twice '(x y z)) evaluates to (X X Y Y Z Z) (flat-twice '(fred)) evaluates to (FRED FRED) (flat-twice '()) evaluates to NIL

  6. Write a recursive function boolean-eval that takes a list, which should be a boolean expression, and returns its value. Don't use the built-in function eval in writing boolean-eval (which would result in a one-line solution!) -- the idea is to write your own evaluation function for booleans. Hint: this function should be multiple recursive. We can define a boolean expression as one of the following: Examples: (boolean-eval nil) evaluates to NIL (boolean-eval '(and t t) evaluates to T (boolean-eval '(not (and t (or t nil))) evaluates to NIL