Analysis

CIS447                                                      

Set Union: (setu s1 s2)

cdr-down set s2:

Cases:                                       Return/action

Base case: 1. s2 = Æ                                 s1

Recursive cases:                                 Recursive call to setu

                                                        arg-1         arg-2

2. 1^st of s2 Î s1                        s1                (rest s2)

3. 1^st of s2 Ï s1    cons 1^st of s2 to s1        (rest s2)

Set Difference: (setdf s1 s2)

cdr-down set s1:

Cases:                                               Return/action

Base case: 1. s1 = Æ                                           nil

Recursive cases:                                

                                                                        arg-1         arg-2

2. 1^st of s1 Î s2                                 RCV   (rest s1)       s2

3. 1^st of s1 Ï s2     cons 1^st of s1 to RCV    (rest s1)       s2

Set Intersection: (setint s1 s2)

cdr-down set s1:

Cases:                                               Return/action

Base case: 1. s1 = Æ                                           nil

Recursive cases:                                

                                                                        arg-1         arg-2

2. 1^st of s1 Î s2     cons 1^st of s1 to RCV    (rest s1)       s2

3. 1^st of s1 Ï s2                                 RCV   (rest s1)       s2

Clean: (clean list)

cdr-down list:

Cases:                                               Return/action

Base case: 1. list = Æ                                           nil

Recursive cases:                                

                                                                        arg

2. 1^st of list Î rest of list                     RCV   (rest list)

3. 1^st of list Ï list   cons 1^st of list to RCV   (rest list)

CountUnique Atoms: (cua list)

Can be done without recursion by using two of the functions defined above.

Subset: (subset s1 s2)

Can be done without recursion by using one of the functions defined above.

Sameset: (sameset list-1 list-2)

Can be done without recursion by using one of the functions defined above.

Some Advice:

For building up a new list, using cdr-ing down a list technique.

1. First, ask this question:  Do we build up from a base list or from the empty list?

  A: For all cases except setu, begin with the empty list.

          {I.e., setdf, setint, clean & flatten}

2. Next, ask:  What is the second test (after the empty-list test)?

  A: For setu, setdf, and setint it is a test for the membership of the 1^st element of set1 in set2.  For clean it is a test for the membership of the 1^st element of list in the rest of list.  For flatten we check whether the 1^st element of list is a cons, using the function consp.

3. Finally, ask:  What is the proper action when the second test succeeds and when it fails?

  A: This is determined by the logic of the function we are writing.  Notice that in some cases the proper set of actions for one function is the exact opposite of those for another function.

4. Alphabetical list of functions used in official answer sheet (in addition to those being defined):

1+

+

append

atom

cond

cons

consp

defun

endp

first

length

member [Note: for fclean it is useful to use the feature of member that allows

        you to specify the equality test to be used, as will be discussed in class].

rest