[plt-scheme] HtDP newbie question, 12.4.2

From: Cooke Kelsey (cookekelsey at yahoo.com)
Date: Thu Mar 27 22:04:29 EDT 2008

Hi, I think I see what you are driving at.  I made tables with the word "ATW" as you suggested, on a piece of paper, and drew arrows to show how the values are passed down.  It helped me to see how each cycle gives me the next words in the list, minus missing letters.  
   
  When you say this:
   
  "From ROW 1: you get a list of TWO words ("XT" "TX") back from the recursive call. But you want THREE and the words are missing the letter A, the first of the current (****) word. The word that is missing is "XAT" which is the old (*****) word prefixed with X, the letter to be inserted."
   
  ...it seems to require a sort of register to save the current prefix, using the successive first letters of the "current" word ("let Z = 'A"), and each cycle increments the register ("let Z='A 'T"  "let Z='A'T'W) which I then append to the symbol and the shrinking (rest word).  
   
  I thought of your reminder to use helper functions, e.g. "add-prefix," but I keep going back to this register idea.  I don't know whether I am getting off track or what.

Matthias Felleisen <matthias at ccs.neu.edu> wrote:
  
  On Mar 27, 2008, at 6:22 PM, Cooke Kelsey wrote:
    Hi, I've made some progress but no jackpot yet...
  

This is huge progress.  Let's roll this up backwards: (see numbers)
  

  
    Here are the tables with all of the values, as you suggested:
   
  First Table: 
  

  ROW 1:

       
   s   |   word  |   (first word)  |  (insert-in-single-word s (rest word)) | expected result for (insert-... s low)
  --------------------------------------------------------------------------------------------------------
   'X   |(list 'A 'T)|     'A          |  (list (list 'X 'T) (list 'T 'X)) |   (list (list 'X 'A 'T) (list 'A 'X 'T) (list 'A 'T 'X))
   
  Table for Recursive Case:
  

  ROW 2: 

    
   
     s   |   word  |   (first word)  |  (insert-in-single-word s (rest word)) | expected result for (insert-... s low)
  --------------------------------------------------------------------------------------------------------
   'X   |(list 'T)|     'T          |  (list 'X) |   (list (list 'X 'T) (list 'T 'X))

   
  

  

  From ROW 2: you get a list of ONE word ("X") back from the recursive call. But you want TWO words altogether and the word is missing the letter T, the first of the current word.  The word that is missing is "XT" which is the old word prefixed with X, the letter to be inserted. 
  

  From ROW 1: you get a list of TWO words ("XT" "TX") back from the recursive call. But you want THREE and the words are missing the letter A, the first of the current word. The word that is missing is "XAT" which is the old word prefixed with X, the letter to be inserted. 
  

    After examining the tables, I tried a couple of new ways to get the results in the last column. 
  

Do my descriptions help? If not, try the following input: "ATT". What is the expected result? What is first? What's the recursive result? Etc. 
  

  Perhaps you also want to think about how the words you get back from the recursion go into the final result. 
  

  ;; --- 
  

  Don't try to code it up. Try to think it through first and come up with a description of WHAT has to happen to combine all these values properly. THEN turn this into a function with the design recipe. 
  

  -- Matthias
  

  

  
  

  

  

  

  

  

  

  

  

  

  

  

  


    
   
  The easiest way was simply to append the letters in order, so that X, AT-->XAT, AXT ATX 
   
  (define (insert-in-single-word2 s word)
(list (append (list s) word) (append word (list s)) (append (list (first word)) (list s) (rest word))))
   
  This doesn't have any recursive part, so it only works on 3 letter words.
   
  When I tried to insert a recursive part, no matter how I arranged the parts, I always lost letters.  
   
  For instance, the definition below results in: X,AT-->XAT, ATX, X
   
  (define (insert-in-single-word s word)
  (cond
    [(empty? (rest word)) empty]
    [else (list (append (list s) word) (append word (list s)) (append (list s) (insert-in-single-word s (rest word))))]))

  

Matthias Felleisen <matthias at ccs.neu.edu> wrote:
    
On Mar 27, 2008, at 3:15 PM, Cooke Kelsey wrote:

> (1) At this point it becomes critical to spell out the (list ...) 
> stuff, i.e., to turn the example into full-fledged Scheme data. 
> Small step.
>
> (.......which Scheme displays as (cons (cons 'X (cons 'A (cons 'T 
> empty))) (cons (cons 'A (cons 'X (cons 'T empty))) (cons (cons 'A 
> (cons 'T (cons 'X empty))) empty)))....)

I recommend raising the language level to Beginner with List ..


> (4) And before you complete the template build a table just like 
> the one above for the recursive case.
>
> First Table:
>
> s | word | (first word) | (insert-in-single-word s (rest 
> word)) | expected result for (insert-... s low)
> ---------------------------------------------------------------------- 
> ----------------------------------
> 'X |(list 'A 'T)| 'A | (insert-in-single-word s 
> (list 'T) | (list (list 'X 'A 'T) (list 'A 'X 'T) (list 'A 'T 'X))


What is the VALUE of (insert-in-single-word s (list 'T) ) ? The 
purpose statement tells you!
   
  

> Table for Recursive Case:
>
> s | word | (first word) | (insert-in-single-word s (rest 
> word)) | expected result for (insert-... s low)
> ---------------------------------------------------------------------- 
> ----------------------------------
> 'X |(list 'T)| 'T | (insert-in-single-word s empty 
> | (list (list 'X 'T) (list 'T 'X))

What is the VALUE of (insert-in-single-word 'X empty) ? The purpose 
statement tells you!
   
  
> I feel I am getting closer to the answer. The second table 
> suggest to me that there is something about recurring down to 2 
> letters and then appending the rest on.....except that I lost the 
> rest of the letters.

Almost! You need to actually determine the value of these expressions 
not just write down the expressions to make the leap. You're almost 
there.

And don't forget: if the leap is to large, you may need yet another 
helper function.

-- Matthias





  

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



       
---------------------------------
Never miss a thing.   Make Yahoo your homepage.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20080327/e4f03103/attachment.html>

Posted on the users mailing list.