[racket] arrangements exercise

From: Sean Kemplay (sean.kemplay at gmail.com)
Date: Fri Jul 6 05:48:49 EDT 2012

Hi Matthias,

Thanks for the feedback. Just a couple of questions before I give it
another go if that's okay. I know there is something I need to learn from
this exercise.

I am going through htdp first edition (at chapter 17 which refers to
arrangements from chapter 12 which is why I revisited the exercise). Would
you suggest continuing with this edition or moving to the draft second
edition?

Do you mean the contract for insert-everywhere/word should be symbol word
-> list of words? And will the words returned be the same length? Ie am I
aiming for the same result as the current definition?

Thanks Sean.
On Jul 5, 2012 9:15 PM, "Matthias Felleisen" <matthias at ccs.neu.edu> wrote:

>
> Sean,
>
> 1. I have re-arranged your program so that it becomes readable:
>
> -- the function that explains it all comes first
> -- if you need a helper function, it is placed below
> -- don't place functions at top that are called by functions further down
>         (roughly)
>
> -- make sure lines are at most 80 keystrokes wide
>
> 2. I have separated the part you created with a == line from the one
> that is given.
>
> 3. I added two comments in place where it becomes obvious that you
> didn't design according to the book but with an ad-hoc method.
>
> Overall, you discovered a design method that is introduced 2 chapters
> later. You used it when it is unnecessary to do so. The program is
> far more complicated (and thus slower) than needed.
>
> 3a. It is possible that you have seen the exercise on creating a one-line
> editor (like Word or Notepad). At least the data structure suggests this
> is possible. IF SO (and I don't know whether this is true), then you might
> have designed by "copy example, change until it works". IF SO, let me
> strongly discourage this approach or -- if you do follow it -- let me
> encourage you to be aware of it and to attempt a systematic approach,
> which tends to produce much better results.
>
> 4. PLEASE feel encouraged to try again. Read the first piece of
> in-lined comment to just skip the whole split-word data structure.
> Follow the design recipe and you will find a wonderful solution.
>
> -- Matthias
>
>
>
>
> #lang racket
>
> (require test-engine/racket-tests)
>
> ;; Word -> [Listof Word]
> (check-expect (arrangements '(a))  (list '(a)))
> (check-expect (arrangements '(a b)) (list '(a b) '(b a)))
>
> (define (arrangements a-word)
>   (cond
>     [(empty? a-word) (cons empty empty)]
>     [else
>      (insert-everywhere/in-all-words (first a-word) (arrangements (rest
> a-word)))]))
>
> ;;
> =============================================================================
>
> ; A split-word is a struct where left and right are list of words
> (define-struct split-word (left right))
>
> ;; insert-everywhere/in-all-words symbol list-of-words -> list of words
> ;; insert the symbol in all possible positions in each word returning an
> ;; expanded list of words
>
> (check-expect (insert-everywhere/in-all-words 'a (cons '(b) empty))
>               (list (list 'a 'b) (list 'b 'a)))
>
> (check-expect (insert-everywhere/in-all-words 'd '((e r) (r e)))
>               '((d e r) (e d r) (e r d) (d r e) (r d e) (r e d)))
>
> (define (insert-everywhere/in-all-words s a-low)
>   (cond
>     [(empty? a-low) empty]
>     ;; MF: this is where it gets weird (from what you know):
>     ;; why do you introduce an intermediate data structure (split-word)
>     ;; to represent a word? It is *difficult* to justify this design with
>     ;; the material in the first three chapters.
>     ;; the function insert-everywhere/word should really just consume a
> word
>     [else (append (insert-everywhere/word s (make-split-word '() (first
> a-low)))
>                   (insert-everywhere/in-all-words s (rest a-low)))]))
>
> ;;insert-everywhere/in-one-word symbol split-word -> low
> ;; take a symbol and a split word and insert the symbol before and after
> each
> ;; letter in the right hand side of the split creating a list of new words
> with
> ;; the symbol progressing through.
>
> (check-expect (insert-everywhere/word 'a (make-split-word empty empty))
>               (list (list 'a)))
> (check-expect (insert-everywhere/word 'a (make-split-word '(b) empty))
>               (list '(b a)))
> (check-expect (insert-everywhere/word 'a (make-split-word empty '(b)))
>               (list '(a b) '(b a)))
> (check-expect (insert-everywhere/word 'a (make-split-word empty '(b c)))
>               (list '(a b c) '(b a c) '(b c a)))
>
> (define (insert-everywhere/word s a-sw)
>   (cond
>     [(empty? (split-word-right a-sw)) (cons (insert-symbol s a-sw) empty)]
>     [else (cons (insert-symbol s a-sw)
>                 ;; MF: this is where you go beyond what the design ideas
> you
>                 ;; have seen in chapters 1 thru 3, and it makes the design
>                 ;; utterly inelegant. Specifically, you are NOT applying
>                 ;; insert-everywhere/word to a *piece* of a-sw but to a
> complete
>                 ;; re-arrangement.
>                 (insert-everywhere/word s (move-split a-sw)))]))
>
> ;; move-split split-word -> split-word
> ;; return a new split word with the list on the left having the first of
> ;; the right list appended to the end and the rest of the right
> (define (move-split a-sw)
>   (cond
>     [(empty? (split-word-right a-sw)) a-sw]
>     [else (make-split-word
>            (append (split-word-left a-sw) (list (first (split-word-right
> a-sw))))
>            (rest (split-word-right a-sw)))]))
>
> (check-expect (move-split (make-split-word empty empty))
>               (make-split-word empty empty))
> (check-expect (move-split (make-split-word '(a) empty))
>               (make-split-word '(a) empty))
> (check-expect (move-split (make-split-word '(a) '(b)))
>               (make-split-word '(a b) empty))
> (check-expect (move-split (make-split-word '(a) '(b c)))
>               (make-split-word '(a b) '(c)))
> (check-expect (move-split (make-split-word '(a b) '(c d)))
>               (make-split-word '(a b c) '(d)))
>
> ;; insert-symbol symbol split-word -> word
> ;; Insert the sysmbo at the front of the left list and append the right if
> left is empty
> ;; Append to end of left if right list is empty
> ;; Otherrwise insert between - returning one list
>
> (check-expect (insert-symbol 'a (make-split-word empty empty))
>               '(a))
> (check-expect (insert-symbol 'a (make-split-word '(b) empty))
>               '(b a))
> (check-expect (insert-symbol 'a (make-split-word empty '(b)))
>               '(a b))
> (check-expect (insert-symbol 'a (make-split-word '(b) '(c)))
>               '(b a c))
>
> (define (insert-symbol s a-sw)
>   (cond
>     [(empty? (split-word-right a-sw)) (append (split-word-left a-sw) (cons
> s empty))]
>     [(empty? (split-word-left a-sw)) (cons s (split-word-right a-sw))]
>     [else (append (split-word-left a-sw) (cons s (split-word-right
> a-sw)))]))
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20120706/3c4ccd3b/attachment.html>

Posted on the users mailing list.