6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology valuabie role 6.001 Notes: Section 6.4 Slide 6.4.1 Common Pattern #1: Transforming a List Now, let's see how we can use"higher order procedures"on data structures. Remember our lists from before. We saw that d0in(gq高r( firSt1gt there were common patterns for lists, especially creating new lists out of old ones. In particular, we had the idea of generating a list, consing it up as we move down another list We can generalize that idea, so that instead of just making a copy of a list, I do something to each element of the list as I make the copy For example, each of these procedures takes a list as input and The first example squares each element of the input list, the y. generates a new list, transforming each element in a fixed wa 6001S second one doubles each element of the list Notice the form is very similar to our append example. We walk down the input list one element at a time however here we actually apply some procedure to the element before adjoining it to the output. Note how the procedures use the selectors and constructors of the data abstraction to extract elements and create elements, and how the recursive structure of the procedure reflects the recursive structure of the data abstraction Common Pattern #1: Transforming a List Slide 6.4.2 Clearly there is a pattern here: we take a list as input down it an element at a time. do something to each (aquare-liwt (rest lxt))))1 and construct a new list of the results because there is a common pattern, we can capture it as a procedural abstraction (ajo indomsie-1ist (resist) Map is that general pattern. It is a higher order procedure that eff ennui? is oe st) takes as input both a list and a procedure, and simply applies a41oin(pe。(tist the procedure to each element of the old list to create the Ist) corresponding element of the new list. As a consequence, we can easily capture the two examples as instances of map, and Landa (xK 6001 SICP map forms a very common interface for manipulating lists6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. valuable role. 6.001 Notes: Section 6.4 Slide 6.4.1 Now, let's see how we can use "higher order procedures" on data structures. Remember our lists from before. We saw that there were common patterns for using lists, especially creating new lists out of old ones. In particular, we had the idea of generating a list, consing it up as we move down another list. We can generalize that idea, so that instead of just making a copy of a list, I do something to each element of the list as I make the copy. For example, each of these procedures takes a list as input and generates a new list, transforming each element in a fixed way. The first example squares each element of the input list, the second one doubles each element of the list. Notice the form is very similar to our append example. We walk down the input list one element at a time, however here we actually apply some procedure to the element before adjoining it to the output. Note how the procedures use the selectors and constructors of the data abstraction to extract elements and create elements, and how the recursive structure of the procedure reflects the recursive structure of the data abstraction. Slide 6.4.2 Clearly there is a pattern here: we take a list as input, walk down it an element at a time, do something to each element, and construct a new list of the results. Because there is a common pattern, we can capture it as a procedural abstraction. Map is that general pattern. It is a higher order procedure that takes as input both a list and a procedure, and simply applies the procedure to each element of the old list to create the corresponding element of the new list. As a consequence, we can easily capture the two examples as instances of map, and map forms a very common interface for manipulating lists