Principles of Programming Languages — Homework 4

Due by class time Tuesday, September 21

Reading

Exercises

  1. Write the function (double sym ls), which takes a symbol sym and a list ls and "doubles" all of the sym's in ls. Examples:

    (double 'hot '())  =>  ()
(double 'hot '(texas hot chili))  =>  (texas hot hot chili)
(double 'fish '(one fish two fish))  =>  (one fish fish two fish fish)
(double 'double '(double toil and trouble)) => (double double toil and trouble)

  2. Write the function (remove-duplicates ls), which takes a list ls of symbols and removes all of the duplicate elements. The ordering of elements in the resulting list does not matter. Hint: define and use member? as a helper function. Examples:

    (remove-duplicates '(a b c c b d))  =>  (a b c d)
(remove-duplicates '(a a a a))  =>  (a)
(remove-duplicates '(a b a b b b a))  =>  (a b)
(remove-duplicates '(x y z))  => (x y z)

  3. Write the function (swap sym1 sym2 ls), which swaps all occurrences of the symbols sym1 and sym2 within a list ls of symbols. Examples:

    (swap 'red 'blue '(red fish blue fish))  =>  (blue fish red fish)
(swap 'orange 'blue '(red fish blue fish))  =>  (red fish orange fish)
(swap 'blue 'orange '(red fish blue fish))  =>  (red fish orange fish)
(swap 'spam 'ham '(green eggs and ham))  =>  (green eggs and spam)
(swap 'eggs 'ham '(green eggs and ham and eggs))  =>  (green ham and eggs and ham)

  4. Write the function (pair-up a set), which takes an element a and a set (a list containing no duplicate elements), and returns a new list consisting of a paired up with each element of set, where each "pair" is a list. Examples:

    (pair-up 'x '(a b c d)) => ((x a) (x b) (x c) (x d))
(pair-up 'fish '(one two three)) => ((fish one) (fish two) (fish three))
(pair-up 'hee '(hee)) => ((hee hee))

  5. Write the function (cross-product set1 set2), which takes two sets (lists containing no duplicates) and returns all elements from set1 paired up with all elements from set2. Hints: use pair-up as a helper function. Scheme's built-in append function may also be useful, which does the same thing as concat. Examples:

    (cross-product '(a b c) '(1 2)) => ((a 1) (a 2) (b 1) (b 2) (c 1) (c 2))
(cross-product '(a b c) '()) => ()
(cross-product '() '(a b c)) => ()

  6. Write the function (zip ls1 ls2), which takes two lists of the same length and forms a new list by combining the corresponding elements of ls1 and ls2 into "pairs". Examples:

    (zip '(1 2 3) '(a b c))  =>  ((1 a) (2 b) (3 c))
(zip '(a) '(b))  => ((a b))

  7. Write the function (wrap n x), which takes a number n and an item x and wraps n sets of parentheses around x. Examples:

    (wrap 0 'banana) => banana
(wrap 1 'surprise) => (surprise)
(wrap 3 'apple) => (((apple)))

  8. Write the function (wrap-all ls), which takes a list ls and wraps parentheses around each top-level element of ls. Examples:

    (wrap-all '(1 2 3)) => ((1) (2) (3))
(wrap-all '((a) (fine) (idea))) => (((a)) ((fine)) ((idea)))
(wrap-all '(a (more (complicated)) object)) => ((a) ((more (complicated))) (object))

  9. Write function (unwrap-all ls), which takes a list ls and removes parentheses from around each top-level element of ls. If a top-level element is not a list, it is included in the result, as is. The built-in function list? can be used to test if an object is a list. Note: (unwrap-all (wrap-all ls)) is equivalent to ls, but (wrap-all (unwrap-all ls)) is not necessarily the same as ls. Examples:

    (unwrap-all '((1 2) (3 4) 5)) => (1 2 3 4 5)
(unwrap-all '((x (y)) z)) => (x (y) z)
(unwrap-all '(() a 2 (()) ())) => (a 2 ())

  10. Write the function (insert num ls), which takes a number num and a list of numbers already in order from smallest to largest, and returns a new list with num inserted in the correct position. Examples:

    (insert 6 '(1 2 3 4 5 7 8))  =>  (1 2 3 4 5 6 7 8)
(insert 2 '(7 9 15))  =>  (2 7 9 15)
(insert 20 '(7 9 15))  =>  (7 9 15 20)

  11. Using insert as a helper function, write the function (sort-nums nums), which takes an unsorted list of numbers and returns a new list in sorted order. Examples:

    (sort-nums '(7 4 6 2 1 9 4))  =>  (1 2 4 4 6 7 9)
(sort-nums '(3 3 3 2 2 1)) => (1 2 2 3 3 3)

  12. Write the function (merge nums1 nums2), which takes two lists of numbers already in sorted order and returns a new list containing all of the numbers in order. Hint: use insert as a helper. Examples:

    (merge '(1 4) '(1 2 8))  =>  (1 1 2 4 8)
(merge '(2 6 7 8 9) '(3 4 7 9))  =>  (2 3 4 6 7 7 8 9 9)

Challenge Problems (optional but highly recommended)

  1. Write the function (cons-code nums), which takes a flat list of numbers and returns a piece of Scheme code consisting of the appropriate cons operations needed to construct nums. You may assume that nums will contain at least one number. Don't forget to quote the empty list in your constructed code! Examples:

    (cons-code '(1 2 3)) => (cons 1 (cons 2 (cons 3 '())))
(cons-code '(5)) => (cons 5 '())
(cons-code '(7 8)) => (cons 7 (cons 8 '()))
(cons-code '(7 3 3 3)) => (cons 7 (cons 3 (cons 3 (cons 3 '()))))

  2. Write the function (car/cdr-code sym ls), which takes a symbol sym and a flat list ls, and returns a piece of Scheme code consisting of the appropriate combination of car and cdr operations needed to retrieve the first occurrence of sym from ls. You may assume that sym appears somewhere in ls. Hint: define a helper function that constructs the cdr's separately. Examples:

    (car/cdr-code 'a '(a b c d e)) => (car ls)
(car/cdr-code 'b '(a b c b b b)) => (car (cdr ls))
(car/cdr-code 'c '(a b c d e)) => (car (cdr (cdr ls)))
(car/cdr-code 'd '(a b c d e)) => (car (cdr (cdr (cdr ls))))

Turning in Your Homework