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

 From: richard gere (diggerrrrr at gmail.com) Date: Sat Apr 5 13:30:35 EDT 2008 Previous message: [plt-scheme] Re: Permutation correct way to do it ? Next message: [plt-scheme] Re: Permutation correct way to do it ? Messages sorted by: [date] [thread] [subject] [author]

```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.

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 .

-----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
>
>  ;; 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)))) ]))
> >
> >
>
>
>
>
>
>
>

```

 Posted on the users mailing list. Previous message: [plt-scheme] Re: Permutation correct way to do it ? Next message: [plt-scheme] Re: Permutation correct way to do it ? Messages sorted by: [date] [thread] [subject] [author]