LAB 2A: 1. How to reverse the order in which coins are tried? One solution is to reverse the order of the numbers in FIRST-DENOMINATION: (define (first-denomination kinds-of-coins) (cond ((= kinds-of-coins 1) 50) ((= kinds-of-coins 2) 25) ((= kinds-of-coins 3) 10) ((= kinds-of-coins 4) 5) ((= kinds-of-coins 5) 1))) Another would be, using the original version of first-denomination, to change COUNT-CHANGE and CC so that the variable KINDS-OF-COINS counts upward instead of downward: (define (count-change amount) (cc amount 1)) (define (cc amount kinds-of-coins) (cond ((= amount 0) 1) ((or (< amount 0) (> KINDS-OF-COINS 5)) 0) ; changed here (else (+ (cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins) (cc amount (+ KINDS-OF-COINS 1)))))) ; changed here 2. Explore the efficiency. Here is what happens with (cc 5 2) in the original order, as in the book: > (cc 5 2) "CALLED" cc 5 2 "CALLED" cc 0 2 "CALLED" cc 5 1 "CALLED" cc 4 1 "CALLED" cc 3 1 "CALLED" cc 2 1 "CALLED" cc 1 1 "CALLED" cc 0 1 "CALLED" cc 1 0 "CALLED" cc 2 0 "CALLED" cc 3 0 "CALLED" cc 4 0 "CALLED" cc 5 0 2 (I've deleted the "RETURNED" lines in the trace; it's easier to read this way and doesn't affect our analysis.) To try out just pennies and nickels backwards, I modified first-denomination this way: (define (first-denomination kinds-of-coins) (cond ((= kinds-of-coins 1) 5) ((= kinds-of-coins 2) 1))) And here are the results: > (cc 5 2) "CALLED" cc 5 2 "CALLED" cc 4 2 "CALLED" cc 3 2 "CALLED" cc 2 2 "CALLED" cc 1 2 "CALLED" cc 0 2 "CALLED" cc 1 1 "CALLED" cc -4 1 "CALLED" cc 1 0 "CALLED" cc 2 1 "CALLED" cc -3 1 "CALLED" cc 2 0 "CALLED" cc 3 1 "CALLED" cc -2 1 "CALLED" cc 3 0 "CALLED" cc 4 1 "CALLED" cc -1 1 "CALLED" cc 4 0 "CALLED" cc 5 1 "CALLED" cc 0 1 "CALLED" cc 5 0 2 We get the same answer, but with 21 calls to CC instead of 13. Why? The extra calls are for attempts to match a small amount of money with a large coin -- for example, to use a nickel in counting four cents. When the coins are tried in the book's order, by the time we are thinking about four cents, we have already abandoned the idea of using nickels and so we quickly find the four-pennies solution. But in backward order, we have to discover that a nickel is too big for four cents, and then that a nickel is too big for three cents, and so on. (These situations give rise to the calls with a negative amount of money; notice that there aren't any like that in the first trace.) 3. Modify CC to take a sentence of denominations. (define (cc amount kinds-of-coins) (cond ((= amount 0) 1) ((or (< amount 0) (EMPTY? KINDS-OF-COINS)) 0) (else (+ (cc (- amount (FIRST KINDS-OF-COINS)) kinds-of-coins) (cc amount (BUTFIRST KINDS-OF-COINS)))))) LAB 2B: Skipping the ones that just say "try this"... 5. (define (+rat a b) (make-rational (+ (* (numerator a) (denominator b)) (* (denominator a) (numerator b))) (* (denominator a) (denominator b)))) 2.2 ;; Constructor and selector for segments ;; Note that we don't have to know what's inside a "point" for these ;; to work! (define (make-segment point1 point2) (cons point1 point2)) (define (start-segment seg) (car seg)) (define (end-segment seg) (cdr seg)) ;; Constructor and selector for points (define (make-point xcor ycor) (cons xcor ycor)) (define (x-point point) (car point)) (define (y-point point) (cdr point)) ;; midpoint of segment from P1(x1,y1) to P2(x2,y2) is ;; ( (x1+x2)/2 , (y1+y2)/2 ) (define (midpoint-segment seg) (make-point (/ (+ (x-point (start-segment seg)) (x-point (end-segment seg))) 2) (/ (+ (y-point (start-segment seg)) (y-point (end-segment seg))) 2))) ;; Alternate definition, maybe fewer keystrokes, ;; maybe even easier to read: (define (midpoint-segment seg) (let ((p1 (start-segment seg)) (p2 (end-segment seg))) (make-point (/ (+ (x-point p1) (x-point p2)) 2) (/ (+ (y-point p1) (y-point p2)) 2))) Note: If you wanted to write (define (make-segment x1 y1 x2 y2) ...) or something similar, it means you don't yet believe that abstract data types are legitimate things, valid arguments to procedures and so on. Just as in section 1.3 you had to learn to accept that procedures are just as good as numbers, now you have to accept that points (or any other abstract type) are just as good as numbers! 2.3 Since the hint suggests using exercise 2.2, let's represent a rectangle as two adjacent sides (adjacent so that we get one length and one width). (define (make-rectangle side1 side2) (cons side1 side2)) (define (first-leg rect) (car rect)) (define (second-leg rect) (cdr rect)) Perimeter and area: (define (perimeter rect) (* 2 (+ (length-segment (first-leg rect)) (length-segment (second-leg rect))))) (define (area rect) (* (length-segment (first-leg rect)) (length-segment (second-leg rect)))) (define (length-segment seg) (sqrt (+ (square (- (x-point (end-segment seg)) (x-point (start-segment seg)))) (square (- (y-point (end-segment seg)) (y-point (start-segment seg))))))) Different representation for rectangles: Note that the representation above really contains more information than necessary; it includes the common point twice, and it doesn't take into account that the angle between the two legs must be 90 degrees. So instead we could represent a rectangle using a BASE, which is a segment, and a HEIGHT, which is just a number (the length of the other segment). (define (make-rectangle base height) (cons base height)) (define (base-rectangle rect) (car rect)) (define (height-rectangle rect) (cdr rect)) Making the same perimeter and area procedures work: To do this we have to redefine first-leg and second-leg in terms of the new representation. The first leg can be just the base, but for the second leg we need some analytic geometry. Specifically, we need to know that if the slope of the base segment is Dy/Dx (using D for delta) then the slope of a perpendicular height should be -Dx/Dy. If we want the same perimeter and area procedures to work for either kind of rectangle, we have to have first-leg and second-leg check which kind we have, like this: (define (first-leg rect) (if (pair? (cdr rect)) (car rect) (base-rectangle rect))) (define (second-leg rect) (if (pair? (cdr rect)) (cdr rect) (let ((origin (start-segment (base-rectangle rect))) (endpoint (end-segment (base-rectangle rect))) (scale-factor (/ (height-rectangle rect) (length-segment (base-rectangle rect))))) (make-segment origin (make-point (+ (x-point origin) (* scale-factor (- (y-point origin) (y-point endpoint)))) (+ (y-point origin) (* scale-factor (- (x-point endpoint) (x-point origin))))))))) Alternatively, you might find it easier to redefine perimeter and area in terms of the new representation, and then to make them work for the old representation you'll have to define base-rectangle and height-rectangle in terms of first-leg and second-leg: (define (perimeter rect) (* 2 (+ (length-segment (base-rectangle rect)) (height-rectangle rect)))) (define (area rect) (* (length-segment (base-rectangle rect)) (height-rectangle rect))) (define (base-rectangle rect) (if (pair? (cdr rect)) (first-leg rect) (car rect))) (define (height-rectangle rect) (if (pair? (cdr rect)) (length-segment (second-leg rect)) (cdr rect))) Note that we don't want to check (pair? (cdr rect)) in the perimeter or area procedure, because those procedures are above the abstraction barrier -- they shouldn't have to know about the internal representation. 2.4 I hope you are awed by this problem. Isn't it beautiful that you can use procedures to capture what you used to consider "data" like this? Anyway, suppose we have two objects A and B, and we've made a pair out of them with this version of cons. Just to make it easier to talk about, let's give that pair a name: (define mypair (cons A B)) The value of the symbol "mypair" is now the procedure created by (lambda (m) (m A B)) Now what happens when we evaluate (car mypair)? By the substitution rule, we must substitute the value of "mypair" for "z" in the body of car: ((lambda (m) (m A B)) (lambda (p q) p)) This expression has two elements, each of which is a lambda-expression. As usual, we evaluate an expression by taking its first subexpression as a function to be applied to the second subexpression as argument. The body of the first subexpression is (m A B). Into that body we substitute the argument for the formal parameter m: ((lambda (p q) p) A B) To evaluate THAT expression, we substitute A for p and B for q in body of the function. That body is just "p" so we get A as the value of the original expression, as desired. The corresponding definition of cdr is, of course, (define (cdr z) (z (lambda (p q) q))) 2.18. Reverse a list. (define (reverse lst) (define (iter old new) (if (null? old) new (iter (cdr old) (cons (car old) new)))) (iter lst nil)) It's worth thinking about the fact that this function is MUCH easier to write as an iterative procedure than as a recursive one. There's something inherently reversing about the iterative structure, when applied to a list. Here's the reason. The basic accumulator for lists is cons; this is analogous to the role played by + in most of the earlier examples of recursive/iterative problems. However, + is commutative; it doesn't matter whether you add a series front-to-back or back-to-front. Cons is NOT commutative, and the pair-diagram representation of a list is NOT left-right symmetric. The only natural way to build up a list is right-to-left. If you want the list (A B C) first you cons C onto nil, then you cons B onto that pair, then you cons A onto that one. The difference between the usual iterative control structure and the usual recursive one is that the former accumulates its result "on the way down" the chain of recursive invocations; the first invocation adds the first term to the result and then does the second invocation. A recursive structure, on the other hand, accumulates terms "on the way up" the chain; it keeps doing recursive invocations, keeping pending the addition of the partial result into the larger result. When you reach the end condition, the invocations start terminating, and that's when the accumulation (using + or whatever) happens. In a list processing situation, the trace for recursion looks like this: (recursive-proc '(a b c)) (cons (some-fn 'a) (recursive-proc '(b c))) ----------------------- V (cons (some-fn 'b) (recursive-proc '(c))) --------------------- V (cons (some-fn 'c) nil) The trace for iteration is (iterative-proc '(a b c)) (iterative-helper '(a b c) nil) (iterative-helper '(b c) (cons (some-fn 'a) nil)) (iterative-helper '(c) (cons (some-fn 'b) (cons (some-fn 'a) nil))) and so on. You can see that the reversal we wanted in this problem "comes free" in the iterative solution. If you want to write reverse recursively, you need left-right symmetrical list operations. Using the word/sentence data abstraction you could say (define (reverse lst) (if (empty? lst) nil (sentence (reverse (butfirst lst)) (first lst)))) but this will be really slow, O(n^2). Also, it's a data abstraction violation unless the argument is really a sentence, i.e., a list of words, not a list of lists. You can avoid the DAV by saying (define (reverse lst) (if (null? lst) nil (append (reverse (cdr lst)) (list (car lst))))) Compared to the SENTENCE solution, this one has an extra call to LIST because APPEND requires lists as its arguments. This solution is still O(n^2) time.