[racket] arrangements exercise

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