[plt-scheme] HtDP newbie question, 12.4.2

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Sat Mar 29 00:03:57 EDT 2008

On Mar 28, 2008, at 9:03 PM, Cooke Kelsey wrote:

> Here's an answer to your question:
> Q: "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?"


Look at the table for a call to insert-everywhere/one-word with 'X  
and (list 'A 'T). <<--- original call

  If you now recursively call

  * (insert-everywhere/one-word s (rest word)) and get
    (list (list 'X 'T)
           (list 'T 'X))

and then you call

  *  (add-letter-to-all (first word) ... the above ..) you get
      (list (list 'A 'X 'T)
             (list 'A 'T 'X))

What do you want for the result of the original call?
How can you add this to what you have so far?
(10 keystrokes)

That's the question I raise. -- Matthias

> A: What's missing is the second letter, the third, etc.
> That is, I can add "W" to a list:
>  (list 'w 'x 'a 't 'e 'r)
>  (list 'w 'x 't 'e 'r)
>  (list 'w 'x 'e 'r)
>  (list 'w 'x 'r))
> But I also need "A" "T" E" "R" to be added, incrementally:
>  (list 'w 'x 'a 't 'e 'r)
>  (list 'w 'a 'x 't 'e 'r)
>  (list 'w 'a 't 'x 'e 'r)
>  (list 'w 'a 't 'e 'x 'r)
> Mark suggested that I look carefully at the table and see how I can  
> "rearrange" the items in the columns to produce the result.   
> Everyone seems to suggest that the answer is found in that table,  
> so I have been copying it and drawing arrows between the letters.
> At this point the solution seems to be to create a second shrinking  
> list of (rest words), flip it around backwards and then merge it  
> into the original list.  I've written some functions to attempt  
> this, but nothing near the expected result.
> Marco has suggested that my entire approach is wrong, that I should  
> build words correctly from the beginning instead of adding missing  
> letters.
> I'm going to begin again from scratch and pay closer attention to  
> the template and contracts.
> Matthias Felleisen <matthias at ccs.neu.edu> wrote:
> Why did you throw away your progress (add-first-letter)?
> Why did you not answer my second question?
> (I'll give you that much: with the two you are about 10 keystrokes  
> from the answer.)
> I am getting the feeling your jumping again.
> ;; ---
> Let's step back a bit. The purpose of this extended exercise is to  
> practice the two ideas that the book has introduced at that point:
> 1. that the design recipe works on a per function basis -- BUT YOU  
> 2. that the 'wish list' works -- BUT YOU NEED TO STICK TO IT.  (If  
> you are systematic about this, you just never forget where in the  
> problem you are.)
> ;; ---
> Another step back:
> 1. In case you're wondering:  most people would consider this  
> exercise way beyond a first-semester exercise. (It was on my MS  
> exam in 1981.)
> 2. HtDP/2e will use a simpler exercise than that and push back  
> Arrangements until students have more practice. A lot of people  
> have problems with it though in 1-1 meetings, it's much easier to  
> tease out the answers to these questions because the speed is  
> higher and less frustrating.
> -- Matthias
> On Mar 28, 2008, at 5:35 PM, Cooke Kelsey wrote:
>> 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?
> You rock. That's why Blockbuster's offering you one month of  
> Blockbuster Total Access, No Cost.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20080329/27d3d849/attachment.html>

Posted on the users mailing list.