Practice Questions #3 This homework will give you practice writing recursive routines. Some of the problems are similar to problems you've seen before, with minor twists. I suggest trying to solve them yourself without looking back at the code you've seen, to make sure you can do this without just copying solution strategies you've seen before. If you get stuck, then look at your notes and try to learn from your being stuck. Try your solutions out in a running Scheme system to make sure they're right. This is always a good idea. For anything more than a couple of lines long, you should write little pieces of code and test those pieces on easy cases, then flesh out the code and test it on harder cases. 1. Define a procedure do-it-to-it which takes two arguments, proc and thing. do-it-to-it should expect proc to be some kind of procedure, and thing to be some kind of thing that proc can operate on. do-it-to-it should just apply the procedure proc to the argument thing, and return the result. The body of this procedure should be one very simple line. Example uses: (do-it-to-it car '(one two three four)) => one (do-it-to-it cadr '(f g h)) => g (do-it-to-it null? "foo") => #f (do-it-to-it not '()) => #f Hint: this is very easy if you know how procedure calling works, what a procedure name really is, and what a higher-order function is. 2. Define a procedure subst which takes three arguments, oldval, newval, and lis, and returns a new list with the same elements as lis, except that occurrences of oldval are replaced with newval. An item in lis should be replaced in the new list if it is eqv? to oldval. Example uses: (subst '1 '2 '(1 2 3 4 3 2 1)) => (2 2 3 4 3 2 2) (subst 'x '1 '(+ x x)) => (+ 1 1) Hints: This is a pretty straightforward list recursion problem similar to list-copy but you have to do something special when you encounter the occurrence of oldval. As usual when doing recursion, you should check for the base case, and default to the recursive case without an explicit check (e.g., use an else clause of a cond or an else branch of an if). That way, if you get bad (non-list) input, you'll force an error when you try to take the car or cdr of a non-pair. 3. Define a procedure pair-tree-subst which takes three arguments, like subst, except that the third argument is pt, a pair tree, rather than lis, a list. A pair-tree can be a leaf, which is any non-pair (including the empty list, for an empty pair-tree), or it can be a pair whose car and cdr are pair-trees. Note that the empty list can be a pair tree, but it's not treated specially. It's just a leaf---a non-pair. Example uses: (pair-tree-subst 'a 'z '()) -> '() (pair-tree-subst 'a 'z '((a . b) . (c . a))) => ((z . b) . (c . z)) note: this will actually print as ((z . b) c . z) (pair-tree-subst 'a 'z 'a) => z (pair-tree-subst 'a 'z '(a a a)) => (z z z) Hints: This is a pretty straightforward binary tree recursion problem. Think about the recursive definition of a pair-tree and use it to guide your coding. This data structure is kind of unusual, in that there are essentially no restrictions on what can be in it. Because of that, our recursion can be controlled by a simple pair? test, because we only need to tell what's an interior node and what's not. Notice that this is different from the recommended style of recursion down lists, where we do a check for the base case, and assume that otherwise we're looking at the recursive case, so an error will be forced if we get bad input. 4. Define a procedure list-tree-subst which takes three arguments, like subst, except that the third argument is a list tree, not a lis. (That is, it's a tree whose interior nodes are proper lists.) A list tree may be a simple item (not a pair or null), or a list of simple items, or lists of such things. (This implies that a tree node may be an empty list, but NOT an improper list. That doesn't make the problem harder.) Example uses: (list-tree-subst 'foo 'bar 'foo) => bar (list-tree-subst '1 '2 '(1 2 (1 2 (3 2 1) (1 2 3)))) => (2 2 (2 2 (3 2 2) (2 2 3))) (list-tree-subst '1 '2 '(1 . 2)) is an ERROR Hints: Formulate a simple recursive description of the data structure, and make sure that your recursion(s) reflect the nature of this structure. That is, you should use recursion to reflect the overall tree structure, and also use recursion to reflect the list structure at each level. You'll want two mutually-recursive procedures, one to process list-trees, and one to process interior nodes of list-trees, which are lists. Call them list-tree-subst and lt-node-subst. These should only be a few lines long, or you're probably doing something wrong. Don't make the problem any harder than it has to be. In particular, write your base cases first, and then rely on recursion to do almost all of the rest of the work. Be sure to realize you've got two different basic kinds of things to deal with: * leaves (which are not lists, so they don't start with a pair and aren't null)---you should do normal tree recursion for these---and * interior nodes, which should be proper lists. You should do the usual list recursion for these, making sure an error is signaled if you the list doesn't end with a null. (If you code list recursion the way I suggested in class, this will happen naturally.) To get the error signaling right for improper lists, what you want to do is recognize tree nodes as tree nodes, even if they're improper lists, and let lt-node-subst signal the error in the usual way when it tries to recurse over the improper list. (So when you test to see if something's a leaf in your main routine, you don't want to use (not (list? list-tree)), because then improper lists will count as leaves. You want to use (not (or (pair? list-tree) (null? list-tree))), so that any kind of list will be regarded as an interior node of the tree, not a leaf. Then when you recurse down the list in lt-node-subst, you can just do it in the usual way, checking for null? and taking the car and cdr otherwise. For an improper list, you'll try to take the car or cdr of a non-pair, and an error will be signaled.) 5. Write a version of map for yourself. It's in the course notes, but if you really understand recursion and first-class procedures, it should be easy enough to write map without copying your solution from me. (Of course, your code should work a lot like mine.) Remember, map makes a transformed copy of a list. Your version of map only needs to take two arguments, proc (a one-argument procedure) and lis (a list of items to apply it to). Call your procedure map1 to avoid redefining map. You'll want Scheme's built-in map for later problems. Example uses: (map1 car '((a b) (c d) (e f) (g h))) => (a c e g) (map1 cadr '((a b) (c d) (e f) (g h))) => (b d f h) (map1 (lambda (x) (+ x x)) '(1 2 3 4)) => (2 4 6 8) (map1 (lambda (x) (* x x)) '(1 2 3 4)) => (1 4 9 16) 6. Write a procedure mapappend that is like map, except that its argument proc must be a procedure that returns a list, and mapappend splices a its result list together like append, rather than nesting the values like list. (mapappend list '(1 2 3 4)) => (1 2 3 4) (mapappend (lambda (x) (list x x x)) '(1 2 3 4)) => (1 1 1 2 2 2 3 3 3 4 4 4) 7. Using map, write a procedure enlist that takes a list of items (of any type), and returns a new list whose elements are one-element lists containing the corresponding elements of the original list. Example uses: (enlist '(1 2 3 4 5)) => ((1) (2) (3) (4) (5)) (enlist '((foo bar) (baz 2 3) quux))) => (((foo bar)) ((baz 2 3)) (quux)) Hint: this is a one-liner. 8. Scheme's built-in procedure map can take more than two arguments. It can take a two-argument procedure and two lists, and apply The procedure to pairs of items from the two lists, like this: (map + '(1 2 3 4) '(10 20 30 40)) => (11 22 33 44) Using map, write a procedure in-twos that takes a pair of (equal-length) lists, and constructs a list half as long, whose elements are corresponding items of the original lists. If you've clobbered map by defining your own map that can't take multiple lists, then quit Scheme and restart so you'll see the built-in map again. Example uses: (in-twos '(a b c d e) '(1 2 3 4 5)) => ((a 1) (b 2) (c 3) (d 4) (d 5)) (in-twos '(steak ham soup) '(potatoes swiss-cheese sandwich)) => ((steak potatoes) (ham swiss-cheese) (soup sandwich)) Hint: map does most of the work for you. You mainly need to supply a procedure that does the right thing to corresponding elements of the list. 9. Write a procedure that's un-twos that is the opposite of in-twos. It should take a list of two-element lists and return a two-element list. The two elements of this list should be the list of first elements of the sublists of the original list, and the list of second elements of that list. (un-twos '((up down) (left right) (in out) (top bottom) (in-twos un-twos)) => ((up left in top in-twos) (down right out bottom un-twos)) Hint: this is easy with two calls to map. 10. Write a procedure pair-tree-map, which recursively transforms a pair tree (a binary tree of pairs where non-pairs are considered leaves) according to any one-arg function. Hints: you can recycle some of your old pair-tree code for this, just replacing specific operations with calls to a procedures passed as an argument. On the other hand, it's better if you can do it from scratch without consulting your old code. 11. Write a procedure pairings, which takes two lists as arguments and returns a list of all two-element lists whose first element is an element of the first list and whose second element is an element of the second list. Use map or mappappend as appropriate. Example uses: (pairings '(a b c) '(1 2 3)) => ((a 1) (a 2) (a 3) (b 1) (b 2) (b 3) (c 1) (c 2) c 3)) (pairings '(up down) '(left right)) => ((up left) (up right) (down left) (down right)) Hints: You want to come up with a procedure that can pair an item with each item in a list, and another procedure that can do that for each item in another list. The first of these two should use map, since you want to come up with a list of two-element lists. The second should use mapappend, because you want to splice those lists together. 12. Rewrite your subst routine using map. Hints: use a lambda expression that takes a list item and either returns it or substitutes the new value for it. Your lambda expression should create a procedure of one argument, since that's what map expects, but it can refer to variable bindings that are visible when the lambda expression is evaluated. This will create a procedure that "remembers" the bindings of oldval and newval that are in scope when it was created. 13. Rewrite your lt-node-subst from the tree substitution problem, so that it uses map instead of traversing lists recursively. Hint: notice that map does exactly what you want in terms of doing recursion over lists, and lets you plug in whatever procedure you want as the transformation to do to each element.