[plt-scheme] HTDP: 9.5.5

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Sun Sep 14 08:11:31 EDT 2008

Beautiful!! When the student becomes a teacher and explains it just  
right, he's understood and he's learning more.

Grant: When we teach this stuff, we ask three template questions at  
this stage (how many clauses in the DD and what do they distinguish;  
are any of them structures, extract the fields; do you see self- 
references, that's where you indicate recursion) and then we give  
three hints for coding:

  -- start with the case(s) that don't use recursion; the examples  
should tell you how to compute the result there
  -- then remind yourself what each subexpression in the remaining  
clauses computes
  -- find a "combinator" that uses just those values and produces the  
proper result.

If kids are really stuck with the latter, we go like this: use the  
examples, apply the sub-expressions, what should the result be?  
Tabulate this and add examples until you see what the "combinator" is.

-- Matthias



On Sep 14, 2008, at 3:35 AM, Veer wrote:

> I think this is a problem of understanding recursion than anything  
> else.
> It took me while to understand recursion.
>
> When i was stuck , Matthias wrote this (i am substituting
> 'arrangements' with 'convert') :
>
> [quote]
>
> When you go from templates to definitions, read out the PURPOSE
> statement for the recursive template expression:
>
> ;;(convert a-list) produce the number that can be formed from all
> ;; digits in  a-list.
>
> ;; (convert (rest a-list)) therefore produces the number that can  
> be formed
> ;; from all the digits in the rest of a-list
> (What does this mean for a concrete example? Use the examples!!)
>
> And then ask yourself how a primitive or a helper function can
> use this and the rest of the template (line) to get the real
> result..
> [unquote]
>
> For example:
> ;;(convert a-list)
> (convert (cons 1 (cons 2 (cons 3 empty))) produces what
>
> ;;(convert (rest a-list))
> (convert (cons 2 (cons 3 empty))) produces what
>
> So does this help?
>
>
> On 9/14/08, Grant Rettke <grettke at acm.org> wrote:
>>> Now discover Jens's hint by following the design recipe.
>>
>> Where did I go wrong? (Here is not where I expect you to be psychic,
>> so let me elaborate)
>>
>> I followed the recipe by defining the recursive data (I re-used list
>> of numbers), created a bunch of tests, walked through the
>> implementation of the body (cond clauses, selector expressions,
>> natural recursion), implemented the answer for the base case (zero),
>> and then was left with:
>>
>> [else
>>  ... (first a-list-of-numbers) ...
>>  ... (convert (rest a-list-of-numbers) ...)]
>>
>> I think I was too preoccupied with shoe-horning in my approach than
>> looking at the data. What I *didn't* do was to take something one  
>> more
>> complex than the base case, like this, which is a test I had written
>> before I implemented the function:
>>
>> (check-expect (convert (cons 1 empty)) 1)
>>
>> That at least would have gotten me to the first part of the equation
>> in the else clause, 1 plus ...
>>
>> Then I would have looked at:
>>
>> (check-expect (convert (cons 0 (cons 1 empty))) 10)
>>
>> and maybe though zero plus something times the 2nd part, and  
>> finally plus
>> zero.
>>
>> Is that the thought process, step by step satisfy the test by  
>> revising
>> the calculation? You start with the simplest thing from the base
>> condition?
>>
>> My approach thus far has been to write *all* of the tests up front, I
>> was staring at this while I tried to implement the body:
>>
>> (check-expect (convert empty) 0)
>> (check-expect (convert (cons 1 empty)) 1)
>> (check-expect (convert (cons 0 (cons 1 empty))) 10)
>> (check-expect (convert (cons 1 (cons 1 empty))) 11)
>> (check-expect (convert (cons 0 (cons 0 (cons 1 empty)))) 100)
>> (check-expect (convert (cons 1 (cons 1 (cons 1 empty)))) 111)
>>
>> This was a point where I totally didn't understand it and I felt like
>> the recipe wasn't taking me there, which I was I posted a long-ish
>> email.
>>
>> Please point me in the right direction to get back on track with what
>> I missed from the recipe.
>> _________________________________________________
>>   For list-related administrative tasks:
>>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>>



Posted on the users mailing list.