6.001 recitation 3/21/07set-car! and set-cdr!ring problemsmore set-car!, set-cdr! problemsDr. Kimberle Koile2compound data mutationconstructor:(cons x y) creates a new pairselectors:(car p)returns car part of pair(cdr p) returns cdr part of pairmutators:(set-car! p new-x)changes car pointer in pair(set-cdr! p new-y) changes cdr pointer in pair; Pair,anytype -> undef -- side-effect only!How can we tell if two things are equivalent?-- What do you mean by "equivalent"?1. The same object: test with eq?(eq? a b) ==> #t2. Objects that "look" the same: test with equal?(equal? (list 1 2) (list 1 2)) ==> #t(eq? (list 1 2) (list 1 2)) ==> #f1212sharing, equivalence, and identity(define a (list 1 2))(define b a)a ==> (1 2)b ==> (1 2)12ba(set-car! a 10)Compare with:(define a (list 1 2))(define b (list 1 2))12a12b(set-car! a 10)example 1: pair/list mutationexample 2: pair/list mutation(define x (list 'a 'b))abxX21How is x mutated to achieve the result at right?And this one?abxX1For the given expressions:(a) Draw the box and pointer diagram corresponding to the list or pair structure(b) Write what Scheme prints out after evaluating the last expression in the sequence1. (define x (cons 7 (list 8 9)))(set-car! (cdr x) 10)a. box and pointer diagram for x b. printed result for xset-car! and set-cdr! problemsFor the given expressions:(a) Draw the box and pointer diagram corresponding to the list or pair structure(b) Write what Scheme prints out after evaluating the last expression in the sequence2. (define y ’(7))(define z (let ((x (list ’a ’(b c) (car y))))(set-car! y (cdr x))(set-cdr! x (car (cdr x)))x))za. box and pointer diagram for x, y and z b. printed result for zset-car! and set-cdr! problemsFor the box & pointer diagram:(a) Write what Scheme prints out for the structure (if it can)(b) Write a Scheme expression that makes the structure (if an error, describe it)(c) Draw the structure that results from the mutation, and its printed representation.3. a. x =>b. Scheme expression: c. mutation: (set-car! (cdr (second x)) 4)x =>more set-car! and set-cdr! problemsRings are circular structures similar to lists. If we define a ring r: (define r (make-ring ‘(1 2 3 4)))the following are true: (nth 0 r) => 1 (nth 1 r) => 2 … (nth 4 r) => 1In order to make a ring, we need a procedure last-pair which returns the last pair in its argument:(last-pair (list 1 2 3 4))=> (4)1. Write last-pair.(define (last-pair x)ring problems2. Write make-ring!, which takes a list and makes a ring out of it..(define (make-ring! x))ring problems3. Write the procedure rotate-left, which takes a ring and returns a ring that has been rotated one to the left.(define r1 (rotate-left r))(nth 0 r1) => 2(define (rotate-left ring))ring problems4. What happens if you evaluate (length r) on the above ring? Write the procedure ring-length, which returns the length of the original list used in constructing the ring. (Hint: Write a helper procedure.)(define (ring-length ring)) ring problems5. Rotating a ring to the right is harder than rotating to the left. (Why?) Write the procedure rotate-right. (Hint: You might want to use the procedure repeated, which takes a procedure, a number n, and an argument to the procedure, and repeatedly calls the op on the argument n times.)(define (rotate-right ring))ring problemsFor the box & pointer diagram:(a) Write what Scheme prints out for the structure (if it can)(b) Write a Scheme expression that makes the structure(if an error, describe it)(c) Draw the structure that results from the mutation, and its printed representation.1. a. x =>b. Scheme expression: c. mutation: (set-cdr! (car x) '(8))x =>more set-car! and set-cdr! problemsFor the box & pointer diagram:(a) Write what Scheme prints out for the structure (if it can)(b) Write a Scheme expression that makes the structure (if an error, describe it)(c) Draw the structure that results from the mutation, and its printed representation.2. a. x =>b. Scheme expression: c. mutation: (set-cdr! (cddr x) (caaar x))x =>more set-car! and set-cdr! problemsFor the box & pointer diagram:(a) Write what Scheme prints out for the structure (if it can)(b) Write a Scheme expression that makes the structure (if an error, describe it)(c) Draw the structure that results from the mutation, and its printed representation.3. a. x =>b. Scheme expression: c. mutation: (set-car! (caar x) 3)x =>more set-car! and set-cdr! problemsFor the box & pointer diagram:(a) Write what Scheme prints out for the structure (if it can)(b) Write a Scheme expression that makes the structure (if an error, describe it)(c) Draw the structure that results from the mutation, and its printed representation.4. a. x =>b. Scheme expression: c. mutation: (set-cdr! (first x) (second x))x =>more set-car! and set-cdr! problemsFor the box & pointer diagram:(a) Write what Scheme prints out for the structure (if it can)(b) Write a Scheme expression that makes the structure (if an error, describe it)(c) Draw the structure that results from the mutation, and its printed representation.5. a. x =>b. Scheme expression: c. mutation: (set-car! (cdr x) ’())(set-cdr! (car x) ’())x =>more set-car! and set-cdr!
View Full Document
Unlocking...