[plt-scheme] HTDP 12.4.2

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Wed Jun 21 22:32:29 EDT 2006

Wooks wooks, Danny has given you the great "design recipe" spiel (no 
patterns here). Let me push you harder on this, because once you follow 
this, you'll see that even complex functions like this one are easy.


On Jun 21, 2006, at 8:03 PM, wooks wooks wrote:

> ;CONTRACT
> ;insertEverywhere : symbol ('a - 'z) list (word) - list of lists

Danny is 100% correct. You are using random things in the contract. 
What does this show? It shows that you haven't thought through the data 
that goes in and the data that comes out. But that's the only thing you 
have to design the box in the middle. (Can you see the most (ab)used 
image of CS with your mental eye now?) You really really need to 
understand. So DEFINE letter and DEFINE word and DEFINE list-of-words:

Letter = Symbol ['a ... 'z to be precise]
A Word is one of:
  - empty
  - (cons Letter Word)
A LoWords is one of:
  - empty
  - (cons Word LoWords)

> ;returns a list of words constructed by interpersing symbol in  
> position of the word
> ;
> (define (insertEverywhere sym letters)
>  (infiltrate  sym empty  letters)
>  )


But this one line shows something even worse. You have jumped to a 
conclusion like so many programmers. You assume that some auxiliary 
function is necessary. You assume that it consumes two lists. WHY? 
Unless you know that inserting a letter everywhere is the composition 
of two (or more) tasks (example: average of a list of numbers is (sum 
them up) / (count their number)), DON'T DO IT. Use the force, Wookie. I 
mean use the steps:

3. Make up examples: given x and y, expect z ...

4. What's the template (inventory of knowledge)

5. Define the function.

6. Turn the examples into tests.

(equal? (insert-everywhere 'a (list 'b 'c))
         (cons (list 'a 'b 'c)
           (cons (list 'b 'a 'c)
             (cons (list 'b 'c 'a)
                empty))))

Etc.

-- Matthias











>
> ;CONTRACT
> ;infiltrate : symbol list list - list of words
> ; (define (infiltrate infiltrator front back) ...
> ; auxiliary function for insertEverywhere
>
> ;TEMPLATE
> ;(define (infiltrate infiltrator front back)
> ;   (cond
> ;      [(empty? back) ....]
> ;      [(empty? front) ..(infiltrate infiltrator (list (first back)) 
> (rest back).]
> ;      [else (..... (infiltrate infiltrator (append front (list (first 
> back))) (rest back))]
> ;    )
> ;  )
>
> (define (infiltrate infiltrator front back)
>  (cond
>    [(empty? back) (append front (list infiltrator))]
>    [(empty? front)
>     (cons (cons infiltrator back)
>           (infiltrate infiltrator (append (list (first back) )) (rest 
> back))) ]
>    [else
>     (cons (append front (list infiltrator) back)
>           (infiltrate infiltrator (append front (list (first back))) 
> (rest back)))]
>    )
>  )
> ;TESTS
> (insertEverywhere 'g (cons 'a (cons 'b (cons 'c empty))))
>
>
> ;; arrangements : word  ->  list-of-words
> ;; to create a list of all rearrangements of the letters in a-word
> (define (arrangements a-word)
>  (cond
>    [(empty? a-word) (cons empty empty)]
>    [else (insertEverywhere (first a-word)
>            (arrangements (rest a-word)))]))
>
> ;TESTS
> (arrangements  (cons 'a (cons 'b (cons 'c empty))))
>
>
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme



Posted on the users mailing list.