[plt-scheme] HTDP 12.4.2

At 12:20 PM -0700 6/22/06, Danny Yoo wrote:
>Imagine for the moment that insertEverywhere is working, and imagine 
>us calling it on the test example.  Since the list isn't empty, 
>we'll be hitting the else body, and we're running into:
>
>      ... sym ... (first alow) ...
>      ... (insertEverywhere sym (rest alow)) ...
>
>We know that we want to get out:
>
>     (list (list 'd 'e 'r)
>           (list 'e 'd 'r)
>           (list 'e 'r 'd)
>           (list 'd 'r 'e)
>           (list 'r 'd 'e)
>           (list 'r 'e 'd))
>
>Again, putting on our "wishing" hat, let's look at the recursive 
>call to insertEverywhere.  What does it give us?
>
>     (insertEverywhere sym (rest alow))
>
>     ==>
>
>     (insertEverywhere 'd (rest (list (list 'e 'r)
>                                      (list 'r 'e))))
>
>     ==>
>
>     (insertEverywhere 'd (list (list 'r 'e)))
>
>     ==> (list (list 'd 'r 'e)
>               (list 'r 'd 'e)
>               (list 'r 'e 'd))
>
>(This would be a good test case to add to your test suite.)
>
>
>
>So, if we are holding onto:
>
>    (list (list 'd 'r 'e)
>          (list 'r 'd 'e)
>          (list 'r 'e 'd))
>
>and we want to mess with it enough so we get:
>
>     (list (list 'd 'e 'r)
>           (list 'e 'd 'r)
>           (list 'e 'r 'd)
>           (list 'd 'r 'e)
>           (list 'r 'd 'e)
>           (list 'r 'e 'd))
>
>do you see what the difference between what we're holding onto and 
>what we want is?  Can you give a concept or name to it?

Here's how I teach this approach in class.

We've already gotten used to writing function templates that list all 
the "interesting expressions" we're likely to need:

(define (insertEverywhere sym alow)
    sym
    alow
    (cond [(empty? alow) ...]
             [(cons? alow)
                (first alow)
                (rest alow)
                (insertEverywhere (rest alow))
              ]))

If this is enough to tell you how to write the program, great.  If 
not, we go to Plan B, the "template with types", in which we annotate 
each of the expressions in the template with its TYPE.  It may also 
be helpful at this point to add a line for "desired answer":

(define (insertEverywhere sym alow)
    sym                                                 a symbol
    alow                                                a list of 
words, i.e. a list of lists of symbols
    (cond [(empty? alow) ...]
             [(cons? alow)
                (first alow)                          a word, i.e. a 
list of symbols
                (rest alow)                          a list of words, 
i.e. a list of lists of symbols
                (insertEverywhere sym (rest alow)) a list of words, 
i.e. a list of lists of symbols
     desired answer                               a list of words, 
i.e. a list of lists of symbols
              ]))

If this gives you a brilliant idea, great.  If not, we go to Plan C, 
the "template with values".  Pick a MODERATELY COMPLICATED example 
(you've already written the examples, and at least one of them should 
be moderately complicated), and write down, next to each expression 
in the template, its value for that example.  So suppose we picked
(insertEverywhere 'd (list (list 'x) (list) (list 'y 'z)))
"should be" (list (list 'd 'x) (list 'x 'd) (list 'd) (list 'd 'y 'z) 
(list 'y 'd 'z) (list 'y 'z 'd))
The template would become

(define (insertEverywhere sym alow)
    sym                                   a symbol:                  'd
    alow                                  a list of words: 
(list (list 'x) (list) (list 'y 'z))
    (cond [(empty? alow) ...]
             [(cons? alow)
                (first alow)           a word:                      (list 'x)
                (rest alow)            a list of words:          (list 
(list) (list 'y 'z))
                (insertEverywhere sym (rest alow)) a list of words: 
(list (list 'd) (list 'd 'y 'z) (list 'y 'd 'z) (list 'y 'z 'd))
     desired answer                 a list of words:    (list (list 'd 
'x) (list 'x 'd) (list 'd) (list 'd 'y 'z) (list 'y 'd 'z) (list 'y 
'z 'd))
              ]))

Now, compare the "desired answer" with the various expressions you've 
got available on the preceding lines.  95% of the time, the recursive 
call will give you most of the right answer, and you just have to 
identify what needs to be added to it to get the complete right 
answer.

This approach will serve you well not only for this function but for 
"intersperse", and any other auxiliary functions you may need.

Note the importance of picking a NON-TRIVIAL example: if you pick an 
example that's too simple, the pattern-recognition circuits in your 
brain don't have an opportunity to kick in and spot what parts of the 
"desired answer" match what available expressions.  Likewise, the 
fact that the example wasn't a "special case" (in which all the input 
words were anagrams of one another) makes it easier for the 
pattern-recognition circuits to do their job.
For example, if you picked

(insertEverywhere 'd (list (list 'x)))
"should be" (list (list 'd 'x) (list 'x 'd))

as your example, the template with values would be only

(define (insertEverywhere sym alow)
    sym                                   a symbol:                  'd
    alow                                  a list of words: 
(list (list 'x))
    (cond [(empty? alow) ...]
             [(cons? alow)
                (first alow)           a word:                      (list 'x)
                (rest alow)            a list of words:          empty
                (insertEverywhere sym (rest alow)) a list of words:  empty
     desired answer                 a list of words:    (list (list 'd 
'x) (list 'x 'd))
              ]))

which isn't nearly as informative.


In my classroom experience, this "template with values" strategy can 
be helpful in many settings, but it's MOST helpful in writing 
functions that return lists or other self-referential data structures.

-- 
					Stephen Bloch
					sbloch at adelphi.edu