HW 5 Solutions: 1. Part A: (car foo) Part B: (cdr foo) This problem should be relatively straightforward if you use box-and-pointer diagram. 2. (define (swap-content foo bar) (let ((temp-car (car foo)) (temp-cdr (cdr foo))) (set-car! foo (car bar)) (set-cdr! foo (cdr bar)) (set-car! bar temp-car) (set-cdr! bar temp-cdr))) Here, the important lesson to learn is that you cannot just do something like "(define temp foo) (set! foo bar) (set! bar temp)" 3. (define (vector-swap! vec1 vec2) (define (loop n) (if (= n (vector-length vec1)) 'okay (begin (let ((temp (vector-ref vec1 n))) (vector-set! vec1 n (vector-ref vec2 n)) (vector-set! vec2 n temp)) (loop (+ n 1)))))) (loop 0)) Here we use a straightforward iterative loop to go through each index and make the swap. 4. (define (repeat? ls n) (define seen-before (make-vector n #f)) (define (loop ls) (cond ((null? ls) #t) ((vector-ref seen-before (car ls)) #f) (else (vector-set! seen-before (car ls) #t) (loop (cdr ls))))) (loop ls)) Here, seen-before is a storage vector used to keep track of what we have already seen. The element at index k in the seen-before vector is #f we have not seen the number k in the input list and #t if we have. This program runs in linear time because it takes constant time to access an element in a vector. 5. (define (count-ways x y) (define memory (make-vector (+ x 1) nil)) (vector-map! (lambda (in) (make-vector (+ y 1) nil)) memory) (define (cw-helper x y) (cond ((or (= x 0) (= y 0)) 1) ((null? (vector-ref (vector-ref memory x) y)) (let ((answer (+ (cw-helper (- x 1) y) (cw-helper x (- y 1))))) (vector-set! (vector-ref memory x) y answer) answer)) (else (vector-ref (vector-ref memory x) y)))) (cw-helper x y)) This is very similar to the memoized fibs shown in lecture. 2 things to note: 1. To create our memory vector, we needed a vector-map! instead of something like (make-vector (+ x 1) (make-vector (+ y 1) nil)) Because (make-vector (+ y 1) nil) will get evaluated first and every element of the outer vector will point to the same inner vector. 2. We gave length (+ x 1) and (+ y 1) to the memory vector so that we can vector-ref back to them easier. Remember that vectors start indexing at 0. 3.51 stream-ref > (stream-ref x 5) 1 2 3 4 5 5 > (stream-ref x 7) 6 7 7 > The repeated last number in each case is the actual value returned by stream-ref; the other numbers are printed by show. The only numbers shown are the ones we haven't already computed. If we ask for a value nearer the front of the stream, nothing is SHOWn at all: > (stream-ref x 4) 4 > Notice that the first element of the stream is zero, not one -- why isn't the zero printed? Answer: It was printed when you defined X in the first place. NOTE: The important thing to take away from this example is that if DELAY didn't involve memoization, the printed results would be quite different. All the numbers would be printed every time. 3.53 implicit definition Try it yourself! We know the first element of S is 1 and the STREAM-CDR is the result of adding S and S, so we get: 1 ... + 1 ... -------- 2 ... So the second element must be 2. That means we have: 1 2 ... + 1 2 ... ---------- 2 4 ... So the third element is 4, and so on. 3.54 factorials (define (mul-streams s1 s2) (stream-map * s1 s2)) (define factorials (cons-stream 1 (mul-streams FACTORIALS INTEGERS))) will give you the stream {1 1 2 6 24 ...} starting with zero factorial, or (define factorials (cons-stream 1 (mul-streams FACTORIALS (STREAM-CDR INTEGERS)))) will give the stream {1 2 6 24 ...} starting with one factorial. 3.55 partial sums (define (partial-sums s) (define result (cons-stream (stream-car s) (add-streams (stream-cdr s) result))) result) Alternatively, it can be done explicitly: (define (partial-sums s) (define (helper s sofar) (cons-stream sofar (helper (stream-cdr s) (+ sofar (stream-car s))))) (helper (stream-cdr s) (stream-car s))) but the first version is way cooler. 3.56 merge and Hamming's problem This is easy: > (define S (cons-stream 1 (merge (scale-stream S 2) (merge (scale-stream S 3) (scale-stream S 5))))) S > (show-stream S 41) (1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 60 64 72 75 80 81 90 96 100 108 120 125 128 135 144 150 ...) 7. (define (smooth-stream strm n) (stream-map (lambda (x) (/ x n)) (stagger-add strm n))) (define (stagger-add strm n) (if (= n 1) strm (stream-map + strm (stream-cdr (stagger-add strm (- n 1)))))) Calling (stagger-add ints 4) would create the stream 1 2 3 4 5 6 7 ... 1 2 3 4 5 6 7 ... 1 2 3 4 5 6 7 ... 1 2 3 4 5 6 7 ... -------------------------- 10 14 18 22 26 30 ... Because we add n copies of the stream staggered as above. Hence, to finish smooth-stream, we just divide every element of the stagger-added stream by n. 8. 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111 ... This is the set of all possible binary strings. Strings composed of just the letters "1" and "0" 10. Because calling "eval" on an expression would evaluate the expression in the underlying STk. This is undesirable for many reasons, for one, the expression might contain primitives that exist only in our Interpreter. 11. We would add: ((remove-exp? exp) (remove-variable! (cadr exp))) into mc-eval conditional checks. (define (lambda-exp? exp) (eq? (car exp) 'remove!)) (define (remove-variable! var) (define (scan vars vals) (cond ((null? (cdr vars)) #f) ((eq? var (cadr vars)) (set-cdr! vars (cddr vars)) (set-cdr! vals (cddr vals)) #t) (else (scan (cdr vars) (cdr vals)))) (let ((scan-result (scan (car the-global) (cdr the-global)))) (if scan-result 'okay (begin (cond ((eq? (caar the-global) var) (set-car! the-global (cdar the-global)) (set-cdr! the-global (cddr the-global)) 'okay) (else (error "Unbound Variable"))))))) Here, remove-variable! is tricky because we need to look ahead at the cadr of our list. We also need to be careful that if the variable we are looking for is the first element of the variable-list, then we must modify the-global environment to skip that first element.