Practice Questions #2 In the following problems, you are asked to define short procedures. All of your procedures should be true functions, without side effects. (That is, you won't need the special form set!, or the procedures set-car! or set-cdr!) This implies that you will not need to use begin, because begin is only necessary for writing sequences where the order of side-effects matters. Likewise, it also implies that you will never need more than one expression in the body of a procedure. Several of the problems require iterating through a list, but in all cases you should use recursion to perform this iteration. Some of your procedures will be very similar to procedures you've seen in the class notes, or on the board in class. Try to write these procedures without just copying the solutions you've seen before---you should understand *why* you're doing what you're doing. You should try out your answers in a real Scheme system. If you get stuck, then consult your notes, and make sure you understand whatever you didn't understand before. You'll have to solve similar problems in graded homework and tests, so the point here is to learn how to do things. For problems involving lists and recursion, it's a very good idea to work through some examples on paper, drawing box-and-arrow pictures of the lists and stepping through your procedure's operation. After you've written your answer and are satisfied with it---or if you get really stuck, even with the help of your notes---look at my answers and comments. Be sure to read the comments even if you get the answer right, and pay attention to indenting. There are important points about programming style in the comments. In quizzes and homework, you will be graded on indenting---not much, but a little, because indenting is important, and if I'm misled by your indenting, I may think your answer is incorrect anyway. General advice on programming: Write small procedures, usually no more than a dozen lines and often only one to five lines. If you're writing lots of big procedures, you're not breaking the problems down logically. When writing recursive procedures, think about the base cases and the recursive steps. For recursion over lists, the base case is usually when you hit a null pointer. For recursion over trees, the base cases are whatever kinds of things are at the leaves of the trees. Write the base cases first, and test them first. This will help avoid infinite recursion problems, and remind you to write the base cases. (If you don't write and test the base cases first, you're likely to mess them up or forget them entirely, and feel a little foolish when your procedure gets stuck in an infinite recursion.) When you run your program, test the low-level procedures first. This is really easy in Scheme, because you can do it interactively and type in data structures as literals, using quotation. Then try out the higher-level procedures that depend on the lower level procedures you've tested. --- 1. Define a procedure add5, which takes an argument n, which is expected to be a number, and returns a value that is 5 greater than n. Use the procedure + and no others. Use the normal procedure definition syntax. Example use: (add5 7) => 12 (remember, => means "evaluates to") Hint: This is just a trivial procedure definition to make sure you know the normal syntax of procedure definitions. 2. Rewrite the procedure definition in #1 using plain variable definition syntax and lambda. Hint: this is really, really easy if you understand that procedures are anonymous, lambda means "make procedure", and the "name" of a procedure is really just the name of a variabe whose value points to the procedure. 3. Define two procedures, first and rest, each of which takes an argument named lis, which is a list. first returns the first item in the list lis. rest returns a list of the rest of the items in lis, i.e, all but the first. Assume that the arguments passed to these procedures are non-empty lists. Example uses: (first '(foo bar baz)) => foo (rest '(foo bar baz)) => (bar baz) Hint: this is really, really, really easy. 4. Define a procedure last, which returns the last element of a proper, non-null list. Example uses: (last '(foo 22 bar 19 baz)) => baz (last '(1 2 3)) => 3 (last '(a)) => a (last '()) is an error Hint: this is a somewhat like length (in the Scheme notes), in that we need to recurse down a list to the end. It's different from length, though, and easier, because we don't need to sum the list on the way back up from the recursion---we just return whatever we find at the end of the list. 5. Define a procedure double-all, which takes one argument, lis, which is a list of numbers, and returns a list of numbers where each number is twice the number in the corresponding position in the original list. Example use: (double-all '(5 8 3)) => (10 16 6) Hint: this is a lot like list-copy in the Scheme notes, except that we don't use the car of the list as-is. 6. Define a procedure list-product, which gives the product of the numbers in a list of numbers. For a null list, return 1. For a list of one item, return that item. Example uses: (list-product '(1 2 3)) => 6 (list-product '(500 10 5 1)) => 25000 (list-product '(5 2)) => 10 (list-product '(2)) => 2 (list-product '()) => 1 Hint: this is a lot like list-sum in the Scheme notes, except that for a zero-element list, we return 1, the identity value for multiplication, rather than 0, the identity value for addition. 7. Define a procedure remove-first which takes two arguments, val and list, where val is any value and lis is a (proper) list, and returns a new list which has the same elements as the original list, except that the first occurrence of the value val in the original list is missing from the new list. Use eqv? to check whether an element of the original list is "the same as" val. If there's no occurrence of val in lis, remove-first should return a copy of the original list. Example uses: (remove-first 2 '(3 2 5 3 1 2)) => (3 5 3 1 2) (remove-first 'foo '(bar baz quux foo)) => (bar baz quux) (remove-first 'bar '()) => '() (remove-first 'baz '(foo bleen)) => (foo bleen) Hint: this is a lot like list-copy, in that we need to construct a modified copy of a list, but it's also like append, in that we can use the "rest" of the list as-is, once we've gotten to the point where the new list is different from the old one. 8. Define a procedure count-occurrences, which takes two arguments, val and lis, and searches the list lis for the value val, counting the number of times the value val occurs in the list lis. Use eqv? as the test for whether a list item is the same as the value we're counting occurrences of. Hint: this is a lot like length (in the Scheme notes), in that we recurse through a list to the end, and sum things on the way back up from the recursion. Example uses: (count-occurrences 'foo '(bar 1 foobaz 1 bar foo)) => 2 (count-occurrences '3 '(5 6 3 foo 2 1)) => 1 9. Define a procedure remove-all which takes arguments val and lis, where val is any value and lis is a (proper) list, and returns a new list which has the same elements as lis, except that all occurrences of the value val in the original list are missing from the new list. Use eqv? to test whether each value in the list is "the same" as the value we're removing. Hint: this is a lot like list-copy, except that we need to skip items that match (are eqv? to) the target value, val. Example uses: (remove-all 2 '(3 2 5 3 1 2)) => (3 5 3 1) (remove-all 'foo '(bar foo baz foo bar)) => (bar baz bar) (remove-all 6 '(6 6 6)) => () 10. Define a procedure list-tree-sum, which is like pair-tree-sum (from the Scheme notes), in that it sums all of the numbers in a tree. For a number (a leaf in the tree), list-tree-sum should return that number. For a list, it should return the list-tree-sum of all of the items in the list. Unlike pair-tree sum, your procedure list-tree-sum should ONLY work on proper lists (and plain numbers). i.e., if the cdr of a pair is not a pair or the empty list, an error should be signaled. Your procedure should also signal an error if any of the elements of a list (i.e., the car values of the pairs) is null. Examples: (list-tree-sum 2) => 2 (list-tree-sum '(1 3 2)) => 6 (list-tree-sum '((1 2) 3 (4 (5 (6))))) => 21 (list-tree-sum '(1 . 2)) is an error Hints: This is rather like the postfix-display problem from the first quiz, but with some differences. You do want to consider each list at a given level as though it were a single object, for purposes of the overall recursion. On the other hand, since each of the lists that acts as a tree node can be of any length, you *also* need to use recursion to iterate over each list. Your code should therefore use recursion in two different ways. That is, you mostly want to think of lists as though they were single objects, like records, in designing the overall recursion. So one of your uses of recursion should implement normal tree-traversal recursion. When you want to operate on all of the children of a list, then you need to rely on the fact that a list is really a sequence of pairs strung together by the cdrs, and do simple list-traversal recursion over that list. You can ensure that an error will be raised for an improper list if you always take the cdr of anything that's supposed to be a pair. You can check for null, and take the cdr of every non-null list, and cdr will signal an error if it's ever given a non-pair. Write one procedure, list-tree-sum, that traverses the tree of lists, using another procedure, node-sum, that iterates over the elements of a list at one level in the tree. Each of these procedures should only be a few lines long. If it's longer, you're probably doing something unnecessarily complicated and need to think about the structure of the problem again. Notice that the overall tree data structure is recursively defined. A tree may be either a plain number or a list of trees. The structure of our routine list-tree-sum should directly reflect this definition. Likewise, the structure of a tree node is recursively defined---it's a list, which is either null or a pair whose cdr is a list. The structure of your node-sum routine should directly reflect this, in much the same way that list-sum reflects the definition of a plain list of numbers. These procedures will be mutually recursive.