[plt-scheme] HTDP 12.4.2

if

(define (interperse sym word)
  (cond
    [(empty? word) (list sym)]
    [else (cons (cons sym  word)
                (interperse sym (rest word)))]
    )
  )

(interperse 'f (list 'd 'a 'r 'k))

gives

(list (list 'f 'd 'a 'r 'k) (list 'f 'a 'r 'k) (list 'f 'r 'k) (list 'f 'k) 
'f)

and I want

(list (list 'f 'd 'a 'r 'k) (list 'd 'f 'a 'r 'k) (list 'd 'a 'f 'r 'k) 
(list 'd 'a 'r 'f 'k) (list 'd 'a 'r 'k 'f))

I need to add

(list)
(list 'd)
(list 'd 'a)
(list 'd 'a 'r)
(list 'd 'a 'r 'k)

to what I have

(is this your cute idea Danny).

Now if  I reverse the order of interperses output like this

(define (interperse sym word)
  (cond
    [(empty? word) (list sym)]
    [else (append
                (interperse sym (rest word))
                (list (cons sym  word)))]
    )
  )

I get

(list 'f (list 'f 'k) (list 'f 'r 'k) (list 'f 'a 'r 'k) (list 'f 'd 'a 'r 
'k))

which means I have to reverse the order of what I have to add to get what I 
want.

(list 'd 'a 'r 'k)
(list 'd 'a 'r)
(list 'd 'a)
(list 'd)
(list)

which of course is just word and then (rest word) which would seem easier to 
add (except I haven't figured out quite how to do it).

Is this your cute idea Danny?



----Original Message Follows----
From: Stephen Bloch <sbloch at adelphi.edu>
To: Danny Yoo <dyoo at hkn.eecs.berkeley.edu>, wooks wooks <wookiz at hotmail.com>
CC: plt-scheme at list.cs.brown.edu
Subject: Re: [plt-scheme] HTDP 12.4.2
Date: Fri, 23 Jun 2006 09:47:22 -0400

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