CS 61A Week 3 solutions LAB 1 EXERCISES: 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. LAB 2 EXERCISES: 2.25. Extract 7 (cadr (caddr '(1 3 (5 7) 9))) I did that one by knowing that "cadr" means "the second element" and "caddr" means "the third element," and the seven is the second element of the third element of the overall list. (car (car '((7))) (cadr (cadr (cadr (cadr (cadr (cadr '(1 (2 (3 (4 (5 (6 7)))))))))))) 2.53. Finger exercises. Note that it matters how many parentheses are printed! > (list 'a 'b 'c) (a b c) > (list (list 'george)) ((george)) > (cdr '((x1 x2) (y1 y2))) ((y1 y2)) > (cadr '((x1 x2) (y1 y2))) (y1 y2) > (pair? (car '(a short list))) #f > (memq 'red '((red shoes) (blue socks))) #f > (memq 'red '(red shoes blue socks)) (red shoes blue socks) 2.55 (car ''abracadabra) When you write 'foo it's just an abbreviation for (quote foo) no matter what foo is, and no matter what the context is. So ''foo is an abbreviation for (quote (quote foo)) If you enter the expression (car ''abracadabra) you are really saying (car (quote (quote abracadabra))) Using the usual evaluation rules, we start by evaluating the subexpressions. The symbol car evaluates to a function. The expression (quote (quote abracadabra)) evaluates to the unevaluated argument to (the outer) quote, namely (quote abracadabra) That latter list is the actual argument to car, and so car returns the first element of that list, i.e., the word quote. Another example: (cdddr '(this list contains '(a quote))) is the same as (cdddr '(this list contains (quote (a quote)))) which comes out to ((quote (a quote))) P.S.: Don't think that (car ''foo) is a quotation mark! First of all, the quotation mark has already been turned into the list for which it is an abbreviation before we evaluate the CAR; secondly, even if the quotation mark weren't an abbreviation, CAR isn't FIRST, so it doesn't take the first character of a quoted word! 2.27. Deep-reverse. This is a tough problem to think about, although you can write a really simple program once you understand how. One trick is to deep-reverse a list yourself, by hand, without thinking about it too hard, and THEN ask yourself how you did it. It's pretty easy for you to take a list like ((1 2 3) (4 5 6) (7 8 9)) and instantly write down ((9 8 7) (6 5 4) (3 2 1)) How'd you do it? The answer probably is, "I reversed the list and then I deep-reversed each of the sublists." So: (define (deep-reverse lst) ;; Almost working version (map deep-reverse (reverse lst))) But this doesn't QUITE work, because eventually you get down to the level of atoms (symbols or numbers) and you can't map over an atom. So: (define (deep-reverse lst) (if (pair? lst) (map deep-reverse (reverse lst)) lst)) If you tried to define deep-reverse without using map, you'll appreciate the intellectual power it gives you. You probably got completely lost in cars and cdrs, none of which are used in this program. Now that you understand the algorithm, it's possible to do what the problem asked us to do, namely "modify your reverse procedure": (define (deep-reverse lst) (define (iter old new) (cond ((null? old) new) ((not (pair? old)) old) (else (iter (cdr old) (cons (deep-reverse (car old)) new))))) (iter lst '())) This program will repay careful study, especially if you've fallen into the trap of thinking that there is an iterative form and a recursive form in which any problem can be expressed. Deep-reverse combines two subproblems. The top-level reversal is one that can naturally be expressed iteratively, and in this procedure the invocation of iter within itself does express an iteration. But the deep-reversal of the sublists is an inherently recursive problem; there is no way to do it without saving a lot of state information at each level of the tree. So the call to deep-reverse within iter is truly recursive, and necessarily so. Can you express the time and space requirements of this procedure in Theta(...) notation? HOMEWORK: 2.7 (define (upper-bound interval) (cdr interval)) (define (lower-bound interval) (car interval)) 2.8 ;; The smallest possible value for A-B is (smallest A)-(largest B). ;; Likewise, the largest value is (largest A)-(smallest B). (define (sub-interval x y) (add-interval x (make-interval (- (upper-bound y)) (- (lower-bound y))))) ;; It would also be okay to replicate the structure of add-interval instead of ;; using add-interval as a subprocedure, although this isn't exactly following ;; Alyssa's method as the problem suggests: (define (sub-interval x y) (make-interval (- (lower-bound x) (upper-bound y)) (- (upper-bound x) (lower-bound y)) )) 2.10 ;; An interval spans zero if its lower bound is negative (or zero) and ;; its upper bound is positive (or zero). ;; It's only the divisor that we have to worry about. (define (div-interval x y) (if (and (<= (lower-bound y) 0) (>= (upper-bound y) 0)) (error "Can't divide by an interval that spans zero.") (mul-interval x (make-interval (/ 1 (upper-bound y)) (/ 1 (lower-bound y)))))) 2.12 (define (make-center-percent c p) (let ((w (* c p 0.01))) (make-interval (- c w) (+ c w)))) ;; We multiply by 0.01 because p percent is a factor of p/100. ;; If you forgot about that part, it's a relatively minor error ;; for computer science purposes, although rather serious in a ;; practical engineering situation! (define (percent i) (* 100 (/ (/ (- (upper-bound i) (lower-bound i)) 2) (/ (+ (lower-bound i) (upper-bound i)) 2)))) ;; Slightly more efficient percent: (define (percent i) (* 100 (/ (- (upper-bound i) (lower-bound i)) (+ (lower-bound i) (upper-bound i))))) ;; Alternate versions, using the center-width procedures we already have: (define (make-center-percent c p) (make-center-width c (* c p 0.01))) (define (percent i) (* 100 (/ (width i) (center i)))) 2.20 The difficulty in writing recursive procedures that take any number of arguments is that you're going to be tempted to make a recursive call with only one argument, namely a list containing some of the original arguments, sort of like this: (define (same-parity . numbers) (cond ((null? (cdr numbers)) numbers) ((equal? (even? (car numbers)) (even? (cadr numbers))) (cons (car numbers) (same-parity (cdr numbers)))) ; WRONG! (else (same-parity (cons (car numbers) (cddr numbers)))))) ; WRONG! (define (even? num) (= (remainder num 2) 0)) Instead, the easiest thing to do is to define a helper procedure that *does* expect a list of numbers as its one argument. An advantage is that we can then separate out the first number, which is always accepted, as a special case: (define (same-parity tester . others) (define (helper numlist) (cond ((null? numlist) nil) ((equal? (even? tester) (even? (car numlist))) (cons (car numlist) (helper (cdr numlist)))) (else (helper (cdr numlist))))) (cons tester (helper others))) Once we know about higher-order functions, there's an even easier solution: (define (same-parity tester . others) (cons tester (filter (lambda (num) (equal? (even? tester) (even? num) (odd? num))) others))) or even more spectacularly shorter, (define (same-parity tester . others) (cons tester (filter (if (even? tester) even? odd?) others))) 2.22. What's wrong with iterative square-list? I've sort of answered this already, in talking about 2.18 (iterative reverse). A list (as opposed to an arbitrary list structure) MUST be made with (cons new-member rest-of-list) and not the other way around. That's why Louis's second try fails; he's making something that isn't a list, even though he does have the members in correct left-to-right order. He gets ((((() . 1) . 4) . 9) . 16) instead of (1 4 9 16), which in dotted representation would be (1 . (4 . (9 . (16 . ())))) Louis's first try fails because he starts by consing the square of 1 onto the empty list, etc. Here's an iterative square-list: (define (square-list x) (define (iter list answer) (if (null? list) answer (iter (cdr list) (cons (square (car list)) answer)))) (reverse (iter x nil))) In this version, iter is O(n) time and O(1) space, as desired. If we use the iterative definition of reverse, it too is O(n) time and O(1) space. So the whole thing is reasonably efficient in both time and space, even though it has what seems to be a redundant pass through the list to reverse it. If you're dealing with very large lists on very small computers, this is sometimes the only way to get an answer at all. 2.24. (list 1 (list 2 (list 3 4))) The printed result is (1 (2 (3 4))). The box and pointer diagram (in which XX represents a pair, and X/ represents a pair whose cdr is the empty list): --->XX--->X/ | | | | V V 1 XX--->X/ | | | | V V 2 XX--->X/ | | | | V V 3 4 The tree diagram: + / \ / \ 1 + / \ / \ 2 + / \ / \ 3 4 2.26. Finger exercises. Given (define x (list 1 2 3)) (define y (list 4 5 6)) > (append x y) (1 2 3 4 5 6) > (cons x y) ((1 2 3) 4 5 6) ;; Equivalent to ((1 2 3) . (4 5 6)) but that's not how ;; it prints! > (list x y) ((1 2 3) (4 5 6)) 2.29 Mobiles. Many people find this exercise very difficult. As you'll see, the solutions are quite small and elegant when you approach the problem properly. The key is to believe in data abstraction; in this problem some procedures take a MOBILE as an argument, while others take a BRANCH as an argument. Even though both mobiles and branches are represented "below the line" as two-element lists, you won't get confused if you use the selectors consistently instead of trying to have one procedure that works for both data types. (a) Selectors. They give us the constructor (define (make-mobile left right) (list left right)) The corresponding selectors have to extract the left and right components from the constructed list: (define (left-branch mobile) (car mobile)) (define (right-branch mobile) (cadr mobile)) Note that the second element of a list is its CADR, not its CDR! Similarly, the other selectors are (define (branch-length branch) (car branch)) (define (branch-structure branch) (cadr branch)) (b) Total weight: The total weight is the sum of the weights of the two branches. The weight of a branch may be given explicitly, as a number, or may be the total-weight of a smaller mobile. (define (total-weight mobile) (+ (branch-weight (left-branch mobile)) (branch-weight (right-branch mobile)) )) (define (branch-weight branch) (let ((struct (branch-structure branch))) (if (number? struct) struct (total-weight struct) ))) The LET isn't entirely necessary, of course; we could just say (branch-structure branch) three times inside the IF. (c) Predicate for balance. It looks like we're going to need a function to compute the torque of a branch: (define (torque branch) (* (branch-length branch) (branch-weight branch) )) Here we have used the BRANCH-WEIGHT procedure from part (b) above. Now, they say a mobile is balanced if two conditions are met: The torques of its branches must be equal, and its submobiles must be balanced. (If a branch contains a weight, rather than a submobile, we don't have to check if it's balanced. This is the base case of the recursion.) (define (balanced? mobile) (and (= (torque (left-branch mobile)) (torque (right-branch mobile)) ) (balanced-branch? (left-branch mobile)) (balanced-branch? (right-branch mobile)) )) (define (balanced-branch? branch) (let ((struct (branch-structure branch))) (if (number? struct) #t (balanced? struct) ))) If you find yourself wondering why we aren't checking the sub-sub-mobiles, the ones two levels down from the one we were asked about originally, then you're missing the central point of this exercise: We are doing a tree recursion, and these procedures will check the balance of all the smaller mobiles no matter how far down in the tree structure. (d) Changing representation. We change the two constructors to use CONS instead of LIST. The only other required change is in two of the selectors: (define (right-branch mobile) (cdr mobile)) (define (branch-structure branch) (cdr branch)) We're now using CDR instead of CADR because the second component of each of these data types is stored in the cdr of a pair, rather than in the second element of a list. Nothing else changes! The procedures we wrote in parts (b) and (c) don't include any invocations of CDR or CADR or anything like that; we respected the abstraction barrier, and so nothing has to change "above the line." 2.30 square-tree The non-MAP way: (define (square-tree tree) (cond ((null? tree) '()) ((number? tree) (* tree tree)) (else (cons (square-tree (car tree)) (square-tree (cdr tree)))))) The MAP way: (define (square-tree tree) (if (number? tree) (* tree tree) (map square-tree tree))) I'm not saying more about this because we talked about these programs in lecture. See the lecture notes! 2.31 tree-map This, too, can be done both ways: (define (tree-map fn tree) (cond ((null? tree) '()) ((not (pair? tree)) (fn tree)) (else (cons (tree-map fn (car tree)) (tree-map fn (cdr tree)))))) (define (tree-map fn tree) (if (not (pair? tree)) (fn tree) (map (lambda (subtree) (tree-map fn subtree)) tree))) In both cases I've replaced NUMBER? with (NOT (PAIR? ...)) so that the leaves of the tree can be symbols as well as numbers. (Obviously if the underlying function is squaring, then only numbers are appropriate.) 2.32 subsets (define (subsets s) (if (null? s) (list nil) (let ((rest (subsets (cdr s)))) (append rest (map (LAMBDA (SET) (CONS (CAR S) SET)) rest))))) Explanation: The subsets of a set can be divided into two categories: those that include the first element and those that don't. Each of the former (including the first element) consists of one of the latter (without the first element) with the first element added. For example, the subsets of (1 2 3) are not including 1: () (2) (3) (2 3) including 1: (1) (1 2) (1 3) (1 2 3) But the "not including 1" ones are exactly the subsets of (2 3), which is the cdr of the original set. So the LET uses a recursive call to find those subsets, and we append to them the result of sticking 1 (the car of the original set) in front of each. Note: It's really important to put the recursive call in a LET argument rather than use two recursive calls, as in (append (subsets (cdr s)) (map (lambda (set) (cons (car s) set)) (subsets (cdr s)))) because that would take Theta(3^n) time, whereas the original version takes Theta(2^n) time. Both are slow, but that's a big difference. 2.36 accumulate-n (define (accumulate-n op init seqs) (if (null? (car seqs)) nil (cons (accumulate op init (MAP CAR SEQS)) (accumulate-n op init (MAP CDR SEQS))))) 2.54 Equal? (define (equal? a b) (cond ((and (symbol? a) (symbol? b)) (eq? a b)) ((or (symbol? a) (symbol? b)) #f) ((and (number? a) (number? b)) (= a b)) ;; not required but ((or (number? a) (number? b)) #f) ;; suggested in footnote ((and (null? a) (null? b)) #t) ((or (null? a) (null? b)) #f) ((equal? (car a) (car b)) (equal? (cdr a) (cdr b))) (else #f))) Note: I think this is the cleanest way to write it--the way that's easiest to read. It's possible to bum a few procedure calls here and there. For example, the first two cond clauses could be ((symbol? a) (eq? a b)) ((symbol? b) #f) on the theory that eq? always returns #f if one argument is a symbol and the other isn't. Similarly, one could write ((null? a) (null? b)) ((null? b) #f) but I'm not sure the saving is worth the potential confusion. EXTRA PRACTICE 2.17 (define (last-pair lst) (if (null? (cdr lst)) lst (last-pair (cdr lst)))) 2.23 (define (for-each proc lst) (if (null? lst) #t (let ((ignored-result (proc (car lst)))) (for-each proc (cdr lst))))) Several people said, "Why not just use map?" There are two answers. First, it's inefficient because map will construct a list of all the results, and we don't care about the results. Second, map does not guarantee to apply the procedure argument to the list elements in left-to-right order. If you think it's inelegant to have a variable ignored-result whose value is something we don't care about, you're right. In chapter 3 we'll learn about an alternative notation: (define (for-each proc lst) (if (null? lst) #t (begin (proc (car lst)) (for-each proc (cdr lst))))) 2.37 matrices (define (matrix-*-vector m v) (map (LAMBDA (ROW) (DOT-PRODUCT ROW V)) m)) (define (transpose mat) (accumulate-n CONS NIL mat)) (define (matrix-*-matrix m n) (let ((cols (transpose n))) (map (LAMBDA (ROW) (MATRIX-*-VECTOR COLS ROW)) m))) Take a minute and try to appreciate the aesthetic beauty in these vector and matrix programs. In a conventional approach, matrix multiplication would involve three nested loops with index variables. These procedures seem closer to the mathematical idea that a matrix is a first-class thing in itself, not just an array of numbers. 2.38 fold-right vs. fold-left > (fold-right / 1 (list 1 2 3)) 1.5 This is 1/(2/3). > (fold-left / 1 (list 1 2 3)) 166.666666666667e-3 This is (1/2)/3, or 1/6. > (fold-right list nil (list 1 2 3)) (1 (2 (3 ()))) This is (list 1 (list 2 (list 3 nil))). > (fold-left list nil (list 1 2 3)) (((() 1) 2) 3) This is (list (list (list nil 1) 2) 3). In each example, notice that the values 1, 2, and 3 occur in left-to-right order whether we use fold-left or fold-right. What changes is the grouping: fold-right: f(1, f(2, f(3, initial))) fold-left: f(f(f(initial, 1), 2), 3) So the kind of function that will give the same answer with fold-right and fold-left is an ASSOCIATIVE operator, i.e., one for which (a op b) op c = a op (b op c)