[plt-scheme] HTDP 12.4.2

From: Danny Yoo (dyoo at hkn.eecs.berkeley.edu)
Date: Thu Jun 22 15:20:57 EDT 2006

> ;(define (insertEverywhere sym alow)
> ;  (cond
> ;    [(empty? alow) ...sym....]
> ;    [else ...sym...(first (first alow)) .....
> ;          ..sym....(rest (first alow)) .....
> ;          .....(insertEverywhere sym (rest alow)).....]
> ;   )
> ;)

Hi Wooks Wooks,

Very close!  In a template for a situation like this, we just need to 
enumerate the cases for alow --- we don't have to go any deeper.  That is:

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

This template should help out a bit in hinting us toward the real body of 
insertEverywhere.  We can go into detail why it helps, if you'd like:

At the moment, we have a single test case for insertEverywhere.  I'll 
translate it so it uses lists rather that cons just for notational ease.

     (insertEverywhere 'd
       (list (list 'e 'r)
             (list 'r 'e)))

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?

Best of wishes!

Posted on the users mailing list.