Exam I, CS 257

Some have said that I can't sing. But no one will say that I didn't sing.

- Florence Foster Jenkins

1. Fill in the two missing entries in this table: (5 points each)

   printed representation	box and pointer diagram
   (a b (c d) ())
   (a b (c) ((d) e f) g)

2. evaluate the following: (2 points each)

   expression	value
   (cons '(a b c) '(d e f))
   (list '(a b c) '(d e f))
   (caddr '(a b (c d) e f))
   (map even? '(1 2 3 4))
   (let ((a 1)) (let ((a 2) (b (+ a 2))) (list 'a a 'b b)))

3. Given the following code:

   (define (a-to-1 wd) (if (equal? wd 'a) 1 0)) (define (neato fn lst) (cond ((null? lst) 0) ((not (list? lst)) (fn lst)) (else (+ (neato fn (car lst)) (neato fn (cdr lst)))))) (define (foo expr) (neato a-to-1 expr))

   1. What does (foo '(a b c (a d) a)) return? (5 points)

   2. In one short English sentence, what does foo do? (5 points)

   3. Define bar, which adds up all the numbers in an s-expression, ignoring any non-numbers. Eg (bar '(a 1 2 (3 b))) gives 6. Use neato from above to make your definition very simple. (5 points)

4. Define the higher-order function curry that takes as arguments a function of two arguments F and a value X and returns a function that when passed an argument Y returns the result of applying F to X and Y. (10 points)

   Examples:

   ((curry + 3) 1)                                 ; 4
   
   ((curry cons 'dog) '(cat rat))                  ; (dog cat rat)
   
   (let ((f (curry assoc 'blood)))
     (f '((hair brown)(blood red)(tongue pink))))  ; (blood red)
   

5. Define replace, which takes three arguments: an s-expression E and two symbols A and B. It replaces every occurance within E of the symbol A by the symbol B. (10 points)

   Example:

   (replace '(a b c (a d) a) 'a 'aye)   ; (aye b c (aye d) aye)
   

6. Extra credit: Define the reshape function, which takes two s-expressions as arguments. These two sexprs should contain the same number of words embedded within them, and reshape returns a sexpr with the same ``shape'' as its first argument, but with successive words from inside its second argument substituted for successive words of its first argument. (3 points + respect)

   Examples:

   (reshape 'a '((((1)))))           ; 1
   
   (reshape '((((a)))) '1)           ; ((((1))))
   
   (reshape '(((a (b)))) '((1) 2))   ; (((1 (2))))
   
   (reshape '(((a (b))) (c d))
            '((1) (2 (((3))) 4)))    ; (((1 (2))) (3 4))