Insert symbol between every element in a list (From HtDP book)
can...@gmail.com
I'm just learning Scheme with the book 'How to Design Programs'.
Now in Chapter 12 and I'm trying to figure out the solution for the
extended exercise.
More precisely Exercise 12.4.2, http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-16.html#node_sec_12.4
My attempt looks like this:
(define (insert-everywhere/in-all-words a-symbol a-list)
(cond
[(empty? a-list) (cons a-symbol empty)]
[else (cons
(append (cons a-symbol empty) a-list) (cons
(first a-list)
(insert-everywhere/in-all-words a-symbol (rest a-list))))]))
(insert-everywhere/in-all-words 'c (cons 'a (cons 'b empty)))
> (cons (cons 'c (cons 'a (cons 'b empty))) (cons 'a (cons (cons 'c (cons 'b empty)) (cons 'b (cons 'c empty)))))
As you can see the output is quiet close to the desired, but I can't
think of a way to get it right...
I hope anyone of you guys can help me! Thanks in advance.
Jens Axel Søgaard
Let's see, what's the main point in this section:
Guideline on Wish Lists
Maintain a list of functions that must be developed to complete a
program. Develop each function according to a design recipe.
Exercise 12.4.2. Develop the function
insert-everywhere/in-all-words. It consumes a symbol and a list of
words. The result is a list of words like its second argument, but
with the first argument inserted between all letters and at the
beginning and the end of all words of the second argument.
I WISH you had a function, insert-every-where/in-one-word, which
consumes a symbol and a word. The result is a word with the
first argument inserted between all letters and at the beginning and
the end of all words of the second argument.
In order to write insert-everywhere/in-all-words with
insert-every-where/in-one-word as a helper function,
use your data definition of "list of words" from exercise 12.4.1.
--
Jens Axel Søgaard
can...@gmail.com
> In order to write insert-everywhere/in-all-words with
> insert-every-where/in-one-word as a helper function,
> use your data definition of "list of words" from exercise 12.4.1.
Hi thanks for your responce!
I did use the data definition and template of the previous exercise.
I just feel really stuck right now. Could you give me another hint?
Jens Axel Søgaard
What tests for insert-every-where/in-one-word do you have?
--
Jens Axel Søgaard
can...@gmail.com
(insert-every-where/in-one-word 'c empty)
> (cons 'c empty)
"should be"
(cons 'c empty)
(insert-every-where/in-one-word 'c (cons 'a empty))
> (cons (cons 'c (cons 'a empty)) (cons 'a (cons 'c empty)))
"should be"
(cons (cons 'c (cons 'a empty)) (cons (cons 'a (cons 'c empty))
empty))
(insert-every-where/in-one-word 'c (cons 'a (cons 'b empty)))
> (cons (cons 'c (cons 'a (cons 'b empty))) (cons 'a (cons (cons 'c (cons 'b empty)) (cons 'b (cons 'c empty)))))
"should be"
(cons (cons 'c (cons 'a (cons 'b empty))) (cons (cons 'a (cons 'c
(cons 'b empty))) (cons (cons 'a (cons 'b (cons 'c empty))) empty)))
Thanks for your help!
Jens Axel Søgaard
> On Jul 30, 3:36 pm, Jens Axel Søgaard <use...@soegaard.net> wrote:
>> can...@gmail.com wrote:
>>> On Jul 30, 1:19 pm, Jens Axel Søgaard <use...@soegaard.net> wrote:
>>>> In order to write insert-everywhere/in-all-words with
>>>> insert-every-where/in-one-word as a helper function,
>>>> use your data definition of "list of words" from exercise 12.4.1.
>>> Hi thanks for your responce!
>>> I did use the data definition and template of the previous exercise.
>>> I just feel really stuck right now. Could you give me another hint?
>> What tests for insert-every-where/in-one-word do you have?
The data definition of a WORD is:
A WORD is either
1.
empty, or
2.
(cons a w) where a is a symbol ('a, 'b, ..., 'z) and w is a word.
We need the test cases in order to figure what to do in each case.
> My test cases:
> (insert-every-where/in-one-word 'c empty)
(cons 'c empty)
"should be"
> (cons 'c empty)
That means that the result of
(insert-every-where/in-one-word a-symbol empty)
is the same as the result of
(cons a-symbol empty) .
>> (insert-every-where/in-one-word 'c (cons 'a empty))
> "should be"
> (cons (cons 'c (cons 'a empty))
(cons (cons 'a (cons 'c empty)) empty))
That doesn't look right to me.
Shouldn't that be
(cons 'c (cons a (cons 'c empty))) ?
also known as (list 'c 'a 'c).
> (insert-every-where/in-one-word 'c (cons 'a (cons 'b empty)))
> "should be"
> (cons (cons 'c (cons 'a (cons 'b empty))) (cons (cons 'a (cons 'c
> (cons 'b empty))) (cons (cons 'a (cons 'b (cons 'c empty))) empty)))
Shouldn't that be
(cons 'c (cons 'a (cons 'c (cons 'b (cons 'c empty))))) ?
also known as (list 'c 'a 'c 'b 'c).
Now we need to figure case 2. of the data definition:
(insert-every-where/in-one-word a-symbol (cons a w))
must give the same results as... what?
Can you combine a and the result of
(insert-every-where/in-one-word a-symbol w)
to give you, what you need?
--
Jens Axel Søgaard
can...@gmail.com
> Shouldn't that be
>
> (cons 'c (cons 'a (cons 'c (cons 'b (cons 'c empty))))) ?
>
> also known as (list 'c 'a 'c 'b 'c).
I don't think that's correct, because the final goal is to rearrange a
word
in all possible combinations. So that's a permutation in a permutation
however
you can't just use one of the elements multiple times.
So afaik each new posistion of 'c must result in a new list.
We are dealing with lists of words anyway, because a word is a list
itself, we got lists of lists.
In the book lists of lists look like that:
(cons (cons 'e (cons 'r empty))
(cons (cons 'r (cons 'e empty))
empty)))
So for the 2. Test the output should be something like:
(list (list 'a 'c) (list 'c 'a))
Well I thinks its a damn tricky exercise ;)
Jens Axel Søgaard
You are right, I made the mistake of reading exercise 12.4.1 only,
and misunderstood:
Exercise 12.4.2. Develop the function
insert-everywhere/in-all-words. It consumes a symbol and a list of
words. The result is a list of words like its second argument, but
with the first argument inserted between all letters and at the
beginning and the end of all words of the second argument.
Our insert-everywhere/in-one-word should therefore return a list
of words, in each word the symbols is inserted different places.
Therefore:
(insert-everywhere/in-one-word 'c empty)
should give
(cons (cons 'c empty)
empty)
And
(insert-everywhere/in-one-word 'c (cons 'a empty))
should give
(cons (cons 'c (cons 'a empty))
(cons (cons 'a (cons 'c empty))
empty))
also known as (list (list 'c 'a) (list 'a 'c)) -- just as you wrote.
The next question about case 2. of the data definition
is still important:
(insert-every-where/in-one-word a-symbol (cons a w))
must give the same results as... what?
You need to combine a and the result of
(insert-every-where/in-one-word a-symbol w)
to give you what you need.
In the test case a-symbol is 'c, a is 'a and w is empty.
So how do we combine
(insert-every-where/in-one-word 'c empty)
= (list (list 'c))
with 'a in order to get the wanted result of
(insert-every-where/in-one-word a-symbol (cons a w))
= (cons (cons 'c (cons 'a empty))
(cons (cons 'a (cons 'c empty))
empty))
[It might be easier to see, if you look at the test case
(insert-every-where/in-one-word 'c (cons 'a (cons 'b empty))) ]
--
Jens Axel Søgaard
can...@gmail.com
I can't figure out how to make the recursive call to nest the lists in
the right way.
Jens Axel Søgaard
> Think me stupid, but I just don't get it...
Not at all.
> I can't figure out how to make the recursive call to nest the lists in
> the right way.
Let's see how we can insert 'x in (list 'a 'b 'c).
The final result must be:
(list (list 'x 'a 'b 'c)
(list 'a 'x 'b 'c)
(list 'a 'b 'x 'c)
(list 'a 'b 'c 'x))
The recursive call (insert-everywhere/in-one-word 'x (list 'b 'c))
gives the result:
(list (list 'x 'b 'c)
(list 'b 'x 'c)
(list 'b 'c 'x))
If we to each element of that list conses an 'a we get:
(list (list 'a 'x 'b 'c)
(list 'a 'b 'x 'c)
(list 'a 'b 'c 'x))
Then we just need to the first element (cons 'x (list 'a 'b 'c)).
That is:
(insert-everywhere/in-one-word a-symbol (cons a w))
= (cons (cons a-symbol w) ; the first element
< something that preprends a-symbol to
each element of the list returned by
(insert-everywhere/in-one-word a-symbol w) >
Hope it helps,
--
Jens Axel Søgaard
can...@gmail.com
concept for me),
but I still have problems to implement it in source code.
I tried it like this:
(define (insert-everywhere/in-one-word a-symbol w)
(cond
[(empty? w) (cons a-symbol empty)]
[else
(cons
(cons a-symbol (first w))
(append
(cons (first (first w)) empty) (insert-everywhere/in-one-word a-
symbol (rest w)) (rest (first w))))]))
(insert 'x (cons (cons 'a empty) empty))
= (cons (cons 'x (cons 'a empty)) (cons 'a (cons 'x empty)))
(insert 'x (cons (cons 'a (cons 'b empty)) empty))
= (cons (cons 'x (cons 'a (cons 'b empty))) (cons 'a (cons 'x (cons 'b
empty))))
Unfortunately the output still isn't how it's supposed to be.
Again, thanks for your help.
Jens Axel Søgaard
Let's focus on turning
(list (list 'x 'b 'c)
(list 'b 'x 'c)
(list 'b 'c 'x))
into
(list (list 'a 'x 'b 'c)
(list 'a 'b 'x 'c)
(list 'a 'b 'c 'x))
We must prepend a symbol to each sublist. That task
deserves a helper function. Following the recipe
for list generating functions, we get:
; prepend-symbol : symbol list-of-lists -> list-of-lists
; prepend the symbol to each of the lists in the list
(define (prepend-symbol a-symbol a-list-of-lists)
(cond
[(empty? a-list-of-lists)
empty]
[(cons? a-list-of-lists)
(cons (cons a-symbol (first a-list-of-lists))
(prepend-symbol a-symbol (rest a-list-of-lists)))]))
--
Jens Axel Søgaard
can...@gmail.com
Thank you for your continued help and your fast responces,
I really appreciate that.
I needed to define another helper function, but now I
finally get the right answers. :D
I am more than glad to be able to share some of my first (hopefully
nice) scheme code with whoever reads this ;)
;; prepend-symbol : symbol list-of-lists -> list-of-lists
;; prepend the symbol to each of the lists in the list
(define (prepend-symbol a-symbol a-list-of-lists)
(cond
[(empty? a-list-of-lists)
empty]
[(cons? a-list-of-lists)
(cons (cons a-symbol (first a-list-of-lists))
(prepend-symbol a-symbol (rest a-list-of-lists)))]))
;; insert-everywhere : a-symbol a-list -> list-of-lists
;; insert a-symbol between (and at start/end) every letter.
;; every new position of a-symbol results in a new list
(define (insert-everywhere a-symbol a-list)
(cond
[(or (empty? a-list) (empty? (first a-list))) (cons (cons a-
symbol empty) empty)]
[else
(cons (cons a-symbol (first a-list))
(prepend-symbol
(first (first a-list)) (insert-everywhere a-symbol (cons
(rest (first a-list)) empty))))]))
;; insert-everywhere/in-all-words : a-symbol words -> lists-of-lists
;; call insert-everywhere with single words for it to process and
;; and append all of its produced new words
(define (insert-everywhere/in-all-words a-symbol words)
(cond
[(empty? words) empty]
[else
(append
(insert-everywhere a-symbol (cons (first words) empty))
(insert-everywhere/in-all-words a-symbol (rest words)))]))
;; arrangements : word -> list-of-words
;; to create a list of all rearrangements of the letters in a-word
(define (arrangements a-word)
(cond
[(empty? a-word) (cons empty empty)]
[else (insert-everywhere/in-all-words (first a-word)
(arrangements (rest a-word)))]))
;; Example/Test:
(arrangements (cons 'a (cons 'b (cons 'c empty))))
;; output =
(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))))))
Perhaps there is a simpler way and you would need not as many helper
functions to acomplish this permutation algorithm...
If you have any comments/suggestions/some-other-feedback, I would be
pleased to hear it!
Jens Axel Søgaard
> Thank you for your continued help and your fast responces,
> I really appreciate that.
Thanks.
> I needed to define another helper function, but now I
> finally get the right answers. :D
Helper functions often simplify things considerably.
> Perhaps there is a simpler way and you would need not as many helper
> functions to acomplish this permutation algorithm...
I rather like having many small functions instead of a few large ones.
Reading and understanding a small functions if much easier than
to untangling a large function.
--
Jens Axel Søgaard