[plt-scheme] HtDP newbie question, 12.4.2

From: Cooke Kelsey (cookekelsey at yahoo.com)
Date: Sun Mar 30 02:07:28 EDT 2008

  Hi, I just want to thank Marco, Mark, Dave, and especially Matthias for helping me out.  I can’t believe how patient you were.
  In case you encounter another hard-headed student like me, the following is what I was thinking when you were trying to help me, and how I finally figured it out.  I hope I don’t offend anyone.  It’s not pretty, but this is what it is like for someone who really doesn’t have a clue
  Me:  Hi, I am stumped by 12.4.2
  Matthias: Let's try what HtDP/2e will introduce: Please make a table
  Me: OK, inputs and outputs.  Huh?  What is this 4th column: Result of Recursion (rest word)?!  Where in the world did this come from?! 
.Whatever, forget the table, I’ll just copy the template
.AHA!  I need to write a main function for “all words” and a helper for “single word.”
  Matthias: Good the first leap went fine.
  Me:  Awesome.  Now, I need another function.  How to get that stupid “x” to move over, without losing first letters

  Matthias: Why don't you make examples for this  function. And *please* do provide a contract, a purpose statement.
  Me: Yeah yeah, he wants me do that whole “recipe” thing, and make another table.  Where is this heading
  Matthias:  Spell out the (list
) elements.  Make a second example again.  
  Me:  (groan) What is the point of writing out all these letters for an example?
  Matthias: You need to actually determine the VALUE of these expressions  not just write down the expressions to make the leap.
  Me: OK, OK!  I see letters in one column, letters in another.  Is something magical supposed to happen by looking at this?
  Matthias: (sees my tables) This is huge progress.  
  Me:  ??
  Matthias:  You’re almost there! And don't forget: if the leap is to large, you may need yet another  helper function.
  Me: Helper function, hmmmm
.. I already know I need “help”--I need a function to get back those stupid missing letters!
  Matthias: 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.
  Me:  So what does he want me to do?  He says I’m not allowed to test out functions, all I can do is look at this stupid table.  Speak to me, table!
  (I stay up all night drawing tables on paper, with arrows in between the different letters, input and output).
  Me:   It seems to require a sort of REGISTER [let register = x] to save the current (first words),  which I then append to 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: "Register" sounds like an old man's way of thinking about machines and lower-level representations of computations yet. But add-prefix seems definitely related to the "it's missing the letter ..." part.  Where should this missing letter get added? Correct! At the beginning.
  Me: It's not possible to add missing letters...they are missing!  
  (I spend more hours trying to write “add-prefix” expressions, helper functions, none of them work.  None of them are recursive.  It never occurs to me that the program would require putting the recursive main function inside ANOTHER recursive function).
  Matthias: X = (list 'X 'T) and 'A --> I want (list 'A 'X 'T). How do I do that?
  Me: Oh God, is this what all these hours amount to?  I just append a stupid ‘A on to it.
  Dave Yrueta: You're so close!  Up to this point in HtDP
functions examine the first element of the list,
  either save or discard it, and then recur.  So it seems natural that any list-processing function could only produce a list of symbols with a length either equal to or less than the original list.  So you're asking yourself, given a word, or a list-of-symbols with,for example, four-letters, how in the heck do I produce a list-of-words 5 words long, with each word the length of original word? 
  Me: YES!  At least someone understands how illogical this all is.
  Dave Yrueta:  My advice is to pay extremely close attention to Matthias' last hint-- it is very telling: * X = (list 'X 'T) and 'A --> I want (list 'A 'X 'T). How do I do that?  Answer in the simplest and most natural terms you can come up with, sit it on it for awhile, and the answer may come to you.
  Me: Oh no!  Not again
. (I spend more hours drawing tables with arrows).
  Me: OK, Matthias and Marco: I realize that I need two functions: one that is shrinking and one that is growing.    So I append them together:   (append (cons-function (word)) (shrinking-function 'X (word))).  What do I get?  Garbage.
  Matthias: All I was getting at is a simple point:  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?
  Me: (groan) YES, that is exactly what I am trying to do.  Why doesn’t anyone listen that I AM trying to make this mysterious function to add the letters back
..OK, I’m just going to write out a function, totally unrelated to the main one, that adds letters to a function.  ( I write “add-first-letter”). 
WHOA!  That was really weird.  Another whole recursive function.  How complicated!  
  Matthias: 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: you failed to read and answer my second question.
  Me: Huh?  I thought I just made a huge breakthrough.  I guess not.  Back to the drawing-boards.  What in the world is he asking: “What is missing?”  Well obviously, I’m missing all these first letters.  Even if I append on “add-first-letter” all I get is one letter.
  Marco: Here is where I believe you are really stuck. All you need is to do something with (first a-word).  Where does it have to go in each of R?
  Me: (groan) Yes, I know that I need to get those stupid first letters back.
  Mark Engelberg: You keep talking about "shrinking lists"
That's not how the design of a recursive function works.  You're really just trying to figure out how to build *one level* from the level below.  In other words, when planning the function, you imagine that the recursive call works, and then figure out how to build the answer you desire from that piece.  
  Me: OK, OK, everything I’ve written is useless.  I’ll start over again from scratch.  
  Matthias: Why did you throw away your progress (add-first-letter)?  I'll give you that much: with the two you are about 10 keystrokes  from the answer.
  Me:  10 keystrokes???!  So I CAN use what I have already written, and I don’t need to draw any more stupid tables with arrows.   But what is he saying about “throwing away” add-first-letter—I must need to put that function in a different place.  
  Matthias: Let's step back a bit. 1. the design recipe works on a per function basis -- BUT YOU  
  NEED TO STICK TO IT; 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.)
  Me: Good advice.  I must be way off track.  (I rewrite the tables, make wish lists—“dear God give me a function to add the first letters incrementally!!!”)
  Matthias: Why did you not answer my second question, what is missing?
  Me: Yeah, yeah, I know I am missing all of those letters, I’m having nightmares about them.  I need to add the first letters incrementally.
  Matthias: NO! NO!  How can you add (the result of the recursion) to what you have so far? 10 keystrokes.  That's the question I raise.
  Me: ?? I thought that’s what I just said, what I’ve been saying all along.
  Marco: Ah! In the face of desperation you are abandoning your knowledge!!!  You are not using a template!   You have, for reasons I cannot fathom, abandoned the template
 You seem to be trying to
  fix something that is wrong instead of building correctly from the beginning.  
  Me: Oh lord, what is he talking about.  I guess I have to start from scratch.
  Marco:  Bigger hint: Do you want to add a letter just to (rest a-word) or to all the possible words that you can form with (rest a-word)?  Notice that all other words will have (first a-word) as the first letter. That is easy to do using (add-letter-to-all  <letter><list-of-words>).   Yes, you are practically there!!!
  Me: Hmmm, he gave me code.  That must be a huge hint.  But still, it’s not like I can just put the whole main function inside “add-letter-to-all”
  Mark Engleberg:
  Matthias’s table is where you were the closest.  In my opinion, you've been getting further off track since then.  You need to figure out how to put together the pieces in the first four columns, to get the thing in the final column.  Stay focused on that.  Matthias has given some strong hints, but perhaps some of his comments are also confusing you.  
  Me: Oh God, back to square one again.  (One more night drawing tables.)
  Finally, this morning I opened up DrScheme and defined the function from scratch.  When I got to the recursive part, I remembered Marco’s code.  That recursive list is what I needed to add letters to, using add-letter-to-all.  It looked REALLY weird to me to put the recursive part inside another recursive function

..I clicked “Run”

..Oh my God, that’s the answer!!!
  Basically what happened was that I couldn’t imagine using a recursive function inside another recursive function.  It was totally unexpected to me when I tried it.  
  I now realize that you were all pushing me to do that all along, but you see, I was still trying to visualize letters passing between functions, drawing arrows to show how to “get from column 1 to column 5.”  I thought that was the point of the table.  Ultimately it looked like a map of the New York subway.  I nearly fried my brain trying to see the letters hop over from one column to the next.
  I’m glad that you all didn’t just tell me the answer.  This was a hurdle that I had to get through.  Honestly I don’t know how any of you could have explained it better.  It seems very tricky thing to teach someone without giving away the answer.  
  As a personal note, I have read many “Learn X in 24 hours” books that went in one ear and out the other, before HtDP.  On a web developer forum someone posted, “If you read HtDP and the MIT wizard book, you will know how to program better than anyone on this forum.”    As soon as I loaded up HtDP, it was like getting on a “learning rocket.”  Now I feel like I’ve been training with the Navy Seals.  Thanks again for all your patience.

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

Posted on the users mailing list.