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

 From: Stephen Bloch (sbloch at adelphi.edu) Date: Thu Apr 30 14:32:49 EDT 2009 Previous message: [plt-scheme] Re: HTDP Exercise 12.4.2 ... Help! Next message: [plt-scheme] Scribble eval contract violation examples Messages sorted by: [date] [thread] [subject] [author]

```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