--- Copyright 1994 Paul R. Wilson You may use these notes freely for noncommercial purposes, as long as this notice is preserved in all copies. --- EXERCISES IN SCHEME PROGRAMMING, PART 1 Some introductory programming exercises. The solutions at the end include IMPORTANT notes that should be considered part of the basic course notes. Even if you already know Lisp, these exercises will be useful in teaching you to use recursion where in old-style Lisps you'd probably use explicit iteration constructs. In old-style Lisp programming, you generally think iteratively for linear lists, and recursively for more general data structures. In Scheme, you can use recursion for both, since recursion is strictly more powerful than iteration. --- In the following, you should only need to use basic special forms such as DEFINE, IF, COND, QUOTE, BEGIN, LET and SET!. You can use local DEFINEs to define private procedures. (A local definition defines a local variable, and in the case of a procedure definition, it's a local variable whose value is a procedure.) --- You can use the obvious built-in Scheme procedures like EQ?, >, <, =, ,+, -, CONS, CAR, and CDR. You WON'T need (and shouldn't use) LETREC, LET*, or built-in iteration constructs like named LET, FOR, and DO. Do not use QUASIQUOTE (backquote) or its friends UNQUOTE and UNQUOTE-SPLICING. You shouldn't use fancier list-manipulation procedures like APPEND and LIST, or fancy quoting features like QUASIQUOTE (backquote). You won't need (and shouldn't use) APPLY, MAP, or FOR-EACH, either. --- When you put type checks in your code, you can call a procedure ERROR that takes any number of arguments, displays them, and stops execution. Unfortunately, there isn't a built-in ERROR function for signaling errors in Scheme. If you're using a Scheme without an error procedure, you can define your own as something like: (define (error . args) (display "ERROR:") (map (lambda (arg) (write arg) (display " ")) args) (car 1)) ; do something illegal to force a break. This defines a procedure that takes any number of arguments, which will be passed to the function as a list that's the binding of the variable args. It then does something (taking the CAR of something that's not a pair) that's an error in any implementation, to make sure that execution stops and an error of some kind is signaled. Of course, when the implementation detects this error, it will signal that you've taken the CDR of a non-pair; this is distracting because the error message you really care about is the one that's printed just before we force that error. --- 1. Write a procedure to get the third element from a list. You can use CAR and CDR, but not the built-in CADR, CDDR, etc. Example usage: Scheme> (one "two" 3 four "five" 6) 3 Note: the names here are a historical artifact of Scheme's Lisp heritage. CAR should probably be called FIRST, and CDR should be called REST; then we'd call CADR SECOND and CADDR THIRD. 2. Write a procedure CDDDR that takes a list, and hands back the list that starts with the fourth element of the original list, i.e., for a list of items 1 through n, you should return a pointer into that list that gives items 3 through n. Example usage: Scheme> (cddr '(1 two "three" 4 five "six")) (4 five "six") 3. Write a procedure CADADADR that takes a list of lists of lists as its argument, and returns the second element of the second element of the second element. Example usage: Scheme> (cadadadr '(((one two three) (four five six)) ((seven eight nine) (ten eleven twelve)) ((thirteen fourteen) (fifteen sixteen))) ELEVEN 4. Write a procedure LIST-NTH that finds element n of a list. Your solution should be recursive, using a tail call to ensure that it executes in constant space. If handed something that is not a list, or a list that's too short, it should give an informative error message. It should also give an informative error if given an unreasonable index value n. Example usage: Scheme> (NTH '(one "two" 3 "four" five 6) 4) "four" 5. Write a procedure LIST-COPY which makes a SHALLOW copy of a list, i.e., another list whose elements are the same objects as the elements of the original list. (A shallow copy just copies the list itself, and the rest of the data structure is shared via the pointers from the new pairs' CAR fields.) You'll need to copy the original list by making new pairs. Your solution should be recursive in a straightforward way, copying one cons cell and then call itself to copy the rest of the list. Example usage: Scheme> (LIST-COPY '(am is (are was were) (be being been))) (am is (are was were) (being been)) 6. Write a procedure APPEND that appends two lists to create a list with the elements of the first list followed by the elements of the second list. This should be a NONDESTRUCTIVE function (i.e., it should not modify the lists given it as arguments), but it should result in SHARED STRUCTURE, i.e., the part of the result list that is the same as the second argument list should actually BE the second argument list. You'll have to construct new cons cells corresponding to the first list, but the second list can just be shared. Do not use Scheme's built-in APPEND procedure. Your solution should be simple and recursive in the obvious way, copying one cons cell per call until the first list is copied. 7. Write a procedure LISTS-DEEP-COPY which makes a copy of a list, including copying any sublists of that list, and sublists of those, and so on. That is, the resulting data structure should be all new, as far down as necessary to reach something that's not a pair, such as a symbol, number or vector. (We could also make a DEEP-COPY that would copy vectors and other structures, but don't do that for this problem.) Example usage: Scheme> (LISTS-DEEP-COPY '(am is (are was were) (be being been))) (am is (are was were) (being been)) Notice that the textual representation of the result that you get back from the read-eval-print loop LOOKS just like the result of calling LIST-COPY. That's because the textual representation generated by the r.e.p. loop doesn't show the identity of an object---you can't tell if two objects with the same printed representation are the exact same object, except for certain kinds of objects (like symbols and booleans) which are guaranteed to be kept unique by the reader. 8. Write LIST-SUM, a procedure that sums a list of numbers. It should be recursive in the obvious way. You can assume that if it's not a proper list, you can ignore any non-pair tail of the list. 9. Write LIST-COPY again, but this time write it tail-recursively, so that it executes in constant space (except, of course, for the new copy of the list, which takes order n space). You can use set! or set-car! or set-cdr!, but only one of them and only in one place in your code. You can assume that the list is null-terminated, or that it's okay to share the improper tail of the list with the original. 10. Write APPEND again, but this time write it tail-recursively, so that it executes in constant space (except, of course, for the new copy of the first list). 11. Write LIST-SUM again, only this time write it tail-recursively so that it executes in constant space. Do NOT use any destructive operations (e.g., set! or set-cdr!). HINTS: It may be useful to use an auxiliary procedure that does most of the work and takes a second argument. Remember that unlike a copy, a sum takes fixed space. (We'll assume that we won't overflow an integer.) 12. Write a simple version of MAP, which takes as arguments a list of values and a one-argument procedure to apply to those values. It should return a new list whose elements are the values obtained by applying the argument procedure to the corresponding elements of the original list. Example usage: Scheme> (map symbol->string '(foo bar baz)) ("foo" "bar" "baz") 13. Write a procedure FOR-EACH, which is like MAP except that it does not create a list of the mapped values. It should have the special property that it applies the functions to the elements of the original list in the order that they appear in the list, and it should return the value of the LAST application, rather than a list of all of the values. Scheme> (map symbol->string '(foo bar baz)) "baz" This is not really the most interesting example---usually, when you use FOR-EACH, you're doing it for side effects. In this case, the function being applied has no side effects. 14. Write a procedure MAP!, which is like MAP (above), except that it modifies the original list, replacing each item with the value computed by applying the argument function to it. It should return the original list after transforming it. --------------------------------------------------------------------- SOLUTIONS Here are some solutions to the above problems. Your solutions may not look like this, but if they're significantly longer or harder to understand, you should think about why. Usually, a complicated solution indicates that you're not really using the language the way it was designed to be used. 1. (define (caddr lis) (car (cdr (cdr lis)))) Note that this solution relies on the fact that car and cdr check their arguments---if you hand THIRD something that's not a list of at least 3 items, CAR or CDR will detect that it's not being given a PAIR as an argument, and will signal an error. There are several reasonable names for this function, depending on your goals. We could have called it "third", or we might have called it "list-third" to make it clear that it operates on lists. We called it CADDR, which is the standard name of this function---there is a special naming convention for functions that destructure lists, based on the nesting of calls to CAR and CDR. This one is called cADDr because it takes the cAr of the cDr of the cDr. 2. (define (cdddr lis) (cdr (cdr (cdr lis)))) We call this function cdddr because it is an application of car (extracting a list item) to the result of nesting three applications of cdr to move down the list 3 times. You should recognize a sequence of d's in the name of a list-destructuring function as meaning that we're moving down the list, skipping a pair each time. We often call this "CDR'ing down a list". Remember, when you cdr down a list, what you end up with is a tail of the list, i.e., the "rest" of the list starting at that point, NOT the item at that position in the list. 3. (define (cadadadr lis) (car (cdr (car (cdr (car (cdr lis))))))) or, since I didn't tell you not to use CADR, it's probably better to use that: (define (cadadadr lis) (cadr (cadr (cadr lis)))) i.e., take the second element of the second element of the second element of some nested lists. You should get used to CADR being the function that takes the second element of a list, and the fact that an occurrence of "ad" in in the name of a list-destructuring function means you're taking the second element of a list. If we really want our error messages to be informative, we could insert our own checks to make sure that the list is properly structured, and display a message that says the error happened in CADADADR. If we leave that out because we're lazy or more interested in speed, then handing the wrong kind of list to CADADADR will cause a run-time error in CAR or CDR (or CADR). Of course, if the naming of list-destructuring procedures in Scheme weren't based on historical stuff, this should be called something like list-extract-2-2-2 4. (define (list-ref lis n) (if (and (pair? lis) (integer? n)) ; check arg types (cond ((> n 1) (list-ref (cdr lis) ; tail call to cdr down list (- n 1))) ((= n 1) (car lis)) (#t (error "bad index arg to list-ref" lis n))) (error "bad arg type in list-ref" lis n))) This is a clean solution, and a good one, but it's not the most efficient. At each recursive call, we check to see whether the index is an integer. Presumably, we only need to do this at the first iteration---if the index is an integer at first, then whenever we subtract 1 from it, we'll get another integer. As we'll explain in the solutions to later problems, we can factor repeated work out by defining a pair of procedures, one of which does the initial checking, and the other of which does the main work. Whether it's worth it to go to the trouble depends on how often this function will be called, and whether its speed matters that much to you. 5. (define (list-copy lis) (if (pair? lis) (cons (car lis) ; create copy of first pair, (list-copy (cdr lis))) ; computing cdr recursively lis)) This is a recursive copier that just conses a copy of the first list element onto a copy of the rest of the list. The recursion terminates when we hit the end of the list, and return that, so that it will serve as the end of the new list as well. Note that here I've chosen to copy a list up to the first non-pair. If it's a proper list, the end of the list will be the empty list object, '(). Copying the empty list is just returning the empty list object. If given an improper list, this function will hand back a copy whose non-list tail is SHARED with the original. This may or may not be what you want---it's just how I've chosen to do it. You might want to make it explicitly illegal to hand list-copy anything but a proper list, and in that case the code above should be modified to check that a non-pair lis is an empty list: (define (list-copy lis) (cond ((pair? lis) (cons (car lis) (list-copy (cdr lis)))) ((null? lis) lis) (#t (error "improper list in list-copy" lis) #f))) 6. (define (append l1 l2) (cond ((null? l1) l2) ((pair? l1) (cons (car l1) (append (cdr l1) l2))) (#t (error "non-list arg to append" l1 l2)))) Be careful to follow the logic here. This is a lot like the list-copy function, in that we're copying the first list argument. The difference is that when we reach the end of the list, we don't want to create a pair with the same car and cdr value---we want to create one with the same car value, but a cdr value that points to the second list. Notice that if we assume that the first list is null-terminated (which is probably what we want in an APPEND function) our recursion bottoms out when we hit the empty list. 7. (define (lists-deep-copy lis) (if (pair? lis) (cons (lists-deep-copy (car lis)) (lists-deep-copy (cdr lis))) lis)) Pretty obvious, huh? If it's a pair, copy it, and use recursion to copy the car and cdr if necessary. Stop the recursion when you hit a non-pair, and just use that value. 8. (define (list-sum lis) (if (pair? lis) (+ (car lis) (list-sum (cdr lis))) 0)) Notice that since we take the car of a list and then call list-sum recursively to compute the sum of the rest of the list BEFORE adding them together, we end up summing the list back-to-front. Notice also that this is NOT tail-recursive. Each call holds onto a list element while the recursion over the rest of the list goes on. 9. This one's a little bit tricky to do cleanly. The problem is that since we want this to execute in constant space (ignoring the list we're constructing), we can't hold onto any values through lots of recursion. So what we do is construct a cons cell at each recursion, BEFORE the rest of the list is built. Each time, we patch up the previous list element to point at the new one. The easy way to do this is with two procedures. The one that does most of the work goes recursively through the list, and takes an extra argument, which is the pair constructed at the previous recursive step, so that it can destructively append the new pair to the end of the new list. (define (list-copy-aux! lis prev-new-pair) (cond ((pair? lis) (let ((new-pair (cons (car lis) '()))) (set-cdr! prev-pair new-pair) (list-copy-aux! (cdr lis) prev-new-pair))) ((null? lis) '()) (#t (error "improper list in list-copy-aux!")))) Given the above helper procedure, we can write list-copy that calls it. It creates a dummy pair to act as the "previous pair" at the first call to list-copy-aux! (The first call to list-copy-aux! will leave the first new pair in the cdr of that pair, so list-copy just extracts that and returns it.) (define (list-copy lis) (let ((dummy-pair (cons 'dummy '()))) (list-copy-aux! lis dummy-pair) (cdr dummy-pair))) The above solution is a little bit tacky, in that list-copy-aux! is only useful to list-copy; it should probably be a local function inside list-copy, thus: (define (list-copy lis) ;; helper that recursively constructs new list by ;; destructively appending a new cons cell to the ;; previous one at each step (define (list-copy-aux! lis prev-new-pair) (cond ((pair? lis) (let ((new-pair (cons (car lis) '()))) (set-cdr! prev-new-pair new-pair) (list-copy-aux! (cdr lis) new-pair))) ((null? lis) '()) (#t (error "improper list in list-copy" lis)))) (let ((dummy-pair (cons 'dummy '()))) ;; dummy prev pair for (list-copy-aux! lis dummy-pair) ;; 1st call to helper (cdr dummy-pair))) By the way, to my eye this is still a clumsy solution. If you have a cleaner one, let me know. By the way, you should become comfortable with using local procedures. They help you organize your code, and they often help a good compiler perform better optimizations. The compiler usually can see that there are no redefinitions of the local procedure, and can compile it in special ways. (For example, it may actually generate the machine code for the helper procedure inline, rather than actually looking up a variable value and calling that at run time; it may also recognize that tail-recursive local procedures are just being used as loops and compile them with simple jumps rather than runtime procedure calls.) 10. Use your imagination for this one. 11. First we can define an auxiliary procedure that adds one list element and then tail-calls to compute the sum of the rest. This is tricky because we can't just compute the sum of the rest of the list and then add this element to it---doing the addition after the recursion would mean keep our procedure from being tail recursive. Instead, we compute the sum of the elements we've seen so far, and hand that value as an argument to the tail call. That way, we compute the sum front-to-back: (define (list-sum-aux lis sum-so-far) (cond ((null? lis) sum-so-far) ((pair? lis) (list-sum-aux (cdr lis) (+ (car lis) sum-so-far))) (#t (error "improper list in list-sum" lis)))) To start this off, we define our LIST-SUM as (define (list-sum lis) (list-sum-aux lis 0)) As before, we should probably make the auxiliary procedure a local procedure, thus: (define (list-sum lis) (define (list-sum-aux lis sum-so-far) (cond ((null? lis) sum-so-far) ((pair? lis) (list-sum-aux (cdr lis) (+ (car lis) sum-so-far))) (#t (error "improper list arg to LIST-SUM" lis)))) (list-sum-aux lis 0)) An important fact about this example is that programmers in conventional languages would almost invariably solve it using a loop and side-effects, but it has a reasonable solution using recursion as well---passing an argument is as good a way of communicating information to a recursive call as assigning to a variable. In a lot of ways, it's BETTER; it makes it clear where the information is going, and that it has no other effects. (This turns out to be important in rigorously proving what procedures do, when you want to make absolutely sure they're correct.) You should try to become adept at this kind of recursive thinking. In Scheme, it's generally considered bad style to use side effects too much. Notice that in our earlier examples, we used some side effects, but produced functions---procedures that didn't side effect their arguments. It's not uncommon to use side-effects in Scheme programs, but you try to keep the effects as local as possible so that they're easy to reason about. Once you're sure that APPEND is right, for example, you can assume that it doesn't have any side effects from the point of view of procedures that call it. When you're programming, you should usually code your procedures as simply as possible if you don't think they're going to be used a lot. This requires judgement and taste. If you're writing a function like APPEND or LIST-COPY or LIST-SUM that you're only going to use in a few places in your own code---and not in ways that affect overall performance much---then you should probably code them in the most straightforward way. For example, you might write something like LIST-SUM that'll only be used on short lists, and not very often. Hacks using side-effects (or tricks with auxiliary procedures and extra arguments) are important for performance-critical code, or for code that will be used by lots of other code and therefore may end up being performance-critical. But when you're really trying to get code to work, simpler is usually better. If you find out that some function is too slow or uses to much space, then you can rewrite it to be more efficient. Of course, part of the art of programming is to spend the most time writing (and debugging) the most useful code. It may be worthwhile to spend time optimizing a very general function, so that you can afford to use it in lots of places. For example, APPEND and MAP are so useful that they're part of the Scheme language standard, and most implementors of Scheme take the trouble to supply you with more efficient implementations than you'd get if you casually hacked them out yourself. Most serious Scheme programmers build their own libraries of handy functions so that they can use them in a bunch of programs, or share them with other people. One of the nice things about Scheme is that it's easy to write higher-order procedures (e.g. MAP) 12. (define (map fn lis) (cond ((null? lis) '()) ((pair? lis) (cons (fn (car lis)) (map fn (cdr lis)))) (#t (error "improper list arg to MAP" fn lis)))) This is just another simple recursive procedure. The key difference is that now we're using the first-class procedure fn to compute each element of the list. At each call, we extract the CAR of the next pair in the original list, and apply the argument function to it. We cons that onto the result of MAPping the function over the rest of the list. (If you're used to Common Lisp or other old-style Lisps, notice how easy it is to apply the function we're given---since we're handed a pointer to the function as the value of the argument binding of fn, we can just call it by that name. It's just like any other variable binding whose value happens to be a procedure; we just use its name in the first position of a combination to call it. This is why it's nice to have a single namespace for all variables. In Common Lisp, we'd have to use special syntax to call a procedure that's stored in a normal data (non-procedure) variable binding.) 13. (define (for-each fn lis) (if (pair? lis) (cond ((pair? (cdr lis)) (fn (car lis)) ; do next app. and (for-each fn (cdr lis))) ; tail-call ((null? (cdr lis)) ; last in proper list? (fn (car lis))) ; return last appl. value (#t (error "improper list in FOR-EACH" fn lis))) (error "non-list arg to FOR-EACH" fn lis))) This is not the most efficient way of doing it. Notice that after the first call, we don't really need to check if the list argument is a pair---that will have been checked by the previous call, when it was checking the CDR value of the previous pair. We can get rid of this inefficiency by having an outer function that calls an inner, recursive function, whose lis argument must be a pair: (define (for-each fn lis) ;; local procedure does main recursive work ;; assumes lis is a pair. (define (for-each-aux lis) (cond ((pair? (cdr lis)) (fn (car lis)) (for-each-aux (cdr lis))) ((null? (cdr lis)) ; last in proper list? (fn (car lis))) ; return last appl value (#t (error "improper list in for-each" fn lis)))) (if (pair? lis) (for-each-aux lis) (error "non-list arg to FOR-EACH" fn lis))) Notice that here we didn't bother to pass the argument fn to each recursive call to the helper procedure. Since the helper procedure is defined inside the FOR-EACH procedure, the argument variable fn is in scope, and can just be used like any other local variable. We couldn't have done this if we had defined FOR-EACH-AUX as another top-level procedure. 14. We can define an auxiliary procedure MAP-AUX! that will do most of the work, and wrap it in an outer procedure that will hold onto (and return) the head of the list. (define (map! fn lis) ;; this helper procedure will use tail recursion to iterate ;; through the list, clobbering each value with the result ;; of applying the function to that value (define (map-aux! lis) (cond ((null? lis) '()) ((pair? lis) (set-car! lis (fn (car lis))) (map-aux! (cdr lis))) (#t (error "improper list in MAP!" fn lis)))) (map-aux! lis) ; do the main work, for side effects lis) ; return the original list, now modified Notice that here again we didn't bother to pass the argument fn to each recursive call to the helper procedure, because the outer procedure's fn binding is in scope. We also use the value of the lis argument to the outer procedure---it's the pointer to the original list, which we return after clobbering its values.