[plt-scheme] HtDP newbie question, 12.4.2

You keep talking about "shrinking lists", as if you think that
designing a recursive function means building a list of all the
recursive calls as the input dwindles down.  Trying to wrap your head
around the entire tower of recursive calls just makes things more
confusing.

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.  That's why the chart you drew is
such a key piece of the puzzle.  The fourth column shows you what
you'd get if the recursive call generated what it's designed to.
Assume that works.  Then, figure out how to combine that piece with
the first three columns to get the final column.  Do you see a
relationship between the final column and the fourth column?  What is
that relationship?  Can you *build* the final column from the other
columns?

--Mark

On Fri, Mar 28, 2008 at 6:03 PM, Cooke Kelsey <cookekelsey at yahoo.com> 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?"
>
> 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 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.)
>
>
> ;; ---
>
>
> 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.
> _________________________________________________
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
>