Exercise 168: Design insert-everywhere/in-all-words.

Exercise 168:  Design insert-everywhere/in-all-words.

It consumes a 1String and a list of words. The result is a list of words like its second argument, but with the first argument inserted at the beginning, between all letters, and at the end of all words of the given list.

Note: I've taken a slightly different approach to structuring this answer. As this is a reasonably complex question (at least compared to that which has been asked so far), there are a larger than normal number of functions. There are five supporting functions, which is not overly large number in itself, but as each function has a number of check-expect test functions to support, the signal-to-noise ratio became quite high. I have moved all of the check-expect functions to the end of the answer, and briefly described the point of each test there. This allows me to keep the main section of the answer uncluttered and a little easier to read

I'm not 100% happy with the approach I took to this solution. It seemed a clean solution in my head but when it came time to put it into code form it became a lot more complex. There is probably a solution out there that is a cleaner than this.

The problem we have is to take a list of letters, and return a new list of lists of letters with our new letter inserted into each place.  Helper functions aside, the main problem is to create a function that will take in a list and a letter, and return a new list with the letter inserted between each letter of the original list. I have called this function insert. In this function we need to recurse through the original word, letter by letter,  creating a new word by inserting the letter in the appropriate place and appending all these new words together.  The challenge here is as we recurse, we need to keep track of both the entire word that we are inserting the letter into, but also where in the word we should be inserting into.

Solving this procedurally with something like Ruby or Python would be very straight forward, but we need to come up with a way of doing this in a functional manner.  I could think of two ways of doing this:

1. Passing in an insertion position/count as you recurse through the word
2. Splitting the list into two - a before and after split, and changing the position of the split as you recurse.

The second option seemed a better idea, though in hindsight, I think passing a position down would have been easier.

Choosing the second option introduced new problems - maintaining this new list. I chose to wrap these before and afters lists up in a new list so that I could pass around only one list, instead of continually passing both lists. To simplify the main function I also required a function dedicated to moving the split in these two lists along. None of these issues were particularly difficult, but I think they could have been avoided altogether by choosing the first option.

Solution

The arrangements function here is taken directly from the text. It recurses through a word building up a list of subwords using the insert-everywhere/in-all-words helper function.

; 1String -> List-of-words
(define (arrangements w)
  (cond
    [(empty? w) (list empty)]
    [else (insert-everywhere/in-all-words (first w)
            (arrangements (rest w)))]))



The insert-everywhere/in-all-words function is the main function that we are asked to create - but does very little of the actual work.
It consumes a letter and a list of words and creates a new expanded list of words with the supplied letter inserted at each point within each word.
The work is mostly farmed out to the helper function insert which for a specific letter and word combination, returns a new list of words with the letter correctly inserted in each place. These lists are then appended together to form a larger list containing the combinations for each word passed in in the original list.

; Letter List of Words -> List of Words
(define (insert-everywhere/in-all-words letter words)
  (cond ((empty? words) empty)
        (else (append
               (insert letter (list empty (first words)) empty)
               (insert-everywhere/in-all-words letter (rest words))))))



The insert function does the actual inserting of the letter into the word. This function takes in three arguments - the letter to insert, a list containing the two sections of the word it should be inserting this letter between, and the expanded list of words with the letter already inserted. This last argument will have the newly created arrangement appended to it and will be the value returned.
The idea here is that we are passing two lists - list1 and list2, each containing a section of the word. The boundaries of the word sections in this list will be adjusted each time. Eg, in pseudo-code, inserting the letter X in the word "dog":


X (list nil dog) ->  (list d og)    (list Xdog)
X (list d og)    ->  (list do g)    (list Xdog dXog)
X (list do g)    ->  (list dog nil) (list Xdog dXog doXg)
X (dog nil)      ->  (list dog nil) (list Xdog dXog doXg dogX)


;insert the letter between word1 and word2 (parts of the same word)
; Letter, List-of-1Strings,  
(define (insert letter word-lists combinations)
  (cond ((empty? (second word-lists)) (append combinations  
                                              (ins-middle letter word-lists))) 
        (else (insert letter 
                      (progress-list word-lists)
                      (append combinations (ins-middle letter word-lists)))))) 





To simplify the insert function I have another helper function progress-list that does nothing other than move the split in the two words one character further along. There is no reason we couldn't have done this within the insert function, but moving it out here makes the insert function a lot shorter and easier to read.

; takes in list of two words segments (eg, a word split in two) and
; moves the split further down the list
; (list "wor" "d") -> (list "wo" "rd")
; list-of-words -> list-of-words
(define (progress-list word-lists)
  (list
   ; when we pull the first letter of the second word-list it's no longer a list
   ; to append it correctly, we need to use cons, or turn it back into a list
   (append (first word-lists) (list (first (second word-lists))))
   ; if we're at the end of the second-word list return an empty list
   ; rather than a list containing an empty list
   (cond ((empty? (rest (second word-lists))) empty)
         (else   (rest (second word-lists))))
  ))


The second helper function created to support insert is the ins-middle function. This function takes in a letter and a list of two word sections, and returns a new word with the letter inserted in the middle of the two lists.
Eg:

X (list empty "dog") -> Xdog
X (list "d" "og")    -> dXog


The letter is passed in simply as a character, not as  part of a list, so to use append we need to make it a list. we could use cons here, but that is so . .. messy

We also wrap what we are returning in a list. This isn't necessary, but this is a helper function for the main insert function which is more complex. The insert function requires the returned word to be part of a list already, (or it needs to convert the word to a list there). If we do not do this  all the words will get munged into one long word. By double wrapping the list here, we can make the main insert function shorter and a little clearer.


; letter list-of-1strings -> list-of-lists-of-1strings
(define (ins-middle letter word-lists)
  (cond ((empty? (first word-lists)) (list (cons letter (second word-lists))))
        (else (list (append (first word-lists)
                            (list letter) 
                            (second word-lists) empty)))))

Example Output

Finally, here is an example output of our arrangement function:


> (arrangements (list "w" "o" "r" "d"))
(list
 (list "w" "o" "r" "d")
 (list "o" "w" "r" "d")
 (list "o" "r" "w" "d")
 (list "o" "r" "d" "w")
 (list "w" "r" "o" "d")
 (list "r" "w" "o" "d")
 (list "r" "o" "w" "d")
 (list "r" "o" "d" "w")
 (list "w" "r" "d" "o")
 (list "r" "w" "d" "o")
 (list "r" "d" "w" "o")
 (list "r" "d" "o" "w")
 (list "w" "o" "d" "r")
 (list "o" "w" "d" "r")
 (list "o" "d" "w" "r")
 (list "o" "d" "r" "w")
 (list "w" "d" "o" "r")
 (list "d" "w" "o" "r")
 (list "d" "o" "w" "r")
 (list "d" "o" "r" "w")
 (list "w" "d" "r" "o")
 (list "d" "w" "r" "o")
 (list "d" "r" "w" "o")
 (list "d" "r" "o" "w"))

Tests for arrangements function

; a simple test of the functions behavior overall using a 3 letter list
(check-expect (arrangements (list "c" "a" "t"))
              (list
               (list "c" "a" "t")
               (list "a" "c" "t")
               (list "a" "t" "c")
               (list "c" "t" "a")
               (list "t" "c" "a")
               (list "t" "a" "c")))


; an arranged empty list should be an empty list
(check-expect (arrangements empty)
              (list empty))


; an arranged list of 1 char, should be a list of 1 list containing 1 char
(check-expect (arrangements (list "c"))
              (list (list "c")))

Tests for insert-everywhere/in-all-words function

; this is a subset of the arrangements test. A single list should
; rearrange as expected.
(check-expect (insert-everywhere/in-all-words "X" (list (list "d" "e")))
              (list (list "X" "d" "e")
                    (list "d" "X" "e")
                    (list "d" "e" "X")))


; test for an empty list - just returns an empty list
(check-expect (insert-everywhere/in-all-words "X" empty)
              empty)




; one word list
(check-expect (insert-everywhere/in-all-words "X" (list (list "e")))
                  (list (list "X" "e")
                        (list "e" "X")))

Tests for insert function

; this is a subset of the arrangements test. A single list should
; rearrange as expected.
(check-expect (insert "x" (list empty (list "c" "a" "t")) empty)
              (list (list "x" "c" "a" "t")
                    (list "c" "x" "a" "t")
                    (list "c" "a" "x" "t")
                    (list "c" "a" "t" "x")))

Tests for progress-list function

; "" "cat" -> "c" "at"
(check-expect (progress-list (list empty (list "c" "a" "t") ))
              (list (list "c") (list "a" "t")))


; "ca" "t" -> "cat" ""
(check-expect (progress-list (list (list "c" "a") (list "t" )))
              (list (list "c" "a" "t") empty))


No point testing this function with a empty second list as you can't progress this list any further - you would expect this to fail.

Tests for ins-middle function

; "x" "ca" "t"  -> "caxt"
(check-expect (ins-middle "x" (list (list "c" "a") (list "t")))
              (list (list "c" "a" "x" "t")))


; "x "" "cat" -> "xcat"
(check-expect (ins-middle "x" (list empty (list "c" "a" "t")))
              (list (list "x" "c" "a" "t" )))




; "x" "cat" "" -> "cat"
(check-expect (ins-middle "x"  (list (list "c" "a" "t") empty))
              (list (list  "c" "a" "t" "x")))