[plt-scheme] HtDP newbie question, 12.4.2

Dear Matthias / Marco,
   
  I read Marco's suggestions.  It was very helpful to read through the whole problem again in clear English and remember how I got to the function "insert-in-single-word."  I think I am near to the answer.
   
  You both ask me a similar question:

  (1) Matthias:  Can you design a function that adds a letter (no matter what it is) to the front of all these words you have gotten back?...DONE? After that: what is missing? 
   
     given:          the recursion                           in the final result I want                     
    'X   "ATE"     "X" "TE" --> "XTE" "TXE" "TEX"     "AXTE" "ATXE" "ATXE" "ATEX"           

  (2) Marco: "Here is where I believe you are really stuck. It is easy to see one member of the result: (letter a-word). This puts letter before the first letter of a-word. Is that the only place it can go? No, it can go before any of the letters in a word and at the end of a-word. How do you insert a letter everywhere in (rest a-word)? Once you have this list (call it R) all you need is to do something with (first a-word).  Where does it have to go in each of R?"

   
  OK, here is a function which I think answers these questions:
   
  (define (add-letter-to-recursive-list letter a-word)
  (cond
    [(empty? (rest a-word)) (cons (list letter (first a-word)) empty)]
    [else (cons (cons letter a-word) (add-letter-to-recursive-list letter (rest a-word)))]))
   
  ;example:
  (add-letter-to-recursive-list 'x (list 'w 'a 't 'e 'r))
  ;answer
  (list
 (list 'x 'w 'a 't 'e 'r)
 (list 'x 'a 't 'e 'r)
 (list 'x 't 'e 'r)
 (list 'x 'e 'r)
 (list 'x 'r))
  
Then next question is, how can I put the missing letters back on the front of these words?  
   
  For this, I can use the "add-first-letter" function which I sent earlier to Matthias:
   
  (define (add-first-letter first-letter low)
  (cond 
    [(empty? (rest low)) (cons (append (list first-letter) (first low)) empty)]
    [else (cons (append (list first-letter) (first low)) (add-first-letter first-letter (rest low)))]))
   
  Now, I can combine the two functions into a main function, "add-letter-plus-prefix":
   
  (define (add-letter-plus-prefix x a-word)
  (add-first-letter (first a-word) (Rest x a-word)))
   
  ;example:
  (add-letter-plus-prefix 'x (list 'w 'a 't 'e 'r))
  ;answer:
  (list
 (list 'w 'x 'w 'a 't 'e 'r)
 (list 'w 'x 'a 't 'e 'r)
 (list 'w 'x 't 'e 'r)
 (list 'w 'x 'e 'r)
 (list 'w 'x 'r))
   
  It looks nice, but the word is still shrinking away.  I have simply added the first letter to the beginning of all the words.  My problem is still, how can I increment the prefix in order: 'w, 'a, 't, 'e, 'r?  
   
  At this point, I think my problem is too many levels of abstraction.  I think that you all can see the answer very clearly, but I can't visualize multiple recursive functions.  The tables, etc have been extremely helpful for me to develop the individual functions.  As far as the final solution, perhaps I don't have the ability to "see" it on that level of abstraction?
   
  Matthias Felleisen <matthias at ccs.neu.edu> wrote:
  
  On Mar 28, 2008, at 1:24 PM, Cooke Kelsey wrote:
    Oh right, in order to include all the words I need more than an append.  Here's a function that adds a letter to ALL the words:
  
(define (add-first-letter first-letter low)
  (cond 
    [(empty? (rest low)) (list (cons first-letter low))]
    [else (cons (cons first-letter (list (first low))) (add-first-letter first-letter (rest low)))]))

  ;example:
(add-first-letter 'X (list 'A 'T 'E 'Y 'W 'Z))   ;result:
  (list (list 'X 'A) (list 'X 'T) (list 'X 'E) (list 'X 'Y) (list 'X 'W) (list 'X 'Z))
  

  

  So if you apply add-first-letter to (first word) and the result of (insert-everywhere/in-one-word (rest word)), you get back all but one of the word you want.  Which brings me to the second question: 
  


     That was a lot more complicated than I thought.  I guess that should be a helper function. 
   
  However, when I try to make a main function (insert-in-single-word) that calls add-first-letter, I end up going around in the same circle as before.
  

  

  Because you failed to read and answer my second question. -- Matthias
  

  

  

  


    
Matthias Felleisen <matthias at ccs.neu.edu> wrote:
  
  On Mar 28, 2008, at 12:34 PM, Cooke Kelsey wrote:
    OK, here's a simple function that adds a letter to a word:
   
  (define (add-first-letter first-letter word)
  (append (list first-letter) word))
  

  

  That's not what I asked you to _design_.  Please read the suggestion carefully. And again, (append (list foo) bar) is equal to (cons foo bar). Why do yu keep using append? 
  

  


    (add-first-letter 'A (list 'X 'T 'E))=(list 'A 'X 'T 'E')

  So my question is, where does (list 'A 'T 'E) come from? 
  

  It is your sample input to the function. It says "Given" in that column. 
  


    In your table below, you say "the recursion: "X" "TE" --> "XTE" "TXE" "TEX".  Actually I have never been able to create such a recursion.  That's the big mystery to me. 
  

  

  The purpose statement of the function tells you what the recursive call should produce. So when you code, you may assume that the recursive call works properly.
  

  

    
  

  I just read Dave Yrueta's encouraging note, and he says I need to focus on your hint about adding 'A to the list, "in the simplest and most natural way."  Well, all I can think of is to append it, like I did above.  But there is no recursive element, and I cannot call it or plug it into the main recursive function.  It is floating out in space.
  
Matthias Felleisen <matthias at ccs.neu.edu> wrote:
    

  Okay you have gotten to the point where you're jumping even faster. Slogan: 
  

   furiously fast programming leads to nowhere. 
  

  ;; --- 
  

  All I was getting at is a simple point: 
  

  Your recursive calls in insert-everywhere/one-word produced almost all the work in the recursion. Indeed, it always produces all but one word, except that the first letter from the original word is missing. Example: 
  

     given:          the recursion                           in the final result I want                    plus 
    'X   "ATE"     "X" "TE" --> "XTE" "TXE" "TEX"     "AXTE" "ATXE" "ATXE" "ATEX"           "XATE" 
  

  Given the recursive result (the list of words that are too short by the first letter in the orginal word) can you design a function that adds this letter (no matter what it is) to the front of all these words you have gotten back? 
  

  DONE? 
  

  After that: what is missing? 
  

  -- Matthias
  

  

  

  


  On Mar 28, 2008, at 11:51 AM, Cooke Kelsey wrote:
    OK, that helps me a little.  If I insert "cons (first word)," then I can rebuild the word:
   
  (define (cons-function word)
  (cond
    [(empty? (rest word)) word]
    [else (cons (first word) (cons-function (rest word)))]))
   
  (cons-function (list 'A 'T 'W)) = (list 'A 'T 'W)
   
  The problem is how to add this to a shrinking function:
   
  (define (shrinking-function s word)
  (cond
    [(empty? (rest word)) empty]
    [else (list (append (list s) word) (shrinking-function s (rest word)))]))

  (This shrinking function isn't exactly what I want, but at least it gives me (list 'X 'A 'T 'W) and (list 'X 'T 'W)).
   
  So I append them together: 
   
  (append (cons-function (list 'A 'T 'W)) (shrinking-function 'X (list 'A 'T 'W)))
   
  And I get this:
   
  (list (list 'X 'A 'T 'W) (list (list 'X 'T 'W) empty)) (list 'A 'T 'W (list 'X 'A 'T 'W) (list (list 'X 'T 'W) empty))
   
  Garbage!
   
  As a last resort, I try to combine cons and shrinking functions together:
   
  (define (cons+shrinking-function s word)
  (cond
    [(empty? (rest word)) word]
    [else (append (cons (first word) (cons+shrinking-function 'X (rest word))) (list s) (rest word))]))
   
  (cons+shrinking-function 'X (list 'A 'T 'W)) = (list 'A 'T 'W 'X 'W 'X 'T 'W)
   
  It looks kind of nice, but it is even further from the expected result.
   
  
Matthias Felleisen <matthias at ccs.neu.edu> wrote:
    

  How about (cons 'A (list 'X 'T)) = (list 'A 'X 'T)
  

  

  


  On Mar 28, 2008, at 10:53 AM, Cooke Kelsey wrote:
  (append (list 'A) (list 'X 'T)) = (list 'A 'X 'T)

Matthias Felleisen <matthias at ccs.neu.edu> wrote:     

  Here is a definition of 'adding in the missing element': 
  

  * If a list X misses the symbol 'A (at the front), how do you get a list that has the 'A and all of X? 
  

  * X = (list 'X 'T) and 'A --> I want (list 'A 'X 'T). How do I do that? 
  

  -- Matthias
  

  

  
---------------------------------
  Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now.


  

  
---------------------------------
  Never miss a thing. Make Yahoo your homepage.


  

  
---------------------------------
  Never miss a thing. Make Yahoo your homepage.


  

  
---------------------------------
  Looking for last minute shopping deals? Find them fast with Yahoo! Search.



       
---------------------------------
Special deal for Yahoo! users & friends - No Cost. Get a month of Blockbuster Total Access now
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20080328/9d7fc70a/attachment.html>