Quiz 4 Answers, CS 257

your time's not wasted
believe what I say
your big investment's
gonna pay off someday

- Timbuk 3

1. What values are printed when you type each of the following to Scheme? (2 points each)

   expression	result
   (every count '(aye be c deeee))	(3 2 1 5)
   (keep (lambda (x) (< (count x) 4))       '(the quick brown fox))	(the fox)
   (define (foo f w)    (f w 'four w)) (foo (lambda (x y z)        (word y (+ (* 10 x) z)))      1)	four11
   (accumulate (lambda (x y) (word x '- y))             (every (lambda (w) (word w w))                    '(a be sea)))	aa-bebe-seasea
   (sentence (if (< 1 0) '(bip) '(bop boop)) 'shazam)	(bop boop shazam)

2. Define a function ave that takes a sentence of words and numbers as its sole argument, and returns the average of the numbers in the given sentence. (10 points)

   Eg (ave '(7 roses 8 carnations and 10 tulips)) returns 8.3333. (10 points)

   ---

   ;;; Simple definition using higher order functions
   
   (define (ave s)
     (/ (accumulate + (keep number? s))
        (count (keep number? s))))
   
   
   ;;; Alternate definition using a helper function
   
   (define (ave s)
     (ave-nums (keep number? s)))
   
   (define (ave-nums s)
     (/ (accumulate + s) (count s)))
   
   
   ;;; Reasonable recursive definition.  Higher order functions sure are succinct.
   
   (define (ave s)
     (/ (sum-nums s) (count-nums s)))
   
   (define (count-nums s)
     (if (empty? s)
         0
         (+ (if (number? (first s)) 1 0)
   	 (count-nums (butfirst s)))))
   
   (define (sum-nums s)
     (if (empty? s) 0
         (+ (if (number? (first s)) (first s) 0)
   	 (sum-nums (butfirst s)))))
   
   
   ;;; Unpleasant recursive definition, NOT RECOMMENDED!
   ;;; Uses count-nums helper function from above.
   
   (define (ave s)
     (cond ((empty? s)
   	 ;; this is undefined, and returning zero simplifies things, so:
   	 0)
   	((number? (first s))
   	 (/ (+ (* (ave (butfirst s))
   		  (- (count-nums s) 1))
   	       (first s))
   	    (count-nums s)))
   	(else
   	 (ave (butfirst s)))))
   

3. Extra credit: Explain briefly in English (a) what foo does and (b) how it works.
   Then (c) demonstrate your understanding by saying what (foo 'a1b2c3d4e5 '6fgh7ijk8m) returns. Note that the definition is not recursive: foo does not call itself.
   This is really tricky, but rewarding. (5 points)

   (define (foo a b)
     ((lambda (f aa bb) (f f aa bb))
      (lambda (g aaa bbb)
        (cond ((empty? aaa) '())
   	   ((number? (first bbb))
   	    (sentence (first aaa)
   		      (g g (butfirst aaa) (butfirst bbb))))
   	   (else (g g (butfirst aaa) (butfirst bbb)))))
      a
      b))
   

   ---

       She was fading fast, but I managed to get it in, in time.
       ``The manifestation of the universe as a complex idea unto itself as opposed to being in or outside the true Being of itself is inherently a conceptual nothingness or Nothingness in relation to any abstract form of existing or to exist or having existed in perpetuity and not subject to laws of physicality or motion or ideas relating to non-matter or the lack of objective Being or subjective otherness.''
       It was a subtle concept but I think she understood before she died.
   

   - from "Mr. Big" by Woody Allen

   a. (foo word-a word-b) returns an ordered sentence of those characters in word-a for which the corresponding character in word-b is a digit. In the event that word-b is shorter than word-a an error will be encountered.

   b. The middle of the function is a straightforward recursive implementation of the functionality described above, which could have been written:

   (define (foo a b)
     (cond ((empty? a) '())
   	((number? (first b))
   	 (sentence (first a)
   		   (foo (butfirst a) (butfirst b))))
   	(else (foo (butfirst a) (butfirst b)))))
   

   In order to get the body to be able to call itself, the whole thing is packed up in a lambda (the second one in the body of foo) that expects an extra argument g which it calls when it wants to recurse. The first lambda in the body of foo arranges for the lambda containing the meat of the function to be passed itself as an extra arg, so it can call itself. Of course when it calls itself, it must add itself as an extra parameter, so its recursive invocation of itself knows in turn how to make a recursive call to itself. That's what the (g g ...) is for.

   c.
   a1b2c3d4e5
   6fgh7ijk8m
   *---*---*-
   A---C---E-
   therefore the answer is: (a c e)