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
    
    
    (defun twice (x) 
       (if (null x) nil 
          (cons (list (first x) (first x)) 
                (twice (rest x)))))
    
    
    

  4. Write another version of twice, which should use one of the applicative operators instead. This version should not be recursive.
    
    
    (defun twice (x) 
       (mapcar #'(lambda (a) (list a a)) x))
    
    
    

  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
    
    
    ;;; using recursion 
    (defun flat-twice (x) (if (null x) nil 
       (let ((head (first x))) 
          (cons head (cons head (flat-twice (rest x)))))))
    
    ;;; using applicative programming
    (defun flat-twice (x) (reduce #'append (twice x)))
    
    
    

  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
    
    
    ;;; note that in this solution we assume the following that we will
    ;;; get input that fits the above template for boolean expressions.
    ;;; and if we can detect that the input does not fit we call it 't' 
    ;;; in the style of lisp.
    
    (defun boolean-eval (x) 
      (cond ((null x) nil)          ;nil atom is nil
            ((atom x) t)            ;any other atom is t
            ((equal (first x) 'and) ;use built in function 'and' on
    				;the results of recursive calls to 
    				;the second and third arguments
    		(and (boolean-eval (second x)) (boolean-eval (third x))))
            ((equal (first x) 'or)  ;use built in function 'or' on
    				;the results of recursive calls to 
    				;the second and third arguments
    		(or (boolean-eval (second x)) (boolean-eval (third x))))
            ((equal (first x) 'not) ;use built in function 'not' on 
    				;the result of a recursive call to 
    				;the second argument
    		(not (boolean-eval (second x))))
            (t t))) 		;anything else is considered t