CS61A			MIDTERM I REVIEW		SPRING 2004

1.  (butfirst '(help!))

    (lambda (x) (/ x 0))
    
    (+ 27 '(word 1 0))

    (and 127 ((lambda (y) #f)))
    
    ((lambda (foo)
        (lambda (for)
	   (foo for)))
     (lambda (x) (* x x)))

    ((lambda (x) (* 2 (x x))) (lambda (y) (* 4 (y y))))

    (cond (first '(1 2 3))
	  (else 'foo))

    (if (23) (23) (23))

    ((let ()
       (lambda () 2)))

    (every (lambda (x) (word (first x) '- x)) '(waiting for my rocket to come))
    
    Given: (define (compose f g) (lambda (x) (f (g x))))
    Evaluate: (compose compose compose)



2.  Here are some definitions:

    (define (square x) (* x x))

    (define (foo x y) x)

    (define (bar x y) (* x y y))   ;; treat as one call to *

    a) How many times is * called when we evaluate 
       (foo (square (* 1 1)) (square (* 1 1)))
       
       in normal order? _____________________________

       in applicative order? ___________________________

    b) How many times is * called when we evaluate 
       (bar (square (* 1 1)) (square (* 1 1)))

       in normal order?  __________________________________

       in applicative order? ________________________________







3.  Given a function FOO:

    (define (foo n)
       (if (< n 2)    
           1    
           (+ (baz (- n 1))       
              (baz  (- n 2))))))

    For each of the following definitions of BAZ, state the order of
    growth of FO0.

    o (define baz fib)                       

    o (define (baz n) (+ n (- n 1))) 

    o (define baz foo) 
   
    o (define baz factorial)                  




4.  Write a procedure interleave, which takes two sentences as arguments
    and returns a sentence containing the first sentence, then the first
    element of the second sentence, then the second of the first sentence,
    then the second of the second sentence, etc. etc.

    > (interleave '(dont so to away) '(be quick walk))
    (dont be so quick to walk away)

    > (interleave '(i feel) '(cant the way i did before))
    (i cant feel the way i did before)



5.  Write the function FOR-AND-REV? that takes a word and returns true
    if the word contains a two-letter sequence, and the same sequence
    in the reverse order.

    STk> (for-and-rev? 'radar)               ;; ra & ar
    #t
    STk> (for-and-rev? pop)                  ;; po & op
    #t
    STk> (for-and-rev? 'aeiou)
    #f



6.  Rewrite the following without using IF or COND. Feel free to use
    NOT, AND, OR and MEMBER?.

    (define (good-enuf? a b c)
       (cond ((equal? a b) #t)
             ((sentence? c) #t)
	     ((odd? (+ a b c)) (if (equal? (- a b) -2) #t #f))
             (else #f)))




7.  Please define a procedure called make-keeper that takes a unary 
    predicate function as an argument and returns a procedure that,
    when invoked on a sentence argument, will keep only those elements
    that satisfy the predicate.

    > ((make-keeper even?) '(1 2 3 4 5 6))
    (2 4 6)

    You may assume that the input to make-keeper will always be a unary
    function and that the input to the returned procedure will always
    be a sentence.

    (a) Write make-keeper using HOFs but NO helpers
    (b) Rewrite make-keeper without using HOFs or helpers (lambda's are OK)



8.  Fill in the blank to get the desired value:

    STk> (every __________________________________________ '(cs61a 12 his))
    ()
    
    STk> ((lambda (x) (x x x)) _____________________________________)
    silver



9.  A word is a doublet of another word of if they differ in exactly one letter. 
    For example "noise" and "poise" are doublets. So are "poise" and "posse," 
    and "game" and "tame." Words that are the same are not considered
    doublets. Write a DOUBLET? predicate takes two words as arguments
    and returns true if they are doublets and false if they're not. Do
    not define any helpers. (Hint: to test when you have "run out" of a
    word use EMPTY?) 



10. Remember REPEATED from homework? Here is one way to define it:

    (define (repeated f n)
      (lambda (x) 
        (if (= n 0)
	    x
	    ((repeated f (- n 1)) (f x)))))

    Use it to write the function COUNT-TO, which takes a positive
    integer and returns a sentence of numbers from 1 to that number:

    STk> (count-to 6) 
    (1 2 3 4 5 6)
 
    Fill in the blanks:
 
    (define (count-to n)
    
       ((repeated __________________________________________________ n) '(1)))

                     

                                             
11. Write a procedure named constant-fn? that takes two arguments: 
    a function of one argument and a sentence of numbers.  It should
    return #t if the value returned by the function is always the same
    for all numbers in the argument sentence.

    > (constant-fn? sqrt '(2 3 4 5 6))
    #f

    > (constant-fn? (lambda (x) 4) '(5 3 88 2 100 7 8 9))
    #t

    > (constant-fn? (lambda (a) (< a 10)) '(22 23 24 25 26 27))
    #t

    > (constant-fn? (lambda (a) (< a 10)) '(5 7 9 11))
    #f



12. Write make-constant-checker that takes a function as an argument.
    It should return a function that takes a sentence of numbers as
    an argument, returning #t if the value returned by the original 
    functions is always the same for all of the numbers in the argument
    sentence.
    
    > (define not-spanning-ten (make-constant-checker (lambda (a) (< a 10))))
    not-spanning-ten
    
    > (not-spanning-ten '(22 23 24 25 26 27))
    #T
 
    > (not-spanning-ten '(5 7 9 11))
    #F

    Write one version WITHOUT USING constant-fn? and write one USING 
    constant-fn?