6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 5.3.17 In addition to procedures that can"cons up"a list, we have Common Pattern #2: cdr'ing down a list procedures that can walk down a list, also known as"caring define (list-ref lst n down"a list (f(=n0) Here is a simple example, which finds the nth element of a list, (list-ref (rest lst n1)))) where by convention a list starts at 0. Notice how we use the recursive property of a list to do this. If our index is 0, then we 中中q(1sr31 want the first element Otherwise. we know that the nth element of a list will be the n-lst element of the rest of the list, by the closure property of lists. So we can recursively reduce this to a simpler version of the same problem For the example shown, we will first check to see if n=0. Since 4 6001 SCP it does not, we take the list pointed to by Joe, extract the rest decrement of n. This recursive call will now have n=0, so we return the first element of the new list, namely the of that list by literally taking the pointer out of the cdr part of the first box, and call list-ref on that structure, with element 3 Common Pattern #2: caring down a list Slide 5.3.18 (define (list-ref lst n) a related procedure is to count up the number of elements in a (first lst list, using the same sort of recursive reasoning. Length of a ist-ref (rest lst) -n1))) list is defined as l more than the length of the rest of a list, which by the closure property is also a list. The base case is the empty list, which has zero length 1 (length rest lst))) Slide 5.3.19 Caring and Cons'ing Examples Now we can put the two ideas together, caring down one list (define (copy lst) while consing up a new one as the return value. Here is an example, which creates a copy of a list SCILS⊥cn Notice the form. If we are given an empty list, we just return an empty list and are done. If not, then we use the recursive property of lists. We adjoin the first element of the input list onto whatever we get by copying the rest of the list. But by closure, the rest of the input list is a list, so copy is guaranteed y induction to give us back a list. And by what we just saw, we see that copy will create a copy of the list in exactly the same 6001联0 order6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 5.3.17 In addition to procedures that can "cons up" a list, we have procedures that can walk down a list, also known as "cdring down" a list. Here is a simple example, which finds the nth element of a list, where by convention a list starts at 0. Notice how we use the recursive property of a list to do this. If our index is 0, then we want the first element. Otherwise, we know that the nth element of a list will be the n-1st element of the rest of the list, by the closure property of lists. So we can recursively reduce this to a simpler version of the same problem. For the example shown, we will first check to see if n=0. Since it does not, we take the list pointed to by joe, extract the rest of that list by literally taking the pointer out of the cdr part of the first box, and call list-ref on that structure, with a decrement of n. This recursive call will now have n=0, so we return the first element of the new list, namely the element 3. Slide 5.3.18 A related procedure is to count up the number of elements in a list, using the same sort of recursive reasoning. Length of a list is defined as 1 more than the length of the rest of a list, which by the closure property is also a list. The base case is the empty list, which has zero length. Slide 5.3.19 Now we can put the two ideas together, cdring down one list while consing up a new one as the return value. Here is an example, which creates a copy of a list. Notice the form. If we are given an empty list, we just return an empty list and are done. If not, then we use the recursive property of lists. We adjoin the first element of the input list onto whatever we get by copying the rest of the list. But by closure, the rest of the input list is a list, so copy is guaranteed by induction to give us back a list. And by what we just saw, we see that copy will create a copy of the list in exactly the same order