Quiz 5 Answers, CS 257

It is vain to do with more what can be done with fewer.

- William of Occam, 14th century

The lyf so short, the craft so long to lerne.

- Chaucer

Experience helps you recognize a mistake
when you make it again.

- Dorothy Parker

1. Consider the following definition:

   (define (foo n)
     (cond ((= n 0) 1)
   	((= n 1) 2)
   	((= n 2) 5)
   	(else (+ (foo (- n 1)) (foo (- n 3))))))
   

   Fill in the five missing elements in the right hand column. (2 points each)

   n	(foo n)
   0	1
   1	2 (base case)
   2	5
   3	6 =5+1
   4	8 =6+2
   5	13 =8+5
   6	19 =13+6

2. everynum takes two arguments, a function and a sentence, and returns the same sentence it was passed except that the given function has been applied to every number in the sentence.

   For instance
    (everynum (lambda (x) (* x x)) '(2 for the show 3 to get ready 4 to go)) evaluates to (4 for the show 9 to get ready 16 to go).

   everynum can be defined using higher order functions:

   (define (everynum f sen)
     (every (lambda (x) (if (number? x)
   			 (f x)
   			 x))
   	 sen))
   

   Define everynum using recursion instead. (10 points)

   ---

   (define (everynum f sen)
      (if (empty? sen)
          '()
          (let ((x (first sen)))
             (se (if (number? x) (f x) x)
                 (everynum f (bf sen))))))
   

3. Use nested let forms to drastically shorten this expression: (10 points)

   (sentence (sentence 'um 'diddle 'diddle 'diddle 'um 'diddle 'ay)
   	  (sentence 'um 'diddle 'diddle 'diddle 'um 'diddle 'ay)
   	  (word (word 'super 'cali 'fragilistic 'expialidocious) '!)
   	  (sentence 'even 'though 'the 'sound 'of 'it
   		    'is 'something 'quite 'atrocious)
   	  (word (word 'super 'cali 'fragilistic 'expialidocious) '!)
   
   	  (sentence 'um 'diddle 'diddle 'diddle 'um 'diddle 'ay)
   	  (sentence 'um 'diddle 'diddle 'diddle 'um 'diddle 'ay)
   	  'shes (word (word 'super 'cali 'fragilistic 'expialidocious) '!)
   	  (word 'super 'cali 'fragilistic 'expialidocious)
   	  (word 'super 'cali 'fragilistic 'expialidocious)
   	  (word (word 'super 'cali 'fragilistic 'expialidocious) '!))
   

   ---

   (let ((d 'diddle)
         (s (word 'super 'cali 'fragilistic 'expialidocious)))
     (let ((s! (word s '!))
           (u (se 'um d d d 'um d 'ay)))
       (se u  u  s!
           (se 'even 'though 'the 'sound 'of 'it
               'is 'something 'quite 'atrocious)
           s!   u  u  'shes s!  s  s  s!)))
   

4. Extra credit: Given these definitions

   (define (a f g) (lambda (h x) (f h (g h x))))
   (define (b f g) (lambda (h x) (f (lambda (y) (g h y)) x)))
   (define (n0 f x) x)
   (define (n1 f x) (f x))
   (define n2 (a n1 n1))
   (define n3 (a n1 n2))
   

   what does

   (* 2
      ((b n3 (a n2 (b (b n3 (a (b n2 n2) n3)) (a n2 n3))))
       (lambda (x) (+ x 1))
       12))
   

   return, and why? (5 points)

   ---

   Try it. I warned you that it was diabolical!

   Hints for figuring it out:

   1. This is somehow related to the repeated function.
      

   2. Work out the following expressions, in order:

      (define (s x) (word 's x))
      (n0 s 'nake)
      
      (n1 s 'nake)
      
      (n2 s 'nake)
      
      ((b n0 n2) s 'nake)
      
      ((b n2 n0) s 'nake)
      
      ((a n0 n2) s 'nake)
      
      ((a n2 n0) s 'nake)
      
      (n3 s 'nake)
      
      ((a n1 n3) s 'nake)
      
      ((a n2 n2) s 'nake)
      
      ((a n3 n1) s 'nake)
      
      ((a n2 n3) s 'nake)
      
      ((b n2 n3) s 'nake)