[plt-scheme] Re: Permutation correct way to do it ?

On Apr 5, 2008, at 1:30 PM, richard gere wrote:
> I think problem was recursion , i did not look hard enough to
> understand it and solved the earlier exercises mechanically (will look
> back again) . In recursively calling a function thing was to look
> backwords , and build from there and i was looking forward , a good
> example of it was "arrangements" function .
> Once this was clear , templates made it easy to devise the function.


When you go from templates to definitions, read out the PURPOSE
statement for the recursive template expression:

;; (arrangements a-word) produces the list of words that can be
;; formed with all the letters in the word (a list of letters)

(arrangements (rest a-word)) therefore produces the list of words
that can be formed from all the letters in the rest of the word.
(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: the arrangements for all the words.


> In my opinion , this time you will be pleased with my code other then
> spelling mistakes.
> Any criticism are welcome .
>
> I also keep getting this error :
> ERROR :reference to an identifier before its definition
> So code has to be read from bottom .


Arrange the code top-down, starting with the most important function,  
finishing with the least important function.

Put all tests at the end. In future releases of DrScheme, we will fix  
this so that tests are collected and executed at the end.

-- Matthias













>
> -----CODE START--------
>
> ;;final
>
> ;;Data Definition for a word
> ;;A word is either
> ;;1. empty or
> ;;2. (cons s wd) where s is a symbol in 'a,'b,'c,...'z and wd is a  
> word
> ;;Example
> ;; (cons 'a (cons 'b (cons 'c empty))) is a word
>
>
> ;;Data definition for a list-of-words
> ;;A list-of-words is either
> ;;1. empty or
> ;;2 (cons wd lw) where wd is a word and lw is a list-of-words
> ;;Example
> ;;(cons (cons 'b (cons 'c empty)) (cons (cons 'c (cons 'b empty))  
> empty))
>
>
> ;;Because of some error the code is to be read from bottom
>
>
> ;;insert-at-begining : symbol word -> word
> ;;to insert a-sym at the begining of a-word
> ;;Examples :
> ;;given 'a (cons 'b (cons 'c empty)) -> (cons 'a (cons 'b (cons 'c  
> empty)))
> ;;given 'a empty -> (cons 'a empty)
> (define (insert-at-begining a-sym a-word)
>   (cond
>     [(empty? a-word) (cons a-sym empty) ]
>     [else (cons a-sym a-word) ]))
>
> ;;tests
> (check-expect (insert-at-begining 'a (cons 'b (cons 'c empty)))
>               (cons 'a (cons 'b (cons 'c empty))) )
> (check-expect (insert-at-begining 'a empty) (cons 'a empty))
>
>
> ;;insert-at-end : symbol word -> word
> ;;to insert a-sym at the end of a-word
> ;;Example : given  'a (cons 'b (cons 'c empty)) -> (cons 'b (cons 'c
> (cons 'a empty)))
> (define (insert-at-end a-sym a-word)
>   (cond
>     [(empty? a-word) (cons a-sym empty) ]
>     [else (append a-word (cons a-sym empty)) ]))
>
> ;;Tests
> (check-expect (insert-at-end 'a (cons 'b (cons 'c empty)))
>               (cons 'b (cons 'c (cons 'a empty))))
>
>
>
> ;;REMARK : i have to move this definition up , because
> ;;in insert-in-between-letters  i go the error :
> ;;ERROR:reference to an identifier before its definition: insert-at- 
> front
>
> ;;insert-at-front : symbol list-of-words -> list-of-words
> ;;to create a list-of-words by inserting a-sym at the front of all
> ;;words in the list-of-words (alow)
> ;;eg given 'b (cons (cons 'c (cons 'a (cons 'd empty))) empty) ->
> ;;(cons (cons 'b (cons 'c (cons 'a (cons 'd empty)))) empty)
> (define (insert-at-front a-sym alow)
>   (cond
>     [(empty? alow) empty]
>     [else (cons (cons a-sym (first alow))  (insert-at-front a-sym
> (rest alow))) ]))
>
> ;;Tests
> (check-expect (insert-at-front 'b (cons (cons 'c (cons 'a (cons 'd
> empty))) empty))
>               (cons (cons 'b (cons 'c (cons 'a (cons 'd empty))))  
> empty))
>
> (check-expect (insert-at-front 'b (cons (cons 'c (cons 'a empty))
>                                         (cons (cons 'd (cons 'e  
> empty)) empty)))
>               (cons (cons 'b (cons 'c (cons 'a empty)))
>                     (cons (cons 'b (cons 'd (cons 'e empty))) empty)))
>
>
>
>
> ;;insert-in-between-letters : symbol word -> list-of-words
> ;;to create a list-of-words by inserting a-sym between the letters  
> of a-word
> ;;Examples :
> ;;given 'a (cons 'b (cons 'c (cons 'd empty))) ->
> ;;(cons (cons 'b (cons 'a (cons 'c (cons 'd empty))))
> ;;(cons (cons 'b (cons 'c (cons 'a (cons 'd empty)))) empty))
>
> (define (insert-in-between-letters a-sym a-word)
>   (cond
>     [(empty? (rest a-word)) empty]
>     [else (cons    (cons (first a-word) (cons a-sym (rest a-word)))
>                    (insert-at-front (first a-word)
>                                     (insert-in-between-letters a-sym
> (rest a-word)))) ]))
>
> ;;Tests
> (check-expect (insert-in-between-letters 'a (cons 'b (cons 'c (cons  
> 'd empty))))
>               (cons (cons 'b (cons 'a (cons 'c (cons 'd empty))))
>                    (cons (cons 'b (cons 'c (cons 'a (cons 'd  
> empty)))) empty)))
>
>
>
>
> ;;insert-everywhere-in-a-word : symbol word -> list-of-words
> ;;to create a list of words by inserting a-sym at the beginning ,
> ;;in between the letters and at the end of a-word.
> ;;Examples :
> ;;given the input: 'a (cons 'b (cons 'c empty)) ->
> ;;(cons (cons 'a (cons 'b (cons 'c empty)))
> ;;(cons (cons 'b (cons 'a (cons 'c empty)))
> ;;(cons (cons 'b (cons 'c (cons 'a empty))) empty)))
>
> ;;given the input: 'c empty
> ;;(cons (cons 'c empty) empty)
> ;;ERROR :reference to an identifier before its definition: insert- 
> at-begining
> (define (insert-everywhere-in-a-word a-sym a-word)
>   (cond
>     [(empty? a-word) (cons (insert-at-begining a-sym a-word) empty)]
>     [else (append (cons (insert-at-begining a-sym a-word) empty)
> (insert-in-between-letters a-sym a-word)
>           (cons (insert-at-end a-sym a-word) empty)) ]))
>
> ;;Tests
> (check-expect (insert-everywhere-in-a-word 'c empty)
>               (cons (cons 'c empty) empty))
>
> (check-expect (insert-everywhere-in-a-word 'a (cons 'b (cons 'c  
> empty)))
>               (cons (cons 'a (cons 'b (cons 'c empty)))
>                     (cons (cons 'b (cons 'a (cons 'c empty)))
>                           (cons (cons 'b (cons 'c (cons 'a empty)))  
> empty))))
>
>
>
> ;;insert-everywhere/in-all-words : symbol list-of-words -> list-of- 
> words
> ;;to create a list of words by inserting a-sym between all letters and
> ;;at beginning and at end of all words in the list-of-words (alow)
> ;;Examples : given the input 'b (cons (cons 'c empty) empty) ->
> ;;   (cons (cons 'b (cons 'c empty)) (cons (cons 'c (cons 'b  
> empty)) empty))
> ;;given  'c (cons empty empty) -> (cons (cons 'c empty) empty)
> ;;ERROR : reference to an identifier before its definition:
> insert-everywhere-in-a-word
> (define (insert-everywhere/in-all-words a-sym alow)
>   (cond
>     [(empty? alow) empty]
>     [else (append (insert-everywhere-in-a-word a-sym (first alow))
>           (insert-everywhere/in-all-words a-sym (rest alow))) ]))
>
> ;;Tests
> (check-expect (insert-everywhere/in-all-words 'b (cons (cons 'c  
> empty) empty))
>               (cons (cons 'b (cons 'c empty)) (cons (cons 'c (cons 'b
> empty)) empty)))
>
>
>
> ;;arrangements : word -> list-of-words
> ;;to create a list of words  by rearranging the letters in a-word
> ;;Examples:
> ;;given the input (cons 'a (cons 'b empty)) -> (cons (cons 'a (cons  
> 'b empty))
> ;;                                               (cons (cons 'b (cons
> 'a empty)) empty))
> ;;given (cons 'a (cons 'b (cons 'c empty))) -> ( '(a b c) '(b a c) '(b
> c a) '(a c b) '(c a b) '(c b a) )
> ;;ERROR:reference to an identifier before its definition:
> insert-everywhere/in-all-words
> (define (arrangements a-word)
>   (cond
>     [(empty? a-word) (cons empty empty) ]
>     [ else (insert-everywhere/in-all-words (first a-word)
> (arrangements (rest a-word)) ) ]))
>
> ;;Tests
> (check-expect (arrangements (cons 'a empty)) (cons (cons 'a empty)  
> empty))
>
> (check-expect (arrangements (cons 'a (cons 'b empty)))
> (cons (cons 'a (cons 'b empty))
> (cons (cons 'b (cons 'a empty)) empty)))
>
> (check-expect (arrangements (cons 'a (cons 'b (cons 'c empty))))
> (cons (cons 'a (cons 'b (cons 'c empty)))
> (cons (cons 'b (cons 'a (cons 'c empty)))
> (cons (cons 'b (cons 'c (cons 'a empty)))
> (cons (cons 'a (cons 'c (cons 'b empty)))
> (cons (cons 'c (cons 'a (cons 'b empty)))
> (cons (cons 'c (cons 'b (cons 'a empty))) empty))))))    )
>
> (generate-report)
>
> ----CODE END----------------------------
>
>
> Thanks
> Veer
>
>
>
> .
>
> On Fri, Apr 4, 2008 at 9:23 PM, Matthias Felleisen  
> <matthias at ccs.neu.edu> wrote:
>>
>>  On Apr 4, 2008, at 5:21 AM, richard gere wrote:
>>
>>> Thank you for taking a look at my code.
>>>
>>>
>>
>>  Here is a second look. Up to this point you are right on track:
>>
>>
>>
>>>   [else (append (insert-symbol-in-a-word a-sym (first alow) empty)
>>>                 (insert-everywhere/in-all-words a-sym (rest  
>>> alow))) ]))
>>>
>>
>>
>>  The use of insert-symbol-in-a-word contradicts the contract/purpose
>> statement of the actual function definition:
>>
>>
>>
>>
>>> ;;here is the final definition
>>> ;;insert-symbol-in-a-word : a-sym word -> list-of-words
>>> ;;to create a list of words by inserting a-sym between cl and
>>> ;; a-word for all letters in a-word
>>> ;;eg (insert-symbol-in-a-word 'a (cons 'b empty)) give us
>>> ;;(cons (cons 'a (cons 'b empty)) (cons (cons 'b (cons 'a empty))  
>>> empty))
>>> (define (insert-symbol-in-a-word a-sym a-word cl)
>>>
>>
>>
>>  As you can see your function consumes THREE arguments in reality,  
>> but your
>> contract says TWO.
>>
>>  You discovered another design technique (you are using a form of
>> accumulator) and are using in an ad-hoc fashion. At the scale at  
>> which you
>> are programming, this is probably fine. BUT if this were a large  
>> module and
>> you might have to hand it over to someone else, this person would get
>> confused now.
>>
>>  In a typed programming language, say Java, this would be  
>> discovered by type
>> checks. So this particular mistake may not show up. You could  
>> still end up
>> using a random ad hoc design, which would still confuse other  
>> programmers.
>>
>>  You could, for example, claim that this is plain structural  
>> recursion in a
>> comment and .. it isn't. And there is no tool that really checks  
>> this aspect
>> of code.
>>
>>  ;; ---
>>
>>  A second criticism: I urge you to design tests for individual  
>> functions as
>> well as the main function. It really helps think through designs.
>>
>>  For an exercise, you may wish to actually design the function  
>> that you
>> advertise:
>>
>>  ;; insert-symbol-in-a-word : Symbol Word -> Listof-Word
>>  ;; insert let in each position into word (including beginning and  
>> end)
>>  ;; Example:
>>  ;; given 'a and (cons 'b (cons 'c empty)) ---> ???
>>  ;; given 'x and (cons 'a (cons 'b (cons 'c empty))) ---> ???
>>  (define (insert-symbol-in-a-word let a-word)
>>   empty) ;; <---- Note: I recommend a dummy response
>>
>>
>>  (check-expect (insert-symbol-in-a-word 'a (cons 'b (cons 'c empty)))
>>               ????)
>>  (check-expect (insert-symbol-in-a-word 'x  (cons 'a (cons 'b  
>> (cons 'c
>> empty)))
>>               ????)
>>
>>  (generate-report)
>>
>>  ;; ---
>>
>>  Having said that, I have never seen your solution and will study  
>> it to see
>> how it can be easily explained as another example of accumulator  
>> design.
>>
>>  -- Matthias
>>
>>
>>
>>
>>> ;;here is the final definition
>>> ;;insert-symbol-in-a-word : a-sym word -> list-of-words
>>> ;;to create a list of words by inserting a-sym between cl and
>>> ;; a-word for all letters in a-word
>>> ;;eg (insert-symbol-in-a-word 'a (cons 'b empty)) give us
>>> ;;(cons (cons 'a (cons 'b empty)) (cons (cons 'b (cons 'a empty))  
>>> empty))
>>> (define (insert-symbol-in-a-word a-sym a-word cl)
>>>  (cond
>>>   [(empty? a-word) (cons (append cl (list a-sym ) a-word ) empty)]
>>>   [else (cons (append cl (cons a-sym empty)  a-word )
>>>               (insert-symbol-in-a-word a-sym (rest a-word)
>>>                                        (append cl (cons (first
>>> a-word) empty)))) ]))
>>>
>>>
>>
>>
>>
>>
>>
>>
>>