Assignment VII: Solution




(2). Common errors:
	In question 2.f, many students failed to give a correct definition
	of function "set-member" for arbitrary sets; the point is that
        membership and equality are mutually recursive, because an element is
        a member of a set if it is equal to some element of that set, and sets
        are equal if the elements of each are members of the other.

In the solution below, we introduce the predicate "subset" (standard mathematical
definition) to define two sets as equal if each is a subset of the other.

**
*************           Scheme Code & Grade Scale
*************************************************************************=
**

Q1. (2 points)
(define (weave list1 list2 list3)
	(cond
  	               ;; If those lists are not equal in length, return '()
  	((or (null? list1) (null? list2) (null? list3)) '())
    (else (map list list1 list2 list3))
  )
)

Q2a. (1 points)
(define (set? l)
	(cond=20
		((not (list? l)) #f)  ;; If l is not a list, it can't be a set
		((null? l) #t)        ;; '() is a set
		((member (car l) (cdr l)) #f) ;; Set can't have duplicates 
		(else
			(set? (cdr l)))       ;; recursive call
	)
)

Q2b. (1 points)
(define (make-set l)
  (cond
    ((null? l) '())									;; '() is itself a set							
    ((member (car l) (cdr l)) 
    	(make-set(cdr l)))	;; remove the duplicate element
    (else 			;; recursive call
    	(cons (car l) (make-set (cdr l))))
  )
)

Q2c. (1 points)
;; This is an auxiliary function for set-equal
;; Check if a set is a subset of another

(define (subset? set1 set2)
	(cond
		((not (set? set1)) #f)	;; not a set, return false
		((not (set? set2)) #f)	;; not a set, return false
		((null? set1) #t)	;; '() is the subset of any set
		((member (car set1) set2) 	;; recursive call
			(subset? (cdr set1) set2))
		(else #f)
	)
)

(define (set-equal set1 set2)
	(cond
           ((or (not (set? set1)) (not (set? set2))) #f);; false if not sets

           ((and (null? set1) (null? set2)) #t)         ;; null sets are equal	

           ((not (eq? (length set1)(length set2))) #f)	;; different sizes
	   (else
              (and (subset? set1 set2) (subset? set2 set1)))))
                      ;; if each one is the subset of the other, equal
		)
	)
)

Q2d. (1 points)

(define (set-intersect set1 set2)
	(cond
            ((or (null? set1) (null? set2)) '())
					;; either one is '(), return '()
            ((member (car set1) set2)	;; find a common element
		(cons (car set1) (set-intersect (cdr set1) set2)));; add rest 
		(else 				;; this element is not common
			(set-intersect (cdr set1) set2))
	)
)


Q2e. (2 points)

;; Auxiliary function for power-set
;; Add a new element to each element of a set of sets
(define (insert_elem elem set)
	(cond
		((null? (cdr set)) (list (list elem)))
		(else
			(cons (cons elem (car set)) (insert_elem elem (cdr set))))
	)
)


(define (power-set set)
	(cond
	((null? (cdr set)) (list set '()))	;; pow {} =>  {{}}

		(else
                  (append (insert_elem (car set) (power-set (cdr set)))
                                                 (power-set (cdr set))))))
          ;; add first  element to each set of (power-set (cdr set))
          ;; and then append this set to (power-set (cdr set))
	)
)

    ;;  note that this computes the power-set twice, which is not
    ;;  the most optimal approach. As usual, we can introduce a
    ;;  small function that allows us to compute this only once:

(define (insert-and-append lis elem) (append lis (insert_elem elem lis)))

    ;;  with this, the last clause can be written as:

    (insert-and-append (car set) (power-set (cdr set)))
	

Q2f. (2 points)

;; The following three functions are defined for arbitrary sets.
;; For purposes of testing, they have to be compiled separately,
;; otherwise, they will override the definitions of "subset?"
;; and "set-equal" on simple sets, given above.

;; Notice: For the following functions, we assume that the parameters
;; are all valid sets; otherwise, we should rewrite
;; function set? for arbitrary sets and use it to test the validity
;; of parameters. This is left as a exercise to the reader.

;; Function set-member for arbitrary sets. Mutually recursive with
;; set equality. Here we have to examine whether an element is a set or
;; an atom to know if we have to recurse.

(define (set-member mem set)
	(cond
	 ((not (list? set)) #f)	;; if value is not a list, it is not a set

	 ((null? set) #f)        ;; the empty set has no members

		;; if mem is atomic, can use predefined function "member"
	 ((not (list? mem)) (member mem set))

	 ((set-equal mem (car set)) #t)	;; mem is a set, use set-equal

         (else (set-member mem (cdr set)));; recursive call
	)
)

;; Auxiliary function for set-equal

(define (subset? set1 set2)
	(cond
	((or (not (list? set1)) (not (list? set2))) #f)	;; if not a list, not a set
        ((null? set1) #t)			;; '() is subset of any set
	((set-member (car set1) set2)		;; find a common element
		(subset? (cdr set1) set2))	;; recursively check the rest
		(else #f)
	)
)

;; Function set-equal for arbitrary sets: mutually recursive with membership,
;;  through auxiliary function subset.

(define (set-equal set1 set2)
	(cond
	  ((or (not (list? set1)) (not (list? set2))) #f)
          ((and (null? set1) (null? set2)) #t)	;; null sets are equal 
	  ((not (eq? (length set1)(length set2))) #f)
	  (else
	    ((and (subset? set1 set2)(subset? set2 set1)) ))
        )
)