Introduction to Functional Programming — Homework 7

Due by 11:59pm Wednesday, March 24

Reading

Programming Exercises

    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.

  1. 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)

  2. 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)

  3. 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.

  4. 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.

  5. 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?

Optional Challenge Problems (Extra Credit)

  1. 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.

  2. 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 cards), 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 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)

  3. 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)

  4. 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)))))

  5. Consider the following series of polynomial functions:

    f0(x) = 1
    f1(x) = x + 1
    f2(x) = x2 + x + 1
    f3(x) = x3 + x2 + x + 1
    ...
    fn(x) = xn + fn-1(x)

    Write the function (poly n), which returns the nth 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 f0 with the lambda expression (lambda (x) 1). The Scheme primitive (expt x n) can be used to compute xn. 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

Turning in Your Homework