6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 6.4.3 Note that in all the previous examples, and indeed for any Common Pattern #2: Filtering a List example using map, the length of the output list is the same as (define (filter pred ist the length of the input list. For each element of the input list, I (cond ((null? lst) nil) ((pred (first lst)) do some process and create a corresponding element of the output list. But what if I want a list as output that is different in (filter pred (rest lst)))) ( else (filter pred (rest 1st))))) length, in particular, a list that has corresponding elements for only some of the elements of the input list? (filter even? (list 1 2 4 5 6) Va1ue:(246 For that we have another conventional interface called a filter Much like a coffee filter, a filter will only let some elements of the input list through. As before, we recursively walk along the list. If the list is empty, we just return an empty list, to guarantee that the result is a list. Otherwise, we apply a predicate to the first element of the list. Note that pred must be a procedure that returns a boolean as output, and hence filter must be a higher order procedure. If the result of applying the predicate to the element is true, we adjoin a copy of the element onto the output list, otherwise we move on to the next element Common Pattern #3: Accumulating Results Slide 6.4. 4 det ine (add-up lst) Finally, suppose we want to gather the elements of the list together into a new value, rather than creating a list as output ad-up (rest lst))))) For example, we might want to add up all the elements of a list or multiply them together. Here, we could just recursively walk down the list, adding the first element of the list to whatever we get by recursively doing the same thing to the rest of the list ( there is that nice recursion property again !) Of course, we have to be careful about what we return when we reach the empty list For addition, we add in a 0, for multiplication we turn a 1 Here are two common patterns for converting lists to number and as before we should be able to capture this common pattern Slide 6.4.5 Common Pattern #3: Accumulating Results and here is the generalization, a third standard operation on lists called fold-right Notice its form: it has three arguments, a procedure op, an (add-up (rest Ist))))) initial value init and a list lst. It's structure is to return the initial (daf in dmz au is value, if the list is empty, otherwise it returns the value of ( (first lst) applying the operator procedure to the first element of the list, (mult-all (rest 1st)))) and whatever we get by reducing the remainder of the list lists and procedure to unwrap this procedure into a simpler e Notice the nice use of closure and the recursive structure of Kop (first lst) (told -right op init (rest lst))))) version of the same problem These common interfaces, by the way, are very powerful ways of deal ing with sequences of data. They can be applied not only to sequences of numbers, but to sequences of other structures, and we will see that many operations of such structures reduce to combinations of map, filter and fold-right6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 6.4.3 Note that in all the previous examples, and indeed for any example using map, the length of the output list is the same as the length of the input list. For each element of the input list, I do some process and create a corresponding element of the output list. But what if I want a list as output that is different in length, in particular, a list that has corresponding elements for only some of the elements of the input list? For that, we have another conventional interface, called a filter. Much like a coffee filter, a filter will only let some elements of the input list through. As before, we recursively walk along the list. If the list is empty, we just return an empty list, to guarantee that the result is a list. Otherwise, we apply a predicate to the first element of the list. Note that pred must be a procedure that returns a boolean as output, and hence filter must be a higher order procedure. If the result of applying the predicate to the element is true, we adjoin a copy of the element onto the output list, otherwise we move on to the next element. Slide 6.4.4 Finally, suppose we want to gather the elements of the list together into a new value, rather than creating a list as output. For example, we might want to add up all the elements of a list, or multiply them together. Here, we could just recursively walk down the list, adding the first element of the list to whatever we get by recursively doing the same thing to the rest of the list (there is that nice recursion property again!). Of course, we have to be careful about what we return when we reach the empty list. For addition, we add in a 0, for multiplication we return a 1. Here are two common patterns for converting lists to numbers, and as before we should be able to capture this common pattern. Slide 6.4.5 ... and here is the generalization, a third standard operation on lists called fold-right. Notice its form: it has three arguments, a procedure op, an initial value init and a list lst. It's structure is to return the initial value, if the list is empty, otherwise it returns the value of applying the operator procedure to the first element of the list, and whatever we get by reducing the remainder of the list. Notice the nice use of closure and the recursive structure of the lists and procedure to unwrap this procedure into a simpler version of the same problem. These common interfaces, by the way, are very powerful ways of dealing with sequences of data. They can be applied not only to sequences of numbers, but to sequences of other structures, and we will see that many operations of such structures reduce to combinations of map, filter and fold-right