[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