6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 5.3.20 Cdr'ing and Cons'ing Examples Well copying is boring, but here is how we can use this idea (if (n(copy 1st) Suppose we want to glue two lists together into one long list, as shown in the example 1st))) Let's just use the same strategy, implemented in a handy 12)(1⊥nt34) procedure called append. For the base case, notice that if we Strategy:copy" list onto front of lst2. do not have anything in the first list, we just want the second (define (append list list2) list. Otherwise, we use the same idea as before. We adjoin the 1⊥8t1) Dage first element of the first list onto whatever we get by appendin ad。⊥n(E⊥rst1⊥st1 recursion 1容t1 the rest of the first list onto the second list Using the same 18t2)))》) closure properties, we see that this will create a list, and adj 60015cP ill then put the first element on the front of this new list Notice how we are using the recursive properties of lists to build this procedure, and in particular notice how the recursive structure of the procedure nicely mimics the recursive structure of the data object Slide 5.3.21 Common Pattern #3: Transforming a List So now we can put these ideas to work in handling more (define group (list p1 p2- p9 complex structures. Let's group together a set of points using a list. Then we can easily write a procedure to stretch the entire (if (null? p) group, by building on the wonderfully recursive nature of the list. Here it (stretch江trm) Note how we subdivide the problem of stretching a group into to a list of points e operation of stretching a point(using the procedure appropriate for points), and then adding that to the result we would get by stretching the rest of the group. Because of the recursive nature of a list we know that the rest of a list is a list so we can use induction to conclude that stretch-group applied to Le the smaller collection will return a new group, and thus adjoining the new element to the front of this will clearly give us back a group Common Pattern #3: Transforming a List Slide 5.3.22 (define add-x (lambda (gP) And if we want to find the midpoint (or centroid) of the group we can put together the pieces we built earlier, as shown here (. (point-x (rirst (p)) (rest gp))))) Add-x and add-y have a structure very similar to our earlier (define add-y (lambda (gp) if (null? gp) examples: they simply cdr down the list, gathering up ( (point-y (rirst p)) information as they go in a set of deferred additions. Each of these will get the sum of the x and y values of all the points in a (define centroid (lambda let ((r-sum (add- gp)) group. To find the midpoint we need to get the average x and y (y-suim (add-y gp)) aow-nany (length gp)) alue, so we need to know how many elements are in the group (make-point ( x-sum how-nary) ( y-sun howman))))) which we get using length. We can combine this information to 6001 scP create a new point at the middle of the group Note the new form let. You can find the details in the textbook but it suffices to think of this as an expression in which each of the names in the first set of expressions(X-sum, y-sum and how-many are bound to the values of the expressions following those names. Then within the confines of the let expression, those names are simply local names for those values, and are substituted for just as we would in the standard substitution model6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 5.3.20 Well copying is boring, but here is how we can use this idea. Suppose we want to glue two lists together into one long list, as shown in the example. Let's just use the same strategy, implemented in a handy procedure called append. For the base case, notice that if we do not have anything in the first list, we just want the second list. Otherwise, we use the same idea as before. We adjoin the first element of the first list onto whatever we get by appending the rest of the first list onto the second list. Using the same closure properties, we see that this will create a list, and adjoin will then put the first element on the front of this new list. Notice how we are using the recursive properties of lists to build this procedure, and in particular notice how the recursive structure of the procedure nicely mimics the recursive structure of the data object. Slide 5.3.21 So now we can put these ideas to work in handling more complex structures. Let’s group together a set of points using a list. Then we can easily write a procedure to stretch the entire group, by building on the wonderfully recursive nature of the list. Here it is. Note how we subdivide the problem of stretching a group into the operation of stretching a point (using the procedure appropriate for points), and then adding that to the result we would get by stretching the rest of the group. Because of the recursive nature of a list, we know that the rest of a list is a list, so we can use induction to conclude that stretch-group applied to the smaller collection will return a new group, and thus adjoining the new element to the front of this will clearly give us back a group. Slide 5.3.22 And if we want to find the midpoint (or centroid) of the group, we can put together the pieces we built earlier, as shown here. Add-x and add-y have a structure very similar to our earlier examples: they simply cdr down the list, gathering up information as they go in a set of deferred additions. Each of these will get the sum of the x and y values of all the points in a group. To find the midpoint we need to get the average x and y value, so we need to know how many elements are in the group, which we get using length. We can combine this information to create a new point at the middle of the group. Note the new form let. You can find the details in the textbook, but it suffices to think of this as an expression in which each of the names in the first set of expressions (x-sum, y-sum and how-many) are bound to the values of the expressions following those names. Then within the confines of the let expression, those names are simply local names for those values, and are substituted for just as we would in the standard substitution model