Laboratory 2

Email solutions and evidence of testing for:

1. Suppose we want to use lists to represent sets. Order and repetition are not important in sets, that is, the set {1, 2, 3} is equal to the set {3, 2, 1} is equal to the set {2, 2, 1, 3}. On the other hand, each of the lists '(1 2 3) , '(3 2 1) , and '(2 2 1 3) are distinct as lists so the built-in equal? predicate will show them unequal. Your task is to define a setequal? predicate that will return #t if two lists (given as arguments) are equal as sets and return false if the two lists are not equal as sets.

   Hint 1: The sets, A and B are equal if A is contained in B and B is contained in A, where set containment is defined: X is contained in Y if every element of X is a member of Y. Earlier, we wrote a predicate memb? that would determine if a single element was a member of a list. It would be worth looking at this definition again. We ought to be able to define a predicate "contains?" that takes two lists as arguments and returns #t if the first argument is contained in the second when they are viewed as sets and returns #f if they are unequal as sets. Think about this.
   Hint2 (for contains?): A predicate that calls itself is reasonable here.
   You need a stopping condition. If A is empty (determined by the built-in predicate null?), then A is certainly contained in B.
   If the first element of A is not in B then A is certainly NOT contained in B.
   If the first element of A is in B, then A is contained in B if the rest of A is contained in B.

2. Text page 60, ex1.30
3. Text page 61, ex1.32a (use to make sum and product and test your new sum and product on some examples from SICP).
4. Write a function called "collapse-first-pair" which locates the first time that the same symbol appears twice in a row and removes one of them. Be sure to add your own test cases to the one case I am providing you with. ;; Test case: ; (collapse-first-pair '(a b c d c c d d)) ; => (a b c d c d d)
5. Write a function called "collapse-all-pairs" which collapses all pairs found in a list. It should not use the collapse-first-pair function you wrote above as part of the solution. ;; Test case: ;(collapse-all-pairs '(a b b b c c c d d e f f)) ; => (a b c d e f)
6. Write a function called sum-list that takes a list of numbers lst and returns the sum of all the numbers in lst. Return 0 if the list is empty. Do this so that your program generates a recursive process. ;; Test cases: ; (sum-list '(1 0 2 -1 3)) ;; => 5 ; (sum-list '()) ;; => 0
7. Rewrite the sum-list function to generate an iterative process solution. This new version should be called sum-list-i
8. Write a function called swap that takes a symbol x, a symbol y, and a list and returns a new list with all occurrences of x replaced by y and all occurrences of y replaced by x. Do this so that your program generates a recursive process. ;; Test case: ; (swap 'red 'blue '(red fish blue fish red)) ;; => (blue fish red fish blue)
9. Rewrite the swap function from to generate an iterative process solution. This new version should be called swap-i