Concrete Abstractions: Chapter 5

Exercise 5.6 Write a general purpose procedure, that when given two integers, low and high, and a procedure for computing a function f , will compute f(text{low}) + f(text{low} + 1) + f (text{low} + 2) + ... + f (text{high}). Show how it can be used to sum the squares of the integers from 5 to 10 and to sum the square roots of the integers from 10 to 100.

Solution: I wrote a iterative version of it because you have to directly apply the function to each number, i.e. it isn’t commutative.

(define add-integers 
  (lambda (f low high)
    (add-integers-iter f low high 0)))

(define add-integers-iter
  (lambda (f low high end)
    (if (= low high)
        (+ end (f low))
        (add-integers-iter f (+ low 1) high (+ end (f low))))))

; sum of squares from 5 to 10
(add-integers (lambda (x) (* x x)) 5 10)

; sum of square roots from 10 to 100
(add-integers (lambda (x) (sqrt x)) 10 100)

Exercise 5.11 Write a procedure make-verifier, which takes f and m as its two arguments and returns a procedure capable of checking a number. The argument f is itself a procedure, of course. Here is a particularly simple example of a verifier being made and used:

(define check-isbn (make-verifier * 11)) (check-isbn 0262010771)

The value #t is the “true” value; it indicates that the number is a valid ISBN.
As we just saw, for ISBN numbers the divisor is 11 and the function is simply f(i, d_i ) = i * di. Other kinds of numbers use slightly more complicated functions, but you will still be able to use make-verifier to make a verifier much more easily than if you had to start from scratch.

Solution:

(define make-verifier
  (lambda (f m)
    (lambda (n)
      (if (= (remainder 
              (map-f f n) 
              m) 0)
          #t
          #f))))


(define map-f
  (lambda (f n)
    (map-digit-f f n 0 1)))
     
(define map-digit-f
  (lambda (f n end i)
    (if (= n 0)
        end
        (map-digit-f f
                     (quotient n 10)
                     (+ end (f i (remainder n 10)))
                     (+ i 1)))))
    

Exercise 5.12 For UPC codes (the barcodes on grocery items), the divisor is 10, and the function f (i, d_i ) is equal to d_i itself when i is odd, but to 3d_i when i is even. Build a verifier for UPC codes using make-verifier, and test it on some of your groceries. (The UPC number consists of all the digits: the one to the left of the bars, the ones underneath the bars, and the one on the right.) Try making some mistakes, like switching or changing digits. Does your verifier catch them?

Solution: Yeah, the mistakes were caught. By the way you can see here how powerful high-order functions are.

(define UPC-f
  (lambda (i di)
    (if (odd? i)
        di
        (* 3 di))))

(define UPC-verifier
  (make-verifier UPC-f 10))

Exercise 5.13 Credit card numbers also use a divisor of 10 and also use a function that yields d_i itself when i is odd. However, when i is even, the function is a bit fancier: It is 2d_i if $latex d_i < 5$, and $latex 2d_i + 1$ if $latex d_i geq 5.$ Build a verifier for credit card numbers. In the dialog at the beginning of this section, did the order taker really mistype the number, or did the customer read it incorrectly? Solution: The credit card number was correct.

(define CC-f
  (lambda (i di)
    (if (odd? i)
        di
        (if (< di 5)
            (* 2 di)
            (+ (* 2 di) 1)))))

(define CC-verifier
  (make-verifier CC-f 10))

Exercise 5.13 The serial number on U.S. postal money orders is self-verifying with a divisor of 9 and a very simple function: f (i, d_i ) = di, with only one exception, namely, f (1, d_1 ) = -d_1. Build a verifier for these numbers, and find out which of these two money orders is mistyped: 48077469777 or 48077462766.
Actually, both of those money order numbers were mistyped. In one case the error was that a 0 was replaced by a 7, and in the other case two digits were reversed. Can you figure out which kind of error got caught and which didn’t? Does this help explain why the other kinds of numbers use fancier functions?

Solution: The reversal of digits, if the digit isn't the first one, isn't caught by this verification function. This is a reason for using fancier verification functions.

(define USPostal-f
  (lambda (i di)
    (if (= i 1)
        (- di)
        di)))

(define USPostal-verifier
  (make-verifier USPostal-f 9))

Exercise 5.17 Suppose you have a function and you want to find at what integer point in a given range it has the smallest value. For example, looking at the following graph of the function f (x) = x^2 - 2x, you can see that in the range from 0 to 4, this function has the smallest value at 1. We could write a procedure for answering questions like this; it could be used as follows for this example:

(integer-in-range-where-smallest (lambda (x) (- (* x x) (* 2 x)))
0 4)
1

Here is the procedure that does this; fill in the two blanks to complete it:

(define integer-in-range-where-smallest 
  (lambda (f a b)
    (if (= a b) 
        a
        (let ((smallest-place-after-a _________________________))
               (if __________________
                a 
                smallest-place-after-a)))))

Solution: I find it actually pretty hard to do fill in questions. Anyhow, here's the solution:

(define integer-in-range-where-smallest 
  (lambda (f a b)
    (if (= a b) 
        a
        (let ((smallest-place-after-a (integer-in-range-where-smallest f (+ a 1) b)))
               (if (< (f a) (f smallest-place-after-a))
                a 
                smallest-place-after-a)))))

Exercise 5.18 Consider the following definitions:

    (define make-scaled 
     (lambda (scale f)
      (lambda (x) 
       (* scale (f x)))))

    (define add-one 
     (lambda (x) 
      (+ 1 x)))
    (define mystery 
     (make-scaled 3 add-one))

For the following questions, be sure to indicate how you arrived at your answer:
a. What is the value of (mystery 4)?
b. What is the value of the procedural call ((make-scaled 2 (make-scaled 3 add-one)) 4)?

Solution: a. You can see that mystery gets a function from (make-scaled 3 add-one). This produces (lambda(x) (* 3 (add-one x))) which equals (lambda(x) (* 3 (+ 1 x))). Therefore the value is 15.
b. Let's take this call apart. (make-scaled 2 f) produces (lambda(x) (* 2 (f x)). Here f is (make-scaled 3 add-one) which produces the known (lambda(x) (* 3 (+ 1 x))) = 15 for x = 4. If you substitute this into (make-scaled 2 f) it becomes (lambda (x) (* 2 15)) = 30.

Exercise 5.20 Suppose the following have been defined:

    (define f 
     (lambda (m b)
      (lambda (x) (+ (* m x) b)))) 

    (define g (f 3 2))

For each of the following expressions, indicate whether an error would be signaled, the value would be a procedure, or the value would be a number. If an error is signaled, explain briefly the nature of the error. If the value is a procedure, specify how many arguments the procedure expects. If the value is a number, specify which number.
a. f
b. g
c. (* (f 3 2) 7)
d. (g 6)
e. (f 6)
f. ((f 4 7) 5)

Solution:
a. f is a procedure with two arguments.
b. g is a procedure returned by f with one argument.
c. (* (f 3 2) 7) evals to (* (lambda (x) (+ (* 3 x) 2) 7) = (* 23) which throws an error because * needs at least two arguments.
d. Here we got another value: (g 6) = ((f 3 2) 6) = (+ (* 3 6) 2) which equals 20.
e. f needs two arguments. So this throws an error.
f. (+ (* 4 5) 7) which equals 27.

Exercise 5.24 Consider the following procedure:

(define positive-integer-upto-where-smallest 
 (lambda (n f) ; return an integer i such that
  ; 1 <= i <= n and for all integers j
  ; in that same range, f(i) <= f(j) 
  (define loop
   (lambda (where-smallest-so-far next-to-try)
    (if (> next-to-try n)
     where-smallest-so-far
     (loop (if (< (f next-to-try)
                (f where-smallest-so-far))
            next-to-try
            where-smallest-so-far)
      (+ next-to-try 1)))))
  (loop 1 2)))

a. Write a mathematical formula involving n that tells how many times this procedure uses the procedure it is given as its second argument. Justify your answer.
b. Give a simple Theta order of growth for the quantity you determined in part a. Justify your answer.
c. Suppose you were to rewrite this procedure to make it more efficient. What (in terms of n) is the minimum number of times it can invoke f and still always determine the correct answer? Justify your answer. (You are not being asked to actually rewrite the procedure.)

Solution: a. If next > n then loop returns directly smallest-so-far, so there's no call of f. If next <= n then there are two calls in the if header. Therefore there are 2(n-1) function calls of f.
b. We can see that 2(n-1) = 2n - 2. 2n is the biggest term and 2 is just a factor, therefore \Theta(n).
c. We can save (f where-smallest-so-far) by adding it in the parameter list of loop. In the ideal case we just need to calculate (f where-smallest-so-far) one time and (f next-to-try) (n - 1) times. However, in the worst case there's no improvement.