**Due by 11:59pm Wednesday, March 24**

- Study the code examples that we discussed in class this week.

The

**flatmap**function is similar to the`map`function, in that it takes a lambda function and a list as inputs, and applies the lambda function to every element of the list. However, we will require that the lambda function provided to`flatmap`must always return a*list*.`Flatmap`then combines all of the results into a single "flat" list containing no inner parentheses. For example:(flatmap (lambda (n) (list n 'anna)) '(1 2 3 4)) => (1 anna 2 anna 3 anna 4 anna)

whereas calling`map`with the same arguments would produce:(map (lambda (n) (list n 'anna)) '(1 2 3 4)) => ((1 anna) (2 anna) (3 anna) (4 anna))

Some further examples are shown below. Write the

`flatmap`function. Hint: Scheme's built-in`append`function, which does the same thing as`concat`from Lab 5, may be useful.(flatmap (lambda (x) (list x x x)) '(a b c)) => (a a a b b b c c c) (flatmap (lambda (x) (cons 'big x)) '((french fries) (pickles) (chili dogs with onions))) => (big french fries big pickles big chili dogs with onions) (flatmap (lambda (x) (reverse x)) '((french fries) (pickles) (chili dogs with onions))) => (fries french pickles onions with dogs chili)

Use your

`flatmap`function as a helper to define the functions**insertL-all**and**insertR-all**(from Lab 5) by filling in the templates below.(define insertL-all (lambda (new old input-list) (flatmap (lambda (x) _______________________ ) input-list))) (define insertR-all (lambda (new old input-list) (flatmap (lambda (x) _______________________ ) input-list))) (insertL-all 'y 'z '(a b c z d z z e)) => (a b c y z d y z y z e) (insertR-all 'y 'z '(a b c z d z z e)) => (a b c z y d z y z y e)

The function

**all-subsets**takes a list of symbols containing no duplicates as input, representing a set*s*, and returns a list of all of the possible*subsets*of*s*, including the empty set and the set*s*itself. The order of the subsets in the returned list does not matter. For example:(all-subsets '(a)) => (() (a)) (all-subsets '(b c)) => (() (b) (c) (b c)) (all-subsets '(a b c)) => (() (b) (c) (b c) (a) (a b) (a c) (a b c))

The empty set

`()`has exactly one subset, namely itself. Therefore, when given the empty set as input,`all-subsets`should return a list*containing*exactly one empty set:(all-subsets '()) => (())

This is the base case. For a non-empty set

*s*such as`(a b c)`, we can remove the car element`a`from*s*and then ask the recursion to generate all of the subsets of the smaller set`(b c)`. That will give us a list containing four subsets:(() (b) (c) (b c))

Next, we need to create four more subsets by cons-ing the element

`a`onto the front of each of the subsets in the above list. This can easily be done by mapping the function`(lambda (x) (cons (car s) x))`across the above list to produce((a) (a b) (a c) (a b c))

Finally, we combine these two lists into a final list containing all eight subsets of

*s*:(() (b) (c) (b c) (a) (a b) (a c) (a b c))

Use this recursive approach to write the function

`all-subsets`. Hints: a`let`expression will make the code more efficient, although it is not strictly necessary. The structure of this problem is similar to the`binary-patterns`function that we wrote in class.

The function

**insert-everywhere**takes a symbol and a list as inputs, and returns a new list of lists, where each inner list is a copy of the original list with the symbol inserted at a different possible position in the list. For example:(insert-everywhere 'z '(b c)) => ((z b c) (b z c) (b c z)) (insert-everywhere 'z '(a b c)) => ((z a b c) (a z b c) (a b z c) (a b c z)) (insert-everywhere 'z '(a)) => ((z a) (a z))

The last example shows the base case, when the input list contains just one element. Suppose we wish to insert

`z`everywhere in the list`(a b c)`. We can remove the first element`a`and then ask the recursion to insert`z`everywhere in the smaller list`(b c)`, which will generate the list of lists((z b c) (b z c) (b c z))

Next, we can easily cons the

`a`onto the front of each of the above lists using`map`, which will give us((a z b c) (a b z c) (a b c z))

This is almost the answer we want, except that we are still missing the list with

`z`inserted at the very front of the original list`(a b c)`, namely:(z a b c)

Adding this fourth list to the above list of lists created by

`map`will give us our final answer:((z a b c) (a z b c) (a b z c) (a b c z))

Use this recursive approach to write the function

`insert-everywhere`.

What if we wanted

**insert-everywhere**to handle the additional base case of inserting a symbol everywhere into an*empty list*? For example, by calling`(insert-everywhere 'z '())`. What would an appropriate answer be in this case? Delete your previous base case for one-element lists and replace it by your new base case for the empty list, and test your function to make sure that it still works for longer lists. Is your code for the new base case simpler than before?

Test cases for this assignment are available in the
file **hw7-tester.scm**. Download this file,
put it in the same folder as your assign7.scm file, and put `(require
"hw7-tester.scm")` at the top of your file. Also make sure that
auto-tester.scm is in the same folder.

An

*anagram*of a sequence of letters is simply a rearrangement of the letters in some new order. For example, "team" is an anagram of the word "mate" (and vice versa). Suppose we wish to write a function called**anagrams**that takes a list of letters as input and generates a new list of all of the possible anagrams of the letters. For example:(anagrams '(e a t)) => ((e a t) (a e t) (a t e) (e t a) (t e a) (t a e))

The base case is straightforward: a sequence of a single letter has exactly one anagram, namely the sequence itself:

(anagrams '(a)) => ((a))

For longer sequences, we can use a recursive approach. For example, to generate the anagrams of

`(a b c)`, we can ask the recursion to generate the anagrams of`(b c)`, which will give the list((b c) (c b))

Next, using

`insert-everywhere`as a helper, we can insert the missing`a`at every position in the list`(b c)`, which will give three anagrams((a b c) (b a c) (b c a))

Likewise, we can insert

`a`at every position in`(c b)`, which will give three more anagrams((a c b) (c a b) (c b a))

Combining these results into a single list will give us all six anagrams of

`(a b c)`:((a b c) (b a c) (b c a) (a c b) (c a b) (c b a))

Use this approach to write the function

`anagrams`. Hint: in addition to`insert-everywhere`, you should also use`flatmap`as a helper function.

In the game of blackjack, face cards (Kings, Queens, and Jacks) count as 10, and Aces can count as either 1 or 11. So a particular hand may have several possible values if Aces are present. For example, the hand

`(king ace)`can sum to either 11 or 21. The hand`(4 10 ace)`can sum to either 15 or 25. The hand`(ace ace)`can sum to 2, 12 (two different ways), or 22. Using the definitions below as your starting point, write the function**(blackjack**, which takes a list of cards representing a hand, and returns a list of all possible values of the hand. The resulting list may contain duplicate values, and the order of the values does not matter. Hint: the structure of this problem is similar to*cards*)`all-subsets`and`binary-patterns`.(define ace? (lambda (card) (equal? card 'ace))) (define face-card? (lambda (card) (or (equal? card 'jack) (equal? card 'queen) (equal? card 'king)))) (define blackjack (lambda (cards) (cond ...))) (blackjack '(ace jack)) => (11 21) (blackjack '(ace ace)) => (2 12 12 22) (blackjack '(4 9)) => (13) (blackjack '(ace ace ace)) => (3 13 13 23 13 23 23 33)

Modify your blackjack function to avoid returning duplicate values. Call your new version

**blackjack2**.(blackjack2 '(ace jack)) => (11 21) (blackjack2 '(ace ace)) => (2 12 22) (blackjack2 '(4 9)) => (13) (blackjack2 '(ace ace ace)) => (3 13 23 33)

Write the function

**car-cdr-code**, which takes a*symbol*and a flat list of symbols named*input-list*as inputs, and returns a piece of Scheme code consisting of the appropriate combination of`car`and`cdr`operations needed to retrieve the first occurrence of*symbol*from*input-list*. You may assume that*symbol*appears somewhere in*input-list*. Hint: define a helper function that constructs the`cdr`'s separately. Examples:(car-cdr-code 'x '(x y z)) => (car input-list) (car-cdr-code 'a '(a b c d e)) => (car input-list) (car-cdr-code 'b '(a b c b b b)) => (car (cdr input-list)) (car-cdr-code 'z '(x y z)) => (car (cdr (cdr input-list))) (car-cdr-code 'c '(a b c d e)) => (car (cdr (cdr input-list))) (car-cdr-code 'd '(a b c d e)) => (car (cdr (cdr (cdr input-list)))) (car-cdr-code 'x '(a a a a x a)) => (car (cdr (cdr (cdr (cdr input-list)))))

Consider the following series of polynomial functions:

*f*_{0}(*x*) = 1

*f*_{1}(*x*) =*x*+ 1

*f*_{2}(*x*) =*x*^{2}+*x*+ 1

*f*_{3}(*x*) =*x*^{3}+*x*^{2}+*x*+ 1

...

*f*_{n}(*x*) =*x*^{n}+*f*_{n-1}(*x*)Write the function

**(poly**, which returns the*n*)*n*th polynomial function in this series. Hints:`poly`should return a*one-argument function*, not a number, for all values of*n*, including*n*=0. We can represent the function*f*_{0}with the lambda expression`(lambda (x) 1)`. The Scheme primitive`(expt x n)`can be used to compute*x*^{n}. Examples:(poly 2) => #<procedure:...> ((poly 2) 2) => 7 ((poly 2) 10) => 111 (poly 3) => #<procedure:...> ((poly 3) 2) => 15 ((poly 3) 10) => 1111 (poly 0) => #<procedure:...> ((poly 0) 2) => 1 ((poly 0) 10) => 1

Save all of your Scheme definitions in a single text file named

**assign7.scm**. Make sure to include your name and the assignment number in a comment at the top of your file. Submit your file using the Homework Upload Site. Please do NOT email your file to me.If you have questions about anything, don't hesitate to ask!