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

Yet another way to think about it, as a series of better-and-better  
versions of the function.  Each function will work correctly on all  
the cases that the previous one did, plus perhaps some more cases.

; insert-everywhere-0 : symbol los -> lolos
; Inserts the symbol in every possible place in the los.  Only works  
if the los is length 0.
(define (insert-everywhere-0 sym word)
    (list (list sym)))

; insert-everywhere-1 : symbol los -> lolos
; Inserts the symbol in every possible place in the los.  Only works  
if the los is length 0 or 1.
(define (insert-everywhere-1 sym word)
    (cond [(empty? word) (insert-everywhere-0 sym word)]
               [(cons? word)
                 ; sym                                      a symbol
                 ; word                                    an los of  
length 1
                 ; (first word)                          a symbol
                 ; (rest word)                          an los of  
length 0
                 ; (insert-everywhere-0 sym (rest  
word))                  must be correct, since (rest word) is length 0
		; figure out how to do this
		]))

; insert-everywhere-2 : symbol los -> lolos
; Inserts the symbol in every possible place in the los.  Only works  
if the los is length 0, 1, or 2.
(define (insert-everywhere-2 sym word)
    (cond [(empty? word) (insert-everywhere-0 sym word)]
               [(cons? word)
                 ; sym                                      a symbol
                 ; word                                    an los of  
length 1 or 2
                 ; (first word)                          a symbol
                 ; (rest word)                          an los of  
length 0 or 1
                 ; (insert-everywhere-1 sym (rest  
word))                  must be correct, since (rest word) is length  
0 or 1
		; figure out how to do this
		]))

You'll probably find that the definition of insert-everywhere-2 is  
almost identical to the definition of insert-everywhere-1, except  
that it calls (insert-everywhere-1 sym (rest word)) rather than  
(insert-everywhere-0 sym (rest word)).

Now, what would happen if insert-everywhere-1 called insert- 
everywhere-1 instead of insert-everywhere-0 on the rest?  The "insert- 
everywhere-1" function is at least as good as the "insert- 
everywhere-0" function.  (rest a-word) is empty, so insert- 
everywhere-0 would get it right, so insert-everywhere-1 must also get  
it right, so the resulting slightly-modified insert-everywhere-1  
function still works correctly on length-1 functions.

But now insert-everywhere-2 and insert-everywhere-1 are identical  
except for the name at the top.  So both functions must behave  
exactly the same way, i.e. they both produce correct answers on  
length-2 inputs, regardless of whether they're named "insert- 
everywhere-1" or "insert-everywhere-2".  Which means "insert- 
everywhere-1" actually works correctly on inputs of length up to 2,  
not just 1 as advertised.  Revise the contract.

Now, what would happen if you called insert-everywhere-1 on an input  
of length 3?  According to the (revised) contract, it's only  
guaranteed to work on inputs of length at most 2, but in fact it  
calls insert-everywhere-1 on an input of length 2, which we know  
works, and puts that together correctly into an answer to the  
original length-3 problem, so insert-everywhere-1 actually produces  
correct answers on inputs of length 3 as well.  Revise the contract.   
By the exact same reasoning, we can show that it works correctly on  
inputs of length 4, and then 5, and then 6....


Stephen Bloch
sbloch at adelphi.edu