js/magic-bird/imgs/extracted-1688-map/MapPartsWhite/hills_white/35.png

<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>&gt; (disjoint-pairs 'tripoli)                  ;; the new problem
(TR IP OL I)

&gt; (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)))))

&gt; (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) &quot;&quot;)
        ((vowel? (first wd))
         (word (first wd) (keep-vowels (bf wd))))
        (else (keep-vowels (bf wd)))))

&gt; (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>&gt; (doubles 'bookkeeper)
OOKKEE

&gt; (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) &quot;&quot;)
        ((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)
      &quot;"
      (word (first sent) (scrunch-words (bf sent)))))

&gt; (addup '(8 3 6 1 10))
28

&gt; (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)))))

&gt; (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))))

&gt; (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 &quot;real&quot; 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) &quot;&quot;)
	((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>&gt; (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>&gt; (sent-before? '(hold me tight) '(sun king))
#T

&gt; (sent-before? '(lovely rita) '(love you to))
#F

&gt; (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>&gt; (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>&nbsp;&nbsp;<PRE>&gt; (<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>&nbsp;&nbsp;<PRE>&gt; (<A NAME="g26"></A>up 'town)
(T TO TOW TOWN)
</PRE>

<P>
<B>14.3</B>&nbsp;&nbsp;<PRE>&gt; (<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>&nbsp;&nbsp;<PRE>&gt; (<A NAME="g28"></A>odds '(i lost my little girl))
(I MY GIRL)
</PRE><A NAME="exodds"></A>

<P>
<B>14.5</B>&nbsp;&nbsp;[<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>&gt; (letter-count '(fixing a hole))
11
</PRE>

<P>
<B>14.6</B>&nbsp;&nbsp;Write <CODE>member?</CODE>.


<P>
<B>14.7</B>&nbsp;&nbsp;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>&gt; (<A NAME="g30"></A>differences '(4 23 9 87 6 12))
(19 -14 78 -81 6)
</PRE>

<P>
<B>14.8</B>&nbsp;&nbsp;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>&gt; (expand '(4 calling birds 3 french hens))
(CALLING CALLING CALLING CALLING BIRDS FRENCH FRENCH FRENCH HENS)

&gt; (expand '(the 7 samurai))
(THE SAMURAI SAMURAI SAMURAI SAMURAI SAMURAI SAMURAI SAMURAI)
</PRE>

<P>
<B>14.9</B>&nbsp;&nbsp;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>&gt; (location 'me '(you never give me your money))
4
</PRE>

<P>
<B>14.10</B>&nbsp;&nbsp;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>&gt; (count-adjacent-duplicates '(y a b b a d a b b a d o o))
3

&gt; (count-adjacent-duplicates '(yeah yeah yeah))
2
</PRE>

<P>
<B>14.11</B>&nbsp;&nbsp;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>&gt; (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)

&gt; (remove-adjacent-duplicates '(yeah yeah yeah))
(YEAH)
</PRE>

<P>
<B>14.12</B>&nbsp;&nbsp;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>&gt; (progressive-squares? '(3 9 81 6561))
#T

&gt; (progressive-squares? '(25 36 49 64))
#F
</PRE>

<P>
<B>14.13</B>&nbsp;&nbsp;What does the <CODE>pigl</CODE> procedure from Chapter 11 do if you invoke
it with a word like &quot;frzzmlpt&quot; that has no vowels?  Fix it so that it
returns &quot;frzzmlptay.&quot;


<P>
<B>14.14</B>&nbsp;&nbsp;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>&gt; (same-shape? '(the fool on the hill) '(you like me too much))
#T

&gt; (same-shape? '(the fool on the hill) '(and your bird can sing))
#F
</PRE>


<P>
<P>
<B>14.15</B>&nbsp;&nbsp;<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>&gt; (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>&nbsp;&nbsp;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
&quot;soaring,&quot; the group &quot;oa&quot; represents one syllable and the vowel &quot;i&quot;
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 &quot;e&quot;s that don't create a syllable (&quot;like&quot;), consecutive vowels
that don't form a diphthong (&quot;cooperate&quot;), letters like &quot;y&quot; 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 &minus;&infin;, 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, &quot;a c&quot; is
treated as if it were &quot;ac&quot; and comes after &quot;ab&quot;; by our rule, &quot;a c&quot;
comes before &quot;ab&quot; because we compare the first words (&quot;a&quot; and &quot;ab&quot;).<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>
ofs	hex dump	ascii
0000	89 50 4e 47 0d 0a 1a 0a 00 00 00 0d 49 48 44 52 00 00 00 45 00 00 00 15 08 06 00 00 00 10 03 23	.PNG........IHDR...E...........#
0020	de 00 00 03 ad 49 44 41 54 78 da ed 98 0b 48 54 51 10 86 35 93 d4 24 53 4a 48 09 31 31 51 29 4a	.....IDATx....HTQ..5..$SJH.11Q)J
0040	0a 62 95 a2 50 0a 43 29 8a 48 02 a1 28 c2 28 94 08 02 71 51 0c 51 0c 31 14 51 90 15 51 12 a5 08	.b..P.C).H..(.(...qQ.Q.1.Q..Q...
0060	45 29 8c c2 28 12 a3 20 2a 8a 22 a2 a2 20 91 20 29 4c e9 a1 fd 03 df c2 b2 68 90 9a ad e1 85 8f	E)..(...*.".....)L.......h......
0080	fb dc 73 ef cc 99 f9 67 ce fa f9 2d 6c be bb 4d 4c 4c 1c 15 57 c5 03 d1 21 ca c4 41 91 f0 3f 1a	..s....g...-l..MLL..W...!..A..?.
00a0	bb 4c 04 fe e6 7e 9c 28 11 f7 c4 a8 f8 29 46 c4 a0 78 24 ba 45 0d 9c 10 91 f3 d9 19 49 18 5b 20	.L...~.(.....)F..x$.E.......I.[.
00c0	0e 88 54 b1 46 6c 14 db c5 16 b1 4f 54 88 3e d1 cc 7e 48 8c e3 98 cf e2 8b 78 2f be 89 61 d1 32	..T.Fl.....OT.>..~H......x/..a.2
00e0	af a2 07 83 8f 31 bb c3 18 72 51 9c 16 67 44 9e b8 23 7e 88 4f ec ab bd c6 28 c0 29 57 44 13 7b	.....1...rQ..gD..#~.O....(.)WD.{
0100	a7 78 c9 f5 71 a2 a9 41 2c ff d7 06 2f 12 21 1c 87 8b 14 66 ba 4a d4 c1 05 91 c8 fd 48 11 35 c9	.x..q..A,.../.!....f.J......H.5.
0120	38 b1 22 5d 84 89 f5 96 5e 93 44 98 19 fd 50 f4 88 76 a2 e9 b2 b8 21 3a 89 a2 0f 9c 77 89 73 62	8."]....^.D...P..v....!:....w.sb
0140	87 58 2c 02 e6 c2 19 16 e6 81 c2 1f 7d 48 22 b7 ab 85 0b 67 14 21 94 59 b3 f0 be 44 a2 e1 15 46	.X,.........}H"....g.!.Y...D...F
0160	b7 43 13 d1 61 dc 17 4f 10 65 73 5e bf 68 13 85 a2 54 9c 62 c2 32 60 a7 d8 2d b2 c5 26 de 91 ca	.C..a..O.es^.h...T.b.2`..-..&...
0180	f1 66 f6 31 7f 22 92 96 12 bb 44 a6 38 29 6e 8b 01 c2 3a df 66 67 96 27 e1 08 69 f7 4c 5c a3 12	.f.1."....D.8)n...:.fg.'..i.L\..
01a0	0d b0 6f 22 32 6c 22 ca 99 0c fb 86 46 d2 f2 8d f8 2a c6 c0 ad 43 43 30 ca 33 2f b8 67 cf 7c e7	..o"2l".....F....*...CC0.3/.g.\|.
01c0	d8 44 3d db d7 f4 68 39 c6 3e 25 1a ba e1 92 b8 4e 2a b5 8a f3 38 a4 92 74 ad 23 92 1a 89 94 12	.D=...h9.>%.....N*...8..t.#.....
01e0	9c 75 16 b2 84 83 f4 2a e6 be 93 94 7c 8e b6 0d f2 5e 8b bc 06 5f 73 4c 33 33 6b 86 d6 63 a8 45	.u.....*....\|....^..._sL33k..c.E
0200	47 ad 47 ea 54 e1 8c 16 0f 11 df 2b b6 92 0a 1b 88 6e 3b cf 21 35 a2 44 04 29 63 3a 16 cd 79 82	G.G.T......+.....n;.!5.D.)c:..y.
0220	58 87 24 c4 91 56 ab a7 f3 e1 c1 7f d1 29 2e 66 ae 0d cd aa c4 09 c5 cc 6c 3d d1 e2 e2 19 3b 3e	X.$..V.......).f........l=....;>
0240	2e e2 89 34 33 7e a5 58 2a 42 b9 be c2 f4 90 f1 97 cc a7 52 6e d5 6a 3f c2 fa 96 94 69 c6 21 4e	...43~.X*B.........Rn.j?....i.!N
0260	1c 54 87 23 ee 78 a4 51 19 0e 32 bd 8b b1 59 b6 d9 fe d7 c6 04 79 9d 87 4d 63 0c 07 d5 a4 0f f1	.T.#.x.Q..2...Y......y..Mc......
0280	76 79 a4 47 1f 02 d8 85 63 2a b8 df 4a 89 ee 41 8c ad ff 89 65 bc e8 e9 7c 87 4f 38 d0 e3 7a 09	vy.G....c*..J..A....e...\|.O8..z.
02a0	4d 5c 27 02 ea c4 29 76 7e 8b f6 bf 1f b1 b5 f4 39 4c f9 2f e6 39 6b f6 72 d1 8b 48 52 26 68 2e	M\'...)v~.......9L./.9k.r..HR&h.
02c0	d7 30 89 33 f8 7d 1a 8d 5b 80 c7 b5 08 44 74 0c fd 70 92 32 ad 38 a1 13 a1 bd 41 59 6e a4 6f 72	.0.3.}..[....Dt..p.2.8....AYn.or
02e0	2f 15 32 d0 92 64 84 d5 e1 8e 98 99 1a 9b 43 dd b6 86 2c dc ab 69 db e6 d5 7e db 1a e4 b1 95 37	/.2..d........C...,..i...~.....7
0300	af 31 4a 27 69 d7 ad bb 7c 4d 23 95 ca f8 d6 68 bd 33 bd f0 4a 1f 77 bf 30 c2 6f 6e 52 8e af 92	.1J'i...\|M#....h.3..J.w.0.onR...
0320	26 b9 44 c0 5a 96 11 f6 be 43 b3 e2 80 29 9c 12 ca 8b d2 3d ca da 2a 4a 55 36 a1 9a 40 29 cb e0	&.D.Z....C...).....=..*JU6..@)..
0340	03 6b 08 e5 7c 66 bf 1c 43 ea e8 24 e3 79 de 34 e1 2e 33 9f 8f 63 fb 59 e8 75 f0 be 64 16 8c 55	.k..\|f..C..$.y.4..3..c.Y.u..d..U
0360	e8 87 7b 21 f8 91 ae b5 97 df 14 f1 7e 07 a5 33 70 2e d2 c3 1f 91 4a a1 6e 07 a3 e6 59 de b5 9b	..{!........~..3p.....J.n...Y...
0380	ff 39 6a 31 24 89 48 c8 c3 51 05 b4 d4 69 38 bb 16 67 59 c4 ec c1 81 3d a4 82 75 af f1 6e 91 66	.9j1$.H..Q...i8..gY....=..u..n.f
03a0	f6 9b 11 cf 5e aa 90 8b 7d 21 ed 7a dc 7c fd db 20 8c 66 28 8c f3 10 1c 60 ce c9 f4 14 5f eb 2b	....^...}!.z.\|....f(....`...._.+
03c0	a6 18 23 80 68 cd f4 ea 7a 13 fd 16 b6 85 cd 27 b6 5f 43 93 fa 78 20 bd 7e 68 00 00 00 00 49 45	..#.h...z......'._C..x..~h....IE
03e0	4e 44 ae 42 60 82	ND.B`.