5653 - mu - Soul of a tiny new machine. More thorough tests → More comprehensible and rewrite-friendly software → More resilient society.

diff options

author	Kartik Agaram <vc@akkartik.com>	2019-09-14 08:52:38 -0700
committer	Kartik Agaram <vc@akkartik.com>	2019-09-14 08:52:38 -0700
commit	6614f9a2d88ca72591802bd370d9d7dd719f6f0f (patch)
tree	21fadac24172ecfffce79b4c9d3622f5d94190be /archive/2.vm/edit
parent	3b42da24c2b1c7a4f923fbdf765ff180591634bc (diff)
download	mu-6614f9a2d88ca72591802bd370d9d7dd719f6f0f.tar.gz

5653

Correct git hash for Soso.

Diffstat (limited to 'archive/2.vm/edit')

0 files changed, 0 insertions, 0 deletions

<A NAME="fish"></A> <CENTER><IMG SRC="../ss-pics/fish.jpg" ALT="figure: fish"></CENTER> <HTML> <HEAD> <TITLE>Simply Scheme: Introducing Computer Science ch 14: Common Patterns in Recursive Procedures</TITLE> </HEAD> <BODY> <HR> <CITE>Simply Scheme:</CITE> <CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT <H2>Chapter 14</H2> <H1>Common Patterns in Recursive Procedures</H1> <TABLE width="100%"><TR><TD> <IMG SRC="../simply.jpg" ALT="cover photo"> <TD><TABLE> <TR><TD align="right"><CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian Harvey</A> University of California, Berkeley</CITE> <TR><TD align="right"><CITE><A HREF="http://ccrma.stanford.edu/~matt">Matthew Wright</A> University of California, Santa Barbara</CITE> <TR><TD align="right"> <TR><TD align="right"><A HREF="../pdf/ssch14.pdf">Download PDF version</A> <TR><TD align="right"><A HREF="../ss-toc2.html">Back to Table of Contents</A> <TR><TD align="right"><A HREF="../ssch13/convince-recur.html">BACK</A> chapter thread <A HREF="number-name.html">NEXT</A> <TR><TD align="right"><A HREF="http://mitpress.mit.edu/0262082810">MIT Press web page for <CITE>Simply Scheme</CITE></A> </TABLE></TABLE> <HR> <A NAME="g1"></A> <A NAME="g2"></A> There are two ideas about how to solve programming problems.<A NAME="text1" HREF="recur-patterns.html#ft1">[1]</A> One idea is that programmers work mostly by recognizing categories of problems that come up repeatedly and remembering the solution that worked last time; therefore, programming students should learn a lot of program patterns, or templates, and fill in the blanks for each specific problem. Another idea is that there are a few powerful principles in programming, and that if a learner understands the principles, they can be applied to any problem, even one that doesn't fit a familiar pattern. Research suggests that an expert programmer, like an expert at any skill, does work mainly by recognizing patterns. Nevertheless, we lean toward the powerful-principle idea. The expert's memory is not full of arbitrary patterns; it's full of meaningful patterns, because the expert has gone through the process of struggling to reason out how each procedure works and how to write new procedures. Still, we think it's worth pointing out a few patterns that are so common that you'll have seen several examples of each before you finish this book. Once you learn these patterns, you can write similar procedures almost automatically. But there's an irony in learning patterns: In Scheme, once you've identified a pattern, you can write a general-purpose procedure that handles all such cases without writing individual procedures for each situation. Then you don't have to use the pattern any more! Chapter 8 presents several general pattern-handling procedures, called higher-order procedures. In this chapter we'll consider the patterns corresponding to those higher-order procedures, and we'll use the names of those procedures to name the patterns. What's the point of learning patterns if you can use higher-order procedures instead? There are at least two points. The first, as you'll see very soon, is that some problems almost follow one of the patterns; in that case, you can't use the corresponding higher-order procedure, which works only for problems that exactly follow the pattern. But you can use your understanding of the pattern to help with these related problems. The second point is that in Chapter 19 we'll show how the higher-order functions are themselves implemented using these recursive patterns. This chapter isn't an official list of all important patterns; as you gain programming experience, you'll certainly add more patterns to your repertoire. <H2>The <CODE>Every</CODE> Pattern</H2> Here's a procedure to square every number in a sentence of numbers: <PRE>(define (square-sent sent) (if (empty? sent) '() (se (square (first sent)) (square-sent (bf sent))))) </PRE> Here's a procedure to translate every word of a sentence into Pig Latin: <PRE>(define (pigl-sent sent) (if (empty? sent) '() (se (pigl (first sent)) (pigl-sent (bf sent))))) </PRE> The pattern here is pretty clear. Our recursive case will do something straightforward to the <CODE>first</CODE> of the sentence, such as <CODE>square</CODE>ing it or <CODE>pigl</CODE>ing it, and we'll combine that with the result of a recursive call on the <CODE>butfirst</CODE> of the sentence. The <CODE>letter-pairs</CODE> procedure that we wrote in Chapter 11 is an example of a procedure that follows the <CODE>every</CODE> pattern pretty closely, but not exactly. The difference is that <CODE>letter-pairs</CODE> looks at its argument sentence two words at a time. <PRE>(define (<A NAME="g3"></A>letter-pairs wd) (if (= (count wd) 1) '() (se (word (first wd) (first (bf wd))) (letter-pairs (bf wd))))) </PRE> Compare this with the earlier definition of <CODE>square-sent</CODE>. The recursive case still uses <CODE>se</CODE> to combine one part of the result with a recursive call based on the <CODE>butfirst</CODE> of the argument, but here both the first letter and the second letter of the argument contribute to the first word of the result. That's why the base case also has to be different; the recursive case requires at least two letters, so the base case is a one-letter word.<A NAME="text2" HREF="recur-patterns.html#ft2">[2]</A> Let's solve a slightly different problem. This time, we want to break the word down into non-overlapping pairs of letters, like this: <PRE>> (disjoint-pairs 'tripoli) ;; the new problem (TR IP OL I) > (letter-pairs 'tripoli) ;; compare the old one (TR RI IP PO OL LI) </PRE> The main difference between these two functions is that in <CODE>disjoint-pairs</CODE> we eliminate two letters at once in the recursive call. A second difference is that we have to deal with the special case of odd-length words. <PRE>(define (<A NAME="g4"></A>disjoint-pairs wd) (cond ((empty? wd) '()) ((= (count wd) 1) (se wd)) (else (se (word (first wd) (first (bf wd))) (disjoint-pairs (bf (bf wd))))))) </PRE> <H2>The <CODE>Keep</CODE> Pattern</H2> In the <CODE>every</CODE> pattern, we collect the results of transforming each element of a word or sentence into something else. This time we'll consider a different kind of problem: choosing some of the elements and forgetting about the others. First, here is a procedure to select the three-letter words from a sentence: <PRE>(define (keep-three-letter-words sent) (cond ((empty? sent) '()) ((= (count (first sent)) 3) (se (first sent) (keep-three-letter-words (bf sent)))) (else (keep-three-letter-words (bf sent))))) > (keep-three-letter-words '(one two three four five six seven)) (ONE TWO SIX) </PRE> Next, here is a procedure to select the vowels from a word: <PRE>(define (keep-vowels wd) (cond ((empty? wd) "") ((vowel? (first wd)) (word (first wd) (keep-vowels (bf wd)))) (else (keep-vowels (bf wd))))) > (keep-vowels 'napoleon) AOEO </PRE> Let's look at the differences between the <CODE>every</CODE> pattern and the <A NAME="g5"></A><A NAME="g6"></A> pattern. First of all, the <CODE>keep</CODE> procedures have three possible outcomes, instead of just two as in most <CODE>every</CODE>-like procedures. In the <CODE>every</CODE> pattern, we only have to distinguish between the base case and the recursive case. In the <CODE>keep</CODE> pattern, there is still a base case, but there are two recursive cases; we have to decide whether or not to keep the first available element in the return value. When we do keep an element, we keep the element itself, not some function of the element. As with the <CODE>every</CODE> pattern, there are situations that follow the <CODE>keep</CODE> pattern only approximately. Suppose we want to look for doubled letters within a word: <PRE>> (doubles 'bookkeeper) OOKKEE > (doubles 'mississippi) SSSSPP </PRE> This isn't a pure <CODE>keep</CODE> pattern example because we can't decide whether to keep the first letter by looking at that letter alone; we have to examine two at a time. But we can write a procedure using more or less the same pattern: <PRE>(define (<A NAME="g7"></A>doubles wd) (cond ((= (count wd) 1) "") ((equal? (first wd) (first (bf wd))) (word (first wd) (first (bf wd)) (doubles (bf (bf wd))))) (else (doubles (bf wd))))) </PRE> As in the <CODE>evens</CODE> example of Chapter 12, the base case of <CODE>doubles</CODE> is unusual, and one of the recursive calls chops off two letters at once in forming the smaller subproblem. But the structure of the <CODE>cond</CODE> with a base case clause, a clause for keeping letters, and a clause for rejecting letters is maintained. <H2>The <CODE>Accumulate</CODE> Pattern</H2> Here are two recursive procedures for functions that combine all of the elements of the argument into a single result: <PRE>(define (<A NAME="g8"></A>addup nums) (if (empty? nums) 0 (+ (first nums) (addup (bf nums))))) (define (<A NAME="g9"></A>scrunch-words sent) (if (empty? sent) "" (word (first sent) (scrunch-words (bf sent))))) > (addup '(8 3 6 1 10)) 28 > (scrunch-words '(ack now ledge able)) ACKNOWLEDGEABLE </PRE> What's the pattern? We're using some combiner (<CODE>+</CODE> or <CODE>word</CODE>) to connect the word we're up to with the result of the recursive call. The base case tests for an empty argument, but the base case return value must be the identity element of the combiner function. If there is no identity element for the combiner, as in the case of <CODE>max</CODE>, we modify the pattern slightly:<A NAME="text3" HREF="recur-patterns.html#ft3">[3]</A> <PRE>(define (<A NAME="g10"></A>sent-max sent) (if (= (count sent) 1) (first sent) (max (first sent) (sent-max (bf sent))))) </PRE> <H2>Combining Patterns</H2> <PRE>(define (<A NAME="g11"></A>add-numbers sent) (cond ((empty? sent) 0) ((number? (first sent)) (+ (first sent) (add-numbers (bf sent)))) (else (add-numbers (bf sent))))) > (add-numbers '(if 6 were 9)) 15 </PRE> This procedure combines aspects of <CODE>keep</CODE> with aspects of <CODE>accumulate</CODE>. We want to do two things at once: get rid of the words that aren't numbers and compute the sum of those that are numbers. (A simple <CODE>keep</CODE> would construct a sentence of them.) <CODE>Add-numbers</CODE> looks exactly like the <CODE>keep</CODE> pattern, except that there's a funny combiner and a funny base case, which look more like <CODE>accumulate</CODE>.<A NAME="text4" HREF="recur-patterns.html#ft4">[4]</A> Here's an example that combines <CODE>every</CODE> and <CODE>keep</CODE>. We want a procedure that takes a sentence as its argument and translates every word of the sentence into Pig Latin, but leaves out words that have no vowels, because the Pig Latin translator doesn't work for such words. The procedure <CODE>safe-pigl</CODE> will be like a <CODE>keep</CODE> pattern in that it keeps only words that contain vowels, but like an <CODE>every</CODE> in that the result contains transformed versions of the selected words, rather than the words themselves. <PRE>(define (<A NAME="g12"></A>safe-pigl sent) (cond ((empty? sent) '()) ((has-vowel? (first sent)) (se (pigl (first sent)) (safe-pigl (bf sent)))) (else (safe-pigl (bf sent))))) (define (<A NAME="g13"></A>has-vowel? wd) (not (empty? (keep-vowels wd)))) > (safe-pigl '(my pet fly is named xyzzy)) (ETPAY ISAY AMEDNAY) </PRE> Finally, here's an example that combines all three patterns. In Chapter 1 we wrote (using higher-order procedures) the <CODE>acronym</CODE> procedure, which selects the "real" words of a sentence (the <CODE>keep</CODE> pattern), takes the first letter of each word (the <CODE>every</CODE> pattern), and combines these initial letters into a single word (the <CODE>accumulate</CODE> pattern). In a recursive procedure we can carry out all three steps at once: <PRE>(define (<A NAME="g14"></A>acronym sent) (cond ((empty? sent) "") ((real-word? (first sent)) (word (first (first sent)) (acronym (bf sent)))) (else (acronym (bf sent))))) </PRE> Don't become obsessed with trying to make every recursive problem fit one of the three patterns we've shown here. As we said at the beginning of the chapter, what's most important is that you understand the principles of recursion in general, and understand how versatile recursion is. The patterns are just special cases that happen to come up fairly often. <H2>Helper Procedures</H2> Let's say we want a procedure <CODE>every-nth</CODE> that takes a number n and a sentence as arguments and selects every nth word from the sentence. <PRE>> (every-nth 3 '(with a little help from my friends)) (LITTLE MY) </PRE> We get in trouble if we try to write this in the obvious way, as a sort of <CODE>keep</CODE> pattern. <PRE>(define (every-nth n sent) ;; wrong! (cond ((empty? sent) '()) ((= n 1) (se (first sent) (every-nth <BIG>n</BIG> (bf sent)))) (else (every-nth (- n 1) (bf sent))))) </PRE> The problem is with the <CODE>n</CODE> that's in boldface. We're thinking that it's going to be the <CODE>n</CODE> of the original invocation of <CODE>every-nth</CODE>, that is, 3. But in fact, we've already counted <CODE>n</CODE> down so that in this invocation its value is 1. (Check out the first half of the same <CODE>cond</CODE> clause.) This procedure will correctly skip the first two words but will keep all the words after that point. That's because we're trying to remember two different numbers: the number we should always skip between kept words, and the number of words we still need to skip this time. If we're trying to remember two numbers, we need two names for them. The way to achieve this is to have our official <CODE>every-nth</CODE> procedure call a <A NAME="g15"></A><A NAME="g16"></A>helper procedure that takes an extra argument and does the real work: <PRE>(define (<A NAME="g17"></A>every-nth n sent) (every-nth-helper n n sent)) (define (<A NAME="g18"></A>every-nth-helper interval remaining sent) (cond ((empty? sent) '()) ((= remaining 1) (se (first sent) (every-nth-helper interval interval (bf sent)))) (else (every-nth-helper interval (- remaining 1) (bf sent))))) </PRE> This procedure always calls itself recursively with the same value of <CODE>interval</CODE>, but with a different value of <CODE>remaining</CODE> each time. <CODE>Remaining</CODE> keeps getting smaller by one in each recursive call until it equals 1. On that call, a word is kept for the return value, and we call <CODE>every-nth-helper</CODE> recursively with the value of <CODE>interval</CODE>, that is, the original value of <CODE>n</CODE>, as the new <CODE>remaining</CODE>. If you like, you can think of this combination of an initialization <A NAME="g19"></A> <A NAME="g20"></A> procedure and a helper procedure as another pattern for your collection. <H2>How to Use Recursive Patterns</H2> One way in which recursive patterns can be useful is if you think of them as templates with empty slots to fill in for a particular problem. Here are template versions of the <CODE>every</CODE>, <CODE>keep</CODE>, and <CODE>accumulate</CODE> patterns as applied to sentences: <PRE>(define (every-something sent) (if (empty? sent) '() (se (______ (first sent)) (every-something (bf sent))))) (define (keep-if-something sent) (cond ((empty? sent) '()) ((______<BIG>?</BIG> (first sent)) (se (first sent) (keep-if-something (bf sent)))) (else (keep-if-something (bf sent))))) </PRE> <A NAME="keeptemplate"></A> <PRE>(define (accumulate-somehow sent) (if (empty? sent) ______ (______ (first sent) (accumulate-somehow (bf sent))))) </PRE> Suppose you're trying to write a procedure <CODE>first-number</CODE> that takes a sentence as its argument and returns the first number in that sentence, but returns the word <CODE>no-number</CODE> if there are no numbers in the argument. The first step is to make a guess about which pattern will be most useful. In this case the program should start with an entire sentence and select a portion of that sentence, namely one word. Therefore, we start with the <CODE>keep</CODE> pattern. <PRE>(define (first-number sent) ;; first guess (cond ((empty? sent) '()) ((______ (first sent)) (se (first sent) (first-number (bf sent)))) (else (first-number (bf sent))))) </PRE> The next step is to fill in the blank. Obviously, since we're looking for a number, <CODE>number?</CODE> goes in the blank. The trouble is that this procedure returns all the numbers in the given sentence. Now our job is to see how the pattern must be modified to do what we want. The overall structure of the pattern is a <CODE>cond</CODE> with three clauses; we'll consider each clause separately. What should the procedure return if <CODE>sent</CODE> is empty? In that case, there is no first number in the sentence, so it should return <CODE>no-number</CODE>: <PRE>((empty? sent) 'no-number) </PRE> What if the first word of the sentence is a number? The program should return just that number, ignoring the rest of the sentence: <PRE>((number? (first sent)) (first sent)) </PRE> What if the first word of the sentence isn't a number? The procedure must make a recursive call for the <CODE>butfirst</CODE>, and whatever that recursive call returns is the answer. So the <CODE>else</CODE> clause does not have to be changed. Here's the whole procedure: <PRE>(define (<A NAME="g21"></A>first-number sent) (cond ((empty? sent) 'no-number) ((number? (first sent)) (first sent)) (else (first-number (bf sent))))) </PRE> After filling in the blank in the <CODE>keep</CODE> pattern, we solved this problem by focusing on the details of the procedure definition. We examined each piece of the definition to decide what changes were necessary. Instead, we could have focused on the behavior of the procedure. We would have found two ways in which the program didn't do what it was supposed to do: For an argument sentence containing numbers, it would return all of the numbers instead of just one of them. For a sentence without numbers, it would return the empty sentence instead of <CODE>no-number</CODE>. We would then have finished the job by debugging the procedure to fix each of these problems. The final result would have been the same. <H2>Problems That Don't Follow Patterns</H2> We want to write the procedure <CODE>sent-before?</CODE>, which takes two sentences as arguments and returns <CODE>#t</CODE> if the first comes alphabetically before the second. The general idea is to compare the sentences word by word. If the first words are different, then whichever is alphabetically earlier determines which sentence comes before the other. If the first words are equal, we go on to compare the second words.<A NAME="text5" HREF="recur-patterns.html#ft5">[5]</A> <PRE>> (sent-before? '(hold me tight) '(sun king)) #T > (sent-before? '(lovely rita) '(love you to)) #F > (sent-before? '(strawberry fields forever) '(strawberry fields usually)) #T </PRE> Does this problem follow any of the patterns we've seen? It's not an <CODE>every</CODE>, because the result isn't a sentence in which each word is a transformed version of a word in the arguments. It's not a <CODE>keep</CODE>, because the result isn't a subset of the words in the arguments. And it's not exactly an <CODE>accumulate</CODE>. We do end up with a single true or false result, rather than a sentence full of results. But in a typical <CODE>accumulate</CODE> problem, every word of the argument contributes to the solution. In this case only one word from each sentence determines the overall result. On the other hand, this problem does have something in common with the <CODE>keep</CODE> pattern: We know that on each invocation there will be three possibilities. We might reach a base case (an empty sentence); if not, the first words of the argument sentences might or might not be relevant to the solution. We'll have a structure similar to the usual <CODE>keep</CODE> pattern, except that there's no <CODE>se</CODE> involved; if we find unequal words, the problem is solved without further recursion. Also, we have two arguments, and either of them might be empty. <PRE>(define (<A NAME="g22"></A>sent-before? sent1 sent2) (cond ((empty? sent1) #t) ((empty? sent2) #f) ((before? (first sent1) (first sent2)) #t) ((before? (first sent2) (first sent1)) #f) (else (sent-before? (bf sent1) (bf sent2))))) </PRE> Although thinking about the <CODE>keep</CODE> pattern helped us to work out this solution, the result really doesn't look much like a <CODE>keep</CODE>. We had to invent most of the details by thinking about this particular problem, not by thinking about the pattern. In the next chapter we'll look at examples of recursive procedures that are quite different from any of these patterns. Remember, the patterns are a shortcut for many common problems, but don't learn the shortcut at the expense of the general technique. <H2>Pitfalls</H2> Review the pitfalls from Chapter 12; they're still relevant. How do you test for the base case? Most of the examples in this chapter have used <CODE>empty?</CODE>, and it's easy to fall into the habit of using that test without thinking. But, for example, if the argument is a number, that's probably the wrong test. Even when the argument is a sentence or a non-numeric word, it may not be empty in the base case, as in the Pig Latin example. A serious pitfall is failing to recognize a situation in which you need an extra variable and therefore need a helper procedure. If at each step you need the entire original argument as well as the argument that's getting closer to the base case, you probably need a helper procedure. For example, write a procedure <CODE>pairs</CODE> that takes a word as argument and returns a sentence of all possible two-letter words made of letters from the argument word, allowing duplicates, like this: <PRE>> (pairs 'toy) (TT TO TY OT OO OY YT YO YY) </PRE> A simple pitfall, when using a helper procedure, is to write a recursive call in the helper that calls the main procedure instead of calling the helper. (For example, what would have happened if we'd had <CODE>every-nth-helper</CODE> invoke <CODE>every-nth</CODE> instead of invoking itself?) Some recursive procedures with more than one argument require more than one base case. But some don't. One pitfall is to leave out a necessary base case; another is to include something that looks like a base case but doesn't fit the structure of the program. For example, the reason <CODE>sent-before?</CODE> needs two base cases is that on each recursive call, both <CODE>sent1</CODE> and <CODE>sent2</CODE> get smaller. Either sentence might run out first, and the procedure should return different values in those two cases. On the other hand, Exercise <A HREF="../ssch11/recursion.html#copies">11.7</A> asked you to write a procedure that has two arguments but needs only one base case: <PRE>(define (<A NAME="g23"></A>copies num wd) (if (= num 0) '() (se wd (copies (- num 1) wd)))) </PRE> In this example, the <CODE>wd</CODE> argument doesn't get smaller from one invocation to the next. It would be silly to test for <CODE>(empty? wd)</CODE>. A noteworthy intermediate case is <CODE><A NAME="g24"></A>every-nth-helper</CODE>. It does have two <CODE>cond</CODE> clauses that check for two different arguments reaching their smallest allowable values, but the <CODE>remaining</CODE> clause isn't a base case. If <CODE>remaining</CODE> has the value 1, the procedure still invokes itself recursively. The only general principle we can offer is that you have to think about what base cases are appropriate, not just routinely copy whatever worked last time. <H2>Exercises</H2> Classify each of these problems as a pattern (<CODE>every</CODE>, <CODE>keep</CODE>, or <CODE>accumulate</CODE>), if possible, and then write the procedure recursively. In some cases we've given an example of invoking the procedure we want you to write, instead of describing it. 14.1  <PRE>> (<A NAME="g25"></A>remove-once 'morning '(good morning good morning)) (GOOD GOOD MORNING) </PRE> (It's okay if your solution removes the other <CODE>MORNING</CODE> instead, as long as it removes only one of them.) <A NAME="remonce"></A> 14.2  <PRE>> (<A NAME="g26"></A>up 'town) (T TO TOW TOWN) </PRE> 14.3  <PRE>> (<A NAME="g27"></A>remdup '(ob la di ob la da)) ;; remove duplicates (OB LA DI DA) </PRE> <A NAME="remdup"></A> (It's okay if your procedure returns <CODE>(DI OB LA DA)</CODE> instead, as long as it removes all but one instance of each duplicated word.) 14.4  <PRE>> (<A NAME="g28"></A>odds '(i lost my little girl)) (I MY GIRL) </PRE><A NAME="exodds"></A> 14.5  [<A HREF="../ssch8/higher.html#lettcount">8.7</A>] Write a procedure <CODE><A NAME="g29"></A>letter-count</CODE> that takes a sentence as its argument and returns the total number of letters in the sentence: <A NAME="lettcrec"></A> <PRE>> (letter-count '(fixing a hole)) 11 </PRE> 14.6  Write <CODE>member?</CODE>. 14.7  Write <CODE>differences</CODE>, which takes a sentence of numbers as its argument and returns a sentence containing the differences between adjacent elements. (The length of the returned sentence is one less than that of the argument.) <PRE>> (<A NAME="g30"></A>differences '(4 23 9 87 6 12)) (19 -14 78 -81 6) </PRE> 14.8  Write <CODE>expand</CODE>, which takes a sentence as its argument. It returns a sentence similar to the argument, except that if a number appears in the argument, then the return value contains that many copies of the following word: <PRE>> (expand '(4 calling birds 3 french hens)) (CALLING CALLING CALLING CALLING BIRDS FRENCH FRENCH FRENCH HENS) > (expand '(the 7 samurai)) (THE SAMURAI SAMURAI SAMURAI SAMURAI SAMURAI SAMURAI SAMURAI) </PRE> 14.9  Write a procedure called <CODE><A NAME="g31"></A>location</CODE> that takes two arguments, a word and a sentence. It should return a number indicating where in the sentence that word can be found. If the word isn't in the sentence, return <CODE>#f</CODE>. If the word appears more than once, return the location of the first appearance. <PRE>> (location 'me '(you never give me your money)) 4 </PRE> 14.10  Write the procedure <CODE><A NAME="g32"></A>count-adjacent-duplicates</CODE> that takes a sentence as an argument and returns the number of words in the sentence that are immediately followed by the same word: <PRE>> (count-adjacent-duplicates '(y a b b a d a b b a d o o)) 3 > (count-adjacent-duplicates '(yeah yeah yeah)) 2 </PRE> 14.11  Write the procedure <CODE><A NAME="g33"></A>remove-adjacent-duplicates</CODE> that takes a sentence as argument and returns the same sentence but with any word that's immediately followed by the same word removed: <PRE>> (remove-adjacent-duplicates '(y a b b a d a b b a d o o)) (Y A B A D A B A D O) > (remove-adjacent-duplicates '(yeah yeah yeah)) (YEAH) </PRE> 14.12  Write a procedure <CODE><A NAME="g34"></A>progressive-squares?</CODE> that takes a sentence of numbers as its argument. It should return <CODE>#t</CODE> if each number (other than the first) is the square of the number before it: <PRE>> (progressive-squares? '(3 9 81 6561)) #T > (progressive-squares? '(25 36 49 64)) #F </PRE> 14.13  What does the <CODE>pigl</CODE> procedure from Chapter 11 do if you invoke it with a word like "frzzmlpt" that has no vowels? Fix it so that it returns "frzzmlptay." 14.14  Write a predicate <CODE>same-shape?</CODE> that takes two sentences as arguments. It should return <CODE>#t</CODE> if two conditions are met: The two sentences must have the same number of words, and each word of the first sentence must have the same number of letters as the word in the corresponding position in the second sentence. <PRE>> (same-shape? '(the fool on the hill) '(you like me too much)) #T > (same-shape? '(the fool on the hill) '(and your bird can sing)) #F </PRE> 14.15  <A NAME="mergeex"></A> Write <CODE><A NAME="g35"></A>merge</CODE>, a procedure that takes two sentences of numbers as arguments. Each sentence must consist of numbers in increasing order. <CODE>Merge</CODE> should return a single sentence containing all of the numbers, in order. (We'll use this in the next chapter as part of a sorting algorithm.) <PRE>> (merge '(4 7 18 40 99) '(3 6 9 12 24 36 50)) (3 4 6 7 9 12 18 24 36 40 50 99) </PRE> 14.16  Write a procedure <CODE><A NAME="g36"></A>syllables</CODE> that takes a word as its argument and returns the number of syllables in the word, counted according to the following rule: the number of syllables is the number of vowels, except that a group of consecutive vowels counts as one. For example, in the word "soaring," the group "oa" represents one syllable and the vowel "i" represents a second one. Be sure to choose test cases that expose likely failures of your procedure. For example, what if the word ends with a vowel? What if it ends with two vowels in a row? What if it has more than two consecutive vowels? (Of course this rule isn't good enough. It doesn't deal with things like silent "e"s that don't create a syllable ("like"), consecutive vowels that don't form a diphthong ("cooperate"), letters like "y" that are vowels only sometimes, etc. If you get bored, see whether you can teach the program to recognize some of these special cases.) <HR> <A NAME="ft1" HREF="recur-patterns.html#text1">[1]</A> That's because there are two kinds of people: those who think there are two kinds of people, and those who don't. <A NAME="ft2" HREF="recur-patterns.html#text2">[2]</A> If you've read Chapter 8, you know that you could implement <CODE>square-sent</CODE> and <CODE>pigl-sent</CODE> without recursion, using the <CODE>every</CODE> higher order function. But try using <CODE>every</CODE> to implement <CODE>letter-pairs</CODE>; you'll find that you can't quite make it work. <A NAME="ft3" HREF="recur-patterns.html#text3">[3]</A> Of course, if your version of Scheme has −∞, you can use it as the return value for an empty sentence, instead of changing the pattern. <A NAME="ft4" HREF="recur-patterns.html#text4">[4]</A> Here's the higher-order function version, from Chapter 8: <PRE>(define (add-numbers sent) (accumulate + (keep number? sent))) </PRE> The higher-order function version is more self-documenting and easier to write. The recursive version, however, is slightly more efficient, because it avoids building up a sentence as an intermediate value only to discard it in the final result. If we were writing this program for our own use, we'd probably choose the higher-order function version; but if we were dealing with sentences of length 10,000 instead of length 10, we'd pay more attention to efficiency. <A NAME="ft5" HREF="recur-patterns.html#text5">[5]</A> Dictionaries use a different ordering rule, in which the sentences are treated as if they were single words, with the spaces removed. By the dictionary rule, "a c" is treated as if it were "ac" and comes after "ab"; by our rule, "a c" comes before "ab" because we compare the first words ("a" and "ab"). <A HREF="../ss-toc2.html">(back to Table of Contents)</A> <A HREF="../ssch13/convince-recur.html">BACK</A> chapter thread <A HREF="number-name.html">NEXT</A> <ADDRESS> <A HREF="../index.html">Brian Harvey</A>, <CODE>bh@cs.berkeley.edu</CODE> </ADDRESS> </BODY> </HTML>


context:
space:
mode: