diff options
| author | elioat <elioat@tilde.institute> | 2023-08-23 07:52:19 -0400 |
|---|---|---|
| committer | elioat <elioat@tilde.institute> | 2023-08-23 07:52:19 -0400 |
| commit | 562a9a52d599d9a05f871404050968a5fd282640 (patch) | |
| tree | 7d3305c1252c043bfe246ccc7deff0056aa6b5ab /js/games/nluqo.github.io/~bh/ssch14 | |
| parent | 5d012c6c011a9dedf7d0a098e456206244eb5a0f (diff) | |
| download | tour-562a9a52d599d9a05f871404050968a5fd282640.tar.gz | |
*
Diffstat (limited to 'js/games/nluqo.github.io/~bh/ssch14')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/ssch14/number-name | 91 | ||||
| -rw-r--r-- | js/games/nluqo.github.io/~bh/ssch14/number-name.html | 91 | ||||
| -rw-r--r-- | js/games/nluqo.github.io/~bh/ssch14/recur-patterns | 789 | ||||
| -rw-r--r-- | js/games/nluqo.github.io/~bh/ssch14/recur-patterns.html | 789 |
4 files changed, 1760 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/ssch14/number-name b/js/games/nluqo.github.io/~bh/ssch14/number-name new file mode 100644 index 0000000..bac8cd1 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/ssch14/number-name @@ -0,0 +1,91 @@ +<P> + +<P> +<HTML> +<HEAD> +<TITLE>Simply Scheme:Project: Spelling Names of Huge Numbers</TITLE> +</HEAD> +<BODY> +<CITE>Simply Scheme</CITE>: +<CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT +<H1>Project: Spelling Names of Huge Numbers</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><BR>University of California, Berkeley</CITE> +<TR><TD align="right"><CITE><A HREF="http://ccrma.stanford.edu/~matt">Matthew +Wright</A><BR>University of California, Santa Barbara</CITE> +<TR><TD align="right"><BR> +<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="recur-patterns.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../ssch15/adv-recur.html"><STRONG>NEXT</STRONG></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> + +<P> + + +<P>Write a procedure <CODE><A NAME="g1"></A>number-name</CODE> that takes a positive integer +argument and returns a sentence containing that number spelled out in words: + +<P><PRE>> (number-name 5513345) +(FIVE MILLION FIVE HUNDRED THIRTEEN THOUSAND THREE HUNDRED FORTY FIVE) + +> (number-name (factorial 20)) +(TWO QUINTILLION FOUR HUNDRED THIRTY TWO QUADRILLION NINE HUNDRED TWO + TRILLION EIGHT BILLION ONE HUNDRED SEVENTY SIX MILLION SIX HUNDRED + FORTY THOUSAND) +</PRE> + +<P>There are some special cases you will need to consider: + +<P><P><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">Numbers in which some particular digit is zero +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">Numbers like 1,000,529 in which an entire group of three digits is zero. +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">Numbers in the teens. + +</TABLE><P> + +<P>Here are two hints. First, split the number into groups of three digits, +going from right to left. Also, use the sentence + +<P><PRE>'(thousand million billion trillion quadrillion quintillion + sextillion septillion octillion nonillion decillion) +</PRE> + +<P>You can write this bottom-up or top-down. To work bottom-up, pick a subtask +and get that working before you tackle the overall structure of the +problem. For example, write a procedure that returns the word <CODE>FIFTEEN</CODE> +given the argument <CODE>15</CODE>. + +<P>To work top-down, start by writing <CODE>number-name</CODE>, freely assuming the +existence of whatever helper procedures you like. You can begin debugging +by writing <EM>stub</EM> procedures that fit into the overall program but +don't really do their job correctly. For example, as an intermediate stage +you might end up with a program that works like this: + +<P><PRE>> (number-name 1428425) ;; intermediate version +(1 MILLION 428 THOUSAND 425) +</PRE> + + +<P> + + +<HR> +<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P> +<A HREF="recur-patterns.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../ssch15/adv-recur.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> diff --git a/js/games/nluqo.github.io/~bh/ssch14/number-name.html b/js/games/nluqo.github.io/~bh/ssch14/number-name.html new file mode 100644 index 0000000..bac8cd1 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/ssch14/number-name.html @@ -0,0 +1,91 @@ +<P> + +<P> +<HTML> +<HEAD> +<TITLE>Simply Scheme:Project: Spelling Names of Huge Numbers</TITLE> +</HEAD> +<BODY> +<CITE>Simply Scheme</CITE>: +<CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT +<H1>Project: Spelling Names of Huge Numbers</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><BR>University of California, Berkeley</CITE> +<TR><TD align="right"><CITE><A HREF="http://ccrma.stanford.edu/~matt">Matthew +Wright</A><BR>University of California, Santa Barbara</CITE> +<TR><TD align="right"><BR> +<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="recur-patterns.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../ssch15/adv-recur.html"><STRONG>NEXT</STRONG></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> + +<P> + + +<P>Write a procedure <CODE><A NAME="g1"></A>number-name</CODE> that takes a positive integer +argument and returns a sentence containing that number spelled out in words: + +<P><PRE>> (number-name 5513345) +(FIVE MILLION FIVE HUNDRED THIRTEEN THOUSAND THREE HUNDRED FORTY FIVE) + +> (number-name (factorial 20)) +(TWO QUINTILLION FOUR HUNDRED THIRTY TWO QUADRILLION NINE HUNDRED TWO + TRILLION EIGHT BILLION ONE HUNDRED SEVENTY SIX MILLION SIX HUNDRED + FORTY THOUSAND) +</PRE> + +<P>There are some special cases you will need to consider: + +<P><P><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">Numbers in which some particular digit is zero +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">Numbers like 1,000,529 in which an entire group of three digits is zero. +</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">Numbers in the teens. + +</TABLE><P> + +<P>Here are two hints. First, split the number into groups of three digits, +going from right to left. Also, use the sentence + +<P><PRE>'(thousand million billion trillion quadrillion quintillion + sextillion septillion octillion nonillion decillion) +</PRE> + +<P>You can write this bottom-up or top-down. To work bottom-up, pick a subtask +and get that working before you tackle the overall structure of the +problem. For example, write a procedure that returns the word <CODE>FIFTEEN</CODE> +given the argument <CODE>15</CODE>. + +<P>To work top-down, start by writing <CODE>number-name</CODE>, freely assuming the +existence of whatever helper procedures you like. You can begin debugging +by writing <EM>stub</EM> procedures that fit into the overall program but +don't really do their job correctly. For example, as an intermediate stage +you might end up with a program that works like this: + +<P><PRE>> (number-name 1428425) ;; intermediate version +(1 MILLION 428 THOUSAND 425) +</PRE> + + +<P> + + +<HR> +<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P> +<A HREF="recur-patterns.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../ssch15/adv-recur.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> diff --git a/js/games/nluqo.github.io/~bh/ssch14/recur-patterns b/js/games/nluqo.github.io/~bh/ssch14/recur-patterns new file mode 100644 index 0000000..cfdd3aa --- /dev/null +++ b/js/games/nluqo.github.io/~bh/ssch14/recur-patterns @@ -0,0 +1,789 @@ +<P> + +<A NAME="fish"></A> +<P><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><BR>University of California, Berkeley</CITE> +<TR><TD align="right"><CITE><A HREF="http://ccrma.stanford.edu/~matt">Matthew +Wright</A><BR>University of California, Santa Barbara</CITE> +<TR><TD align="right"><BR> +<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"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="number-name.html"><STRONG>NEXT</STRONG></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> + + +<P><A NAME="g1"></A> +<A NAME="g2"></A> + +<P> +<P>There are two ideas about how to solve programming problems.<A NAME="text1" HREF="recur-patterns#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 <EM>patterns,</EM> or <EM>templates,</EM> 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 <EM>any</EM> problem, even one that +doesn't fit a familiar pattern. + +<P>Research suggests that an expert programmer, like an expert at any skill, +<EM>does</EM> 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 <EM>meaningful</EM> patterns, because the +expert has gone through the process of struggling to reason out how each +procedure works and how to write new procedures. + +<P>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 <EM>higher-order</EM> 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. + +<P>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 <EM>almost</EM> follow one of the patterns; in +that case, you can't use the corresponding higher-order procedure, which +works only for problems that <EM>exactly</EM> 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. + +<P>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. + +<P><H2>The <CODE><B>Every</B></CODE> Pattern</H2> + +<P>Here's a procedure to square every number in a sentence of numbers: + +<P><PRE>(define (square-sent sent) + (if (empty? sent) + '() + (se (square (first sent)) + (square-sent (bf sent))))) +</PRE> + +<P>Here's a procedure to translate every word of a sentence into Pig Latin: + +<P><PRE>(define (pigl-sent sent) + (if (empty? sent) + '() + (se (pigl (first sent)) + (pigl-sent (bf sent))))) +</PRE> + +<P>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. + +<P>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. + +<P><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> + +<P>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#ft2">[2]</A> + +<P>Let's solve a slightly different problem. This time, we want to break the +word down into <EM>non-overlapping</EM> pairs of letters, like this: + +<P><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> + +<P>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. + +<P><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> + +<P><H2>The <CODE><B>Keep</B></CODE> Pattern</H2> + +<P>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: + +<P> +<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> + +<P> +Next, here is a procedure to select the vowels from a word: + +<P><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> + +<P>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 <EM>two</EM> 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. + +<P>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: + +<P> +<PRE>> (doubles 'bookkeeper) +OOKKEE + +> (doubles 'mississippi) +SSSSPP +</PRE> + +<P>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: + +<P><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> + +<P>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. + +<P><H2>The <CODE><B>Accumulate</B></CODE> Pattern</H2> + +<P>Here are two recursive procedures for functions that combine all of the +elements of the argument into a single result: + +<P><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> + +<P>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. + +<P>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#ft3">[3]</A> + +<P><PRE>(define (<A NAME="g10"></A>sent-max sent) + (if (= (count sent) 1) + (first sent) + (max (first sent) + (sent-max (bf sent))))) +</PRE> + +<P><H2>Combining Patterns</H2> + +<P><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> + +<P>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 <EM>sum</EM> 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#ft4">[4]</A> + +<P> +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. + +<P><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> + +<P> +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: + +<P><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> + +<P>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. + +<P><H2>Helper Procedures</H2> + +<P>Let's say we want a procedure <CODE>every-nth</CODE> that takes a number <EM>n</EM> and a +sentence as arguments and selects every <EM>n</EM>th word from the sentence. + +<P><PRE>> (every-nth 3 '(with a little help from my friends)) +(LITTLE MY) +</PRE> + +<P>We get in trouble if we try to write this in the obvious way, as a sort of +<CODE>keep</CODE> pattern. + +<P><PRE>(define (every-nth n sent) ;; wrong! + (cond ((empty? sent) '()) + ((= n 1) + (se (first sent) (every-nth <STRONG><BIG>n</BIG></STRONG> (bf sent)))) + (else (every-nth (- n 1) (bf sent))))) +</PRE> + +<P>The problem is with the <CODE><B>n</B></CODE> that's in boldface. +We're thinking that it's going to be the <CODE>n</CODE> of the <EM>original</EM> +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. + +<P> +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: + +<P><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> + +<P>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 <EM>original</EM> value of <CODE>n</CODE>, as the new <CODE>remaining</CODE>. +If you like, you can think of this combination of an <EM>initialization</EM> +<A NAME="g19"></A> +<A NAME="g20"></A> +procedure and a <EM>helper</EM> procedure as another pattern for your +collection. + +<P> +<P><H2>How to Use Recursive Patterns</H2> + +<P>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: + +<P><PRE>(define (<B>every-something</B> sent) + (if (empty? sent) + '() + (se (______ (first sent)) + (<B>every-something</B> (bf sent))))) + +(define (<B>keep-if-something</B> sent) + (cond ((empty? sent) '()) + ((______<STRONG><BIG>?</BIG></STRONG> (first sent)) + (se (first sent) (<B>keep-if-something</B> (bf sent)))) + (else (<B>keep-if-something</B> (bf sent))))) +</PRE> + +<P> +<A NAME="keeptemplate"></A> +<PRE>(define (<B>accumulate-somehow</B> sent) + (if (empty? sent) + ______ + (______ (first sent) + (<B>accumulate-somehow</B> (bf sent))))) +</PRE> + +<P>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. + +<P><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> + +<P>The next step is to fill in the blank. Obviously, since we're looking for a +number, <CODE>number?</CODE> goes in the blank. + +<P>The trouble is that this procedure returns <EM>all</EM> 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. + +<P>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>: + +<P><PRE>((empty? sent) <B>'no-number</B>) +</PRE> + +<P>What if the first word of the sentence is a number? The program should +return just that number, ignoring the rest of the sentence: + +<P><PRE>((number? (first sent)) <B>(first sent)</B>) +</PRE> + +<P>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. + +<P>Here's the whole procedure: + +<P><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> + +<P>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 <EM>behavior</EM> 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 <EM>debugging</EM> the procedure to fix each of these +problems. The final result would have been the same. + +<P> +<H2>Problems That Don't Follow Patterns</H2> + +<P>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#ft5">[5]</A> + +<P><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> + +<P>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. + +<P>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. + +<P>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. + +<P><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> + +<P>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. + +<P>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. + +<P><H2>Pitfalls</H2> + +<P>Review the pitfalls from Chapter 12; they're still relevant. + +<P> +<P>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. + +<P> +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: + +<P><PRE>> (pairs 'toy) +(TT TO TY OT OO OY YT YO YY) +</PRE> + +<P> + +<P>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?) + +<P>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. + +<P>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. + +<P>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: + +<P><PRE>(define (<A NAME="g23"></A>copies num wd) + (if (= num 0) + '() + (se wd (copies (- num 1) wd)))) +</PRE> + +<P>In this example, the <CODE>wd</CODE> argument <EM>doesn't</EM> get smaller +from one invocation to the next. It would be silly to test for <CODE>(empty? wd)</CODE>. + +<P>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. + +<P>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. + +<P> +<H2>Exercises</H2> + +<P>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. + +<P><B>14.1</B> <PRE>> (<A NAME="g25"></A>remove-once 'morning '(good morning good morning)) +(GOOD GOOD MORNING) +</PRE> + +<P>(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> + + + +<P> +<B>14.2</B> <PRE>> (<A NAME="g26"></A>up 'town) +(T TO TOW TOWN) +</PRE> + +<P> +<B>14.3</B> <PRE>> (<A NAME="g27"></A>remdup '(ob la di ob la da)) ;; remove duplicates +(OB LA DI DA) +</PRE> + +<P><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.) + + +<P> +<P> +<B>14.4</B> <PRE>> (<A NAME="g28"></A>odds '(i lost my little girl)) +(I MY GIRL) +</PRE><A NAME="exodds"></A> + +<P> +<B>14.5</B> [<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> + +<P><PRE>> (letter-count '(fixing a hole)) +11 +</PRE> + +<P> +<B>14.6</B> Write <CODE>member?</CODE>. + + +<P> +<B>14.7</B> 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.) + +<P><PRE>> (<A NAME="g30"></A>differences '(4 23 9 87 6 12)) +(19 -14 78 -81 6) +</PRE> + +<P> +<B>14.8</B> 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: + +<P><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> + +<P> +<B>14.9</B> 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. + +<P><PRE>> (location 'me '(you never give me your money)) +4 +</PRE> + +<P> +<B>14.10</B> 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: + +<P><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> + +<P> +<B>14.11</B> 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: + +<P><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> + +<P> +<B>14.12</B> 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: + +<P><PRE>> (progressive-squares? '(3 9 81 6561)) +#T + +> (progressive-squares? '(25 36 49 64)) +#F +</PRE> + +<P> +<B>14.13</B> 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." + + +<P> +<B>14.14</B> 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. + +<P><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> + + +<P> +<P> +<B>14.15</B> <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.) + +<P><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> + +<P> +<B>14.16</B> 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. + +<P>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? + +<P>(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.) + +<P> + +<HR> +<A NAME="ft1" HREF="recur-patterns#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.<P> +<A NAME="ft2" HREF="recur-patterns#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.<P> +<A NAME="ft3" HREF="recur-patterns#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.<P> +<A NAME="ft4" HREF="recur-patterns#text4">[4]</A> Here's the higher-order function version, from Chapter 8: + +<P><PRE>(define (add-numbers sent) + (accumulate + (keep number? sent))) +</PRE> + +<P>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.<P> +<A NAME="ft5" HREF="recur-patterns#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").<P> +<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P> +<A HREF="../ssch13/convince-recur.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="number-name.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> diff --git a/js/games/nluqo.github.io/~bh/ssch14/recur-patterns.html b/js/games/nluqo.github.io/~bh/ssch14/recur-patterns.html new file mode 100644 index 0000000..10e4fc4 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/ssch14/recur-patterns.html @@ -0,0 +1,789 @@ +<P> + +<A NAME="fish"></A> +<P><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><BR>University of California, Berkeley</CITE> +<TR><TD align="right"><CITE><A HREF="http://ccrma.stanford.edu/~matt">Matthew +Wright</A><BR>University of California, Santa Barbara</CITE> +<TR><TD align="right"><BR> +<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"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="number-name.html"><STRONG>NEXT</STRONG></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> + + +<P><A NAME="g1"></A> +<A NAME="g2"></A> + +<P> +<P>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 <EM>patterns,</EM> or <EM>templates,</EM> 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 <EM>any</EM> problem, even one that +doesn't fit a familiar pattern. + +<P>Research suggests that an expert programmer, like an expert at any skill, +<EM>does</EM> 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 <EM>meaningful</EM> patterns, because the +expert has gone through the process of struggling to reason out how each +procedure works and how to write new procedures. + +<P>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 <EM>higher-order</EM> 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. + +<P>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 <EM>almost</EM> follow one of the patterns; in +that case, you can't use the corresponding higher-order procedure, which +works only for problems that <EM>exactly</EM> 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. + +<P>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. + +<P><H2>The <CODE><B>Every</B></CODE> Pattern</H2> + +<P>Here's a procedure to square every number in a sentence of numbers: + +<P><PRE>(define (square-sent sent) + (if (empty? sent) + '() + (se (square (first sent)) + (square-sent (bf sent))))) +</PRE> + +<P>Here's a procedure to translate every word of a sentence into Pig Latin: + +<P><PRE>(define (pigl-sent sent) + (if (empty? sent) + '() + (se (pigl (first sent)) + (pigl-sent (bf sent))))) +</PRE> + +<P>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. + +<P>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. + +<P><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> + +<P>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> + +<P>Let's solve a slightly different problem. This time, we want to break the +word down into <EM>non-overlapping</EM> pairs of letters, like this: + +<P><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> + +<P>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. + +<P><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> + +<P><H2>The <CODE><B>Keep</B></CODE> Pattern</H2> + +<P>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: + +<P> +<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> + +<P> +Next, here is a procedure to select the vowels from a word: + +<P><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> + +<P>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 <EM>two</EM> 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. + +<P>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: + +<P> +<PRE>> (doubles 'bookkeeper) +OOKKEE + +> (doubles 'mississippi) +SSSSPP +</PRE> + +<P>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: + +<P><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> + +<P>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. + +<P><H2>The <CODE><B>Accumulate</B></CODE> Pattern</H2> + +<P>Here are two recursive procedures for functions that combine all of the +elements of the argument into a single result: + +<P><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> + +<P>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. + +<P>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> + +<P><PRE>(define (<A NAME="g10"></A>sent-max sent) + (if (= (count sent) 1) + (first sent) + (max (first sent) + (sent-max (bf sent))))) +</PRE> + +<P><H2>Combining Patterns</H2> + +<P><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> + +<P>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 <EM>sum</EM> 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> + +<P> +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. + +<P><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> + +<P> +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: + +<P><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> + +<P>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. + +<P><H2>Helper Procedures</H2> + +<P>Let's say we want a procedure <CODE>every-nth</CODE> that takes a number <EM>n</EM> and a +sentence as arguments and selects every <EM>n</EM>th word from the sentence. + +<P><PRE>> (every-nth 3 '(with a little help from my friends)) +(LITTLE MY) +</PRE> + +<P>We get in trouble if we try to write this in the obvious way, as a sort of +<CODE>keep</CODE> pattern. + +<P><PRE>(define (every-nth n sent) ;; wrong! + (cond ((empty? sent) '()) + ((= n 1) + (se (first sent) (every-nth <STRONG><BIG>n</BIG></STRONG> (bf sent)))) + (else (every-nth (- n 1) (bf sent))))) +</PRE> + +<P>The problem is with the <CODE><B>n</B></CODE> that's in boldface. +We're thinking that it's going to be the <CODE>n</CODE> of the <EM>original</EM> +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. + +<P> +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: + +<P><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> + +<P>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 <EM>original</EM> value of <CODE>n</CODE>, as the new <CODE>remaining</CODE>. +If you like, you can think of this combination of an <EM>initialization</EM> +<A NAME="g19"></A> +<A NAME="g20"></A> +procedure and a <EM>helper</EM> procedure as another pattern for your +collection. + +<P> +<P><H2>How to Use Recursive Patterns</H2> + +<P>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: + +<P><PRE>(define (<B>every-something</B> sent) + (if (empty? sent) + '() + (se (______ (first sent)) + (<B>every-something</B> (bf sent))))) + +(define (<B>keep-if-something</B> sent) + (cond ((empty? sent) '()) + ((______<STRONG><BIG>?</BIG></STRONG> (first sent)) + (se (first sent) (<B>keep-if-something</B> (bf sent)))) + (else (<B>keep-if-something</B> (bf sent))))) +</PRE> + +<P> +<A NAME="keeptemplate"></A> +<PRE>(define (<B>accumulate-somehow</B> sent) + (if (empty? sent) + ______ + (______ (first sent) + (<B>accumulate-somehow</B> (bf sent))))) +</PRE> + +<P>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. + +<P><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> + +<P>The next step is to fill in the blank. Obviously, since we're looking for a +number, <CODE>number?</CODE> goes in the blank. + +<P>The trouble is that this procedure returns <EM>all</EM> 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. + +<P>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>: + +<P><PRE>((empty? sent) <B>'no-number</B>) +</PRE> + +<P>What if the first word of the sentence is a number? The program should +return just that number, ignoring the rest of the sentence: + +<P><PRE>((number? (first sent)) <B>(first sent)</B>) +</PRE> + +<P>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. + +<P>Here's the whole procedure: + +<P><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> + +<P>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 <EM>behavior</EM> 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 <EM>debugging</EM> the procedure to fix each of these +problems. The final result would have been the same. + +<P> +<H2>Problems That Don't Follow Patterns</H2> + +<P>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> + +<P><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> + +<P>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. + +<P>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. + +<P>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. + +<P><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> + +<P>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. + +<P>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. + +<P><H2>Pitfalls</H2> + +<P>Review the pitfalls from Chapter 12; they're still relevant. + +<P> +<P>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. + +<P> +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: + +<P><PRE>> (pairs 'toy) +(TT TO TY OT OO OY YT YO YY) +</PRE> + +<P> + +<P>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?) + +<P>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. + +<P>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. + +<P>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: + +<P><PRE>(define (<A NAME="g23"></A>copies num wd) + (if (= num 0) + '() + (se wd (copies (- num 1) wd)))) +</PRE> + +<P>In this example, the <CODE>wd</CODE> argument <EM>doesn't</EM> get smaller +from one invocation to the next. It would be silly to test for <CODE>(empty? wd)</CODE>. + +<P>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. + +<P>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. + +<P> +<H2>Exercises</H2> + +<P>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. + +<P><B>14.1</B> <PRE>> (<A NAME="g25"></A>remove-once 'morning '(good morning good morning)) +(GOOD GOOD MORNING) +</PRE> + +<P>(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> + + + +<P> +<B>14.2</B> <PRE>> (<A NAME="g26"></A>up 'town) +(T TO TOW TOWN) +</PRE> + +<P> +<B>14.3</B> <PRE>> (<A NAME="g27"></A>remdup '(ob la di ob la da)) ;; remove duplicates +(OB LA DI DA) +</PRE> + +<P><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.) + + +<P> +<P> +<B>14.4</B> <PRE>> (<A NAME="g28"></A>odds '(i lost my little girl)) +(I MY GIRL) +</PRE><A NAME="exodds"></A> + +<P> +<B>14.5</B> [<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> + +<P><PRE>> (letter-count '(fixing a hole)) +11 +</PRE> + +<P> +<B>14.6</B> Write <CODE>member?</CODE>. + + +<P> +<B>14.7</B> 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.) + +<P><PRE>> (<A NAME="g30"></A>differences '(4 23 9 87 6 12)) +(19 -14 78 -81 6) +</PRE> + +<P> +<B>14.8</B> 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: + +<P><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> + +<P> +<B>14.9</B> 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. + +<P><PRE>> (location 'me '(you never give me your money)) +4 +</PRE> + +<P> +<B>14.10</B> 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: + +<P><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> + +<P> +<B>14.11</B> 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: + +<P><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> + +<P> +<B>14.12</B> 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: + +<P><PRE>> (progressive-squares? '(3 9 81 6561)) +#T + +> (progressive-squares? '(25 36 49 64)) +#F +</PRE> + +<P> +<B>14.13</B> 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." + + +<P> +<B>14.14</B> 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. + +<P><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> + + +<P> +<P> +<B>14.15</B> <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.) + +<P><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> + +<P> +<B>14.16</B> 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. + +<P>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? + +<P>(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.) + +<P> + +<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.<P> +<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.<P> +<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.<P> +<A NAME="ft4" HREF="recur-patterns.html#text4">[4]</A> Here's the higher-order function version, from Chapter 8: + +<P><PRE>(define (add-numbers sent) + (accumulate + (keep number? sent))) +</PRE> + +<P>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.<P> +<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").<P> +<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P> +<A HREF="../ssch13/convince-recur.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="number-name.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> |