[plt-scheme] HtDP 12.4.2 Design Recipe Blues

Help!  I've fallen on HtDP problem 12.4.2 and I can't get up!

Here's a link -- http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-16.html#node_sec_12.4

As a home schooled newbie trying to get through HtDP in my spare time,
I've been working on this problem for last two months and am now
declaring myself officially stumped.  My version of the function
performs the insertions properly, but for any list-of-words containing
2+ words, the output takes the shape of something more than the
intended list-of-words, but less than the full-blown list-of-list-of-
words it approaches.  It looks like this --

Dave's List (dl) is either
1.	low where 'low' is a list-of-words
2.	(cons low dl)

--  and I can't fix it.

Last time I showed up asking for help with an HtDP problem, I was
encouraged to submit my design recipe.  Comments on my design would be
the most helpful, since in the end I'm really more interested in
identifying the design flaw than in knowing the right answer.  But for
anyone who would like to offer help but prefers to avoid the slog
through the design recipe below,  here's my final version of function
insert-everywhere/in-all-words -

;;insert-everywhere/in-all-words : s low > low
;; produces a list-of-words which inserts s into the beginning, middle
and end of each word contained in the ;;list-of-words
(define (insert-everywhere/in-all-words s low)
	(cond
		[(empty? (rest low))(insert-everywhere/in-one-word s (first low))]
		[else(cons(insert-everywhere/in-one-word s (first low))
			(insert-everywhere/in-all-words s (rest low))]))

;;insert-everywhere/in-one-word: s word > low
;; produces a list-of-words which inserts s into the beginning, middle
and end positions of a single word.
(define(insert-everywhere/in-one-word s word)
	(cond
		[(empty? word)(cons(cons s empty)empty)]
		[else(cons(cons s word)
			(insert-middle-end/in-one-word (cons (first word) empty) s (rest
word)))]))

;; insert-middle-end/in-one-word : b-word s e-word > low
;;produces a list-of-words which appends 'b-word' to the word formed
by (cons s e-word), and then takes the first ;;letter of the e-word,
appends it to b-word, and recurs until e-word is empty.
(define(insert-middle-end/in-one-word b-word s e-word)
	(cond
		[(empty? (e-word))(cons(append b-word (cons s e-word))empty)]
		[else(cons(append b-word (cons s e-word))
			(insert-middle-end/in-one-word
(append b-word (cons (first e-word) empty)) s (rest e-word)))]))

As far as I can tell, the problem starts when insert-everywhere/in-all-
words cons's the result of its else condition onto the result of the
else condition for insert-everywhere/in-one-word.  If I could free the
creation of first word made in the else condition of insert-everywhere/
in-one-word from the recursive call, then it seems my problem would be
solved.  I just can't see how this is possible.  I'm also not sure I
truly understand the proper role of an auxiliary function, and that
the output of insert-everywhere/in-one-word and insert-middle-end/in-
one-word should be something less than a complete list-of-words.
Again, I just can't figure out what that would be.

All comments are appreciated and welcome!

Data Definitions: word and list-of-words

A word  is either
1.	Empty or
2.	(cons s w) where s is a symbol and w is a word

A list-of-words is either
1.	(cons w empty) or
2.	(cons w low) where w is a word and low is a list-of-words

Examples:
(define w1 (cons 'a empty))
(define w2 (cons 'a (cons 't empty)))
(define w2(cons 'a(cons 't(cons 'e empty))))
(define low1 (cons w1 empty)
(define low2 (cons w1(cons  w2 empty))

Design Recipe for 'Insert-everywhere/in-all-words'

;;insert-everywhere/in-all-words : s low > low
;; produces a list-of-words which inserts s into the beginning, middle
and end of each word contained in the ;;list-of-words
(define (insert-everywhere/in-all-words s low)
	(cond
		[(empty? (rest low))(insert-everywhere/in-one-word s (first low))]
		[else(cons(insert-everywhere/in-one-word s (first low))
			(insert-everywhere/in-all-words s (rest low))]))

The first condition tests for an empty list-of words.  According to
the first clause of our data definition, a list-of-words must have at
least one word.  (rest empty) is therefore the only possible test for
empty, and if true signifies there is only one word in the list-of-
words.   That word is peeled off (first low) and sent to wish-list
function insert-everywhere/in-one-word, meant to produce a list-of-
words consisting of words produced by the insertion of s into the
beginning, middle and end positions of the word.

The second condition answers the second clause of data definition for
list-of-words.  It sends the first word of the list to insert-
everywhere/into-one-word, recurs on the rest of list, and cons's the
result together.

;;insert-everywhere/in-one-word: s word > low
;; produces a list-of-words which inserts s into the beginning, middle
and end positions of a single word.
(define(insert-everywhere/in-one-word s word)
	(cond
		[(empty? word)(cons(cons s empty)empty)]
		[else(cons(cons s word)
			(insert-middle-end/in-one-word (cons (first word) empty) s (rest
word)))]))

The first condition tests for the first clause of the word data
definition.  If true it produces a list-of-words consisting of a
single word made from s.

The second condition inserts s onto the beginning of the word,
fulfills the rest of the contract with wish-list function insert-
middle-end/in-one-word and cons's the two together.

;;insert-middle-end/in-one-word : s word > low
;; produces a list-of-words by inserting s into successive middle
positions of the word until it reaches the end of ;;the word
;;(define(insert-middle-end/in-one-word s word)
	(cond....

Under the current header definition, the function would repeat the
steps of the prior function: test for an empty word and if true, make
a list-of-words from s, and then recur on the rest of the word after
making s the word's middle character:
;;(define(insert-middle-end/in-one-word s word)
	(cond
		[(empty? word)(cons(cons s word)empty)]
		[else(cons(cons(first word)(cons s (rest word))
                (insert-middle-end/in-one-word s (rest word))]))

This doesn't work because it won't allow the first part of the word to
build from the recursion.  The only way to preserve the successive
first parts of the word is by turning it into a partial word, or
list--
		[else(cons(cons(begin-word(cons s (rest word))....

That almost works, but since the second argument of cons must be
another list, not a symbol, it fails. To fix that, we turn s into a
word and append the first word to word made from s, and then append
that word to the (rest word), creating a word --
		[else(cons(cons (append(append begin-word (cons s empty))(rest
word)))....

Anyway, that's the line of thought that eventually led to the revised
header, contract statement and function below -

;; insert-middle-end/in-one-word : b-word s e-word > low
;;produces a list-of-words which appends 'b-word' to the word formed
by (cons s e-word), and then takes the first ;;letter of the e-word,
appends it to b-word, and recurs until e-word is empty.
(define(insert-middle-end/in-one-word b-word s e-word)
	(cond
		[(empty? (e-word))(cons(append b-word (cons s e-word))empty)]
		[else(cons(append b-word (cons s e-word))
			(insert-middle-end/in-one-word
(append b-word (cons (first e-word) empty)) s (rest e-word)))]))

The first condition tests if the end of the word passed from (insert-
everywhere/in-one-word) is empty.  If so, it builds a word by first
cons'ing s onto e-word, then appending the resulting word onto b-
word.   A new word with s taking the middle-end position is the
result, fulfilling the function's contract statement for what started
as a 1 letter word passed from insert-everywhere/in-all-words to
insert-everywhere/in-one-word.

Example:
b-word			s	e-word			    Output
(cons 'a empty)     't 	     empty 		>	(cons(cons t'(cons a'
empty))empty)

The second condition repeats the word-building operation of the first.
It also recurs on the rest of e-word, while appending the first letter
of e-word to the end of b-word, and then cons'ing the two together.
The final result is a list-of-words with s inserted into the middle
and end positions of the decomposed word received from insert-
everywhere/in-one-word.

Example:
b-word			s	e-word			        Output
(cons 'a empty)     't 	     (cons 'e empty)	>	(cons(cons 'a(cons
't(cons 'e empty)))
							                (cons(cons 'a(cons 'e(cons 't empty)))empty))

That's it.  Each function works as intended, but when strung together,
produces the Dave's list defined above, which causes arrangements to
blow up.

 I can only offer my thanks in the here-and-now for any help, but
promise that if I make to the afterlife before you, I will not only
put in a good word, but every possible arrangement of that word
provided by this function.  So in addition to everything else, as Bill
Murray's Carl Spackler says, you'll have that going for you....

Cheers,
Dave Yrueta