[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