[plt-scheme] Re: HTDP Exercise 12.4.2 ... Help!

On Apr 30, 2009, at 12:26 PM, Stephen wrote:

>   (cond ((empty? a-word) (list (list a-letter)))
>              (else
>                   ; a-letter                            
> symbol                      'x
>                   ; a-word                            
> los                              (list 'a 'b 'c 'd)
>                   ; (first a-word)                  
> symbol                      'a
>                   ; (rest a-word)                  
> los                             (list 'b 'c 'd)
>                   ; (insert-everywhere a-letter (rest a-word))     
> lolos (list (list 'x 'b 'c 'd) (list 'b 'x 'c 'd) (list 'b 'c 'x  
> 'd) (list 'b 'c 'd 'x))
>                   ; right answer                 lolos              
> (list (list 'x 'a 'b 'c 'd) (list 'a 'x 'b 'c 'd) (list 'a 'b 'x 'c  
> 'd) (list 'a 'b 'c 'x 'd) (list 'a 'b 'c ' d 'x))
>               )))
>
> In this example, how is the recursion (insert-everywhere a-letter  
> (rest a-word))  producing the result (list (list 'x 'b 'c 'd) (list  
> 'b 'x 'c 'd) (list 'b 'c 'x 'd) (list 'b 'c 'd 'x)). In other  
> words, this is stating that the value of (insert-everywhere a- 
> letter (rest a-word)) is (list (list 'x 'b 'c 'd) (list 'b 'x 'c  
> 'd) (list 'b 'c 'x 'd) (list 'b 'c 'd 'x)), which is correct, but  
> how does the function produce that result? Each time (insert- 
> everywhere a-letter (rest a-word)) is called, the word passed to  
> insert-everywhere is missing it's first letter, so eventually I'm  
> calling (insert-everywhere a-letter empty), which results in (list  
> (list a-letter)).

This is a common difficulty for people getting used to recursion:  
they try to think about how it works at every level simultaneously,  
and since there are potentially infinitely many levels, their brains  
aren't big enough to do that.  A much more effective way to think  
about recursion is to only worry about two levels at once: assume  
that the lower level works correctly, and figure out how to make the  
upper level work correctly too.

In other words, don't try to figure out HOW the recursion (insert- 
everywhere a-letter (rest a-word)) produces a correct answer; just  
assume that it does, and use that assumption to make (insert- 
everywhere a-letter a-word) also produce a correct answer.  If you  
can do that without assuming anything special about a-word, then

1) You already know that (insert-everywhere a-letter empty) works  
correctly.

2) Suppose a-word is length 1.  Since (rest a-word) is length 0, i.e.  
empty, and the function works correctly on that input, it must also  
work correctly for a-word... regardless of *which* length-1 list a- 
word is!  In other words, the function works correctly on all inputs  
of length 1.

3) Suppose a-word is length 2.  Since (rest a-word) is length 1, and  
we already showed that the function works correctly on all inputs of  
length 1, it must also work correctly for a-word... regardless of  
*which* length-2 list a-word is!  In other words, the function works  
correctly on all inputs of length 2.

And so on.  Eventually you conclude that no matter how long a-word  
is, the function works correctly on it.

Here's another way to think about it.  Suppose your program weren't  
always correct; then there must be at least one input on which it  
produces a wrong answer.  Of the (possibly many) inputs on which it's  
wrong, pick a SHORTEST one (e.g. if it were correct on all inputs of  
length up to 3, but not all of length 4, we would pick one of length  
4 on which it was wrong).  Plug in this "shortest bad input" as a- 
word.  Since (rest a-word) is shorter than a-word, it can't be a bad  
input, so the function must be correct on (rest a-word).  Use this  
fact to make the function correct on a-word as well.

If you understand this, and truly believe it in your heart, you've  
just learned mathematical induction.  I wrote a Ph.D. dissertation  
about mathematical induction, but EVERY competent mathematician can  
use mathematical induction as an essential tool of daily life, just  
as EVERY competent programmer can use recursion as an essential tool  
of daily life.

> So, for the example above:
>
> First time insert-everywhere is called:
> (insert-everywhere 'x (list 'a 'b 'c 'd)
>
> => (else ... 'x  ; a-letter
>                  'a  ; (first a-word)
>                  (list 'b 'c 'd) ; (rest a-word)
>                  (insert-everywhere 'x (list 'b 'c 'd)
>
> Second time insert-everywhere is called:

it produces (list (list 'x 'b 'c 'd) (list 'b 'x 'c 'd) (list 'b 'c  
'x 'd) (list 'b 'c 'd 'x)) .  Never mind how; just go on and design  
the rest of the function.




Stephen Bloch
sbloch at adelphi.edu