This is in the programming language Scheme.

Consider an implementation of sets with Scheme lists. A set is an unordered collection of elements, without duplicates. (a) Write a recursive function (is-set? L), which determines whether the list L is a set. The following examples illustrate the use of this function: > (is-set?’ (1 2 5)) #t > (is-set?’ (1 5 2 5)) #f (b) Write a recursive function (make – set L), which returns a set built from list L by removing duplicates, if any. Remember that the order of set elements does not matter. The following example illustrates the use of this function: > (make-set’ (4 3 5 3 4 1)) (5 3 4 1) (c) Write a recursive function (subset? A S), which determines whether the set A is a subset of the set S. (d) Write a recursive function (union A B), which returns the union of sets A and B. (e) Write a recursive function (intersection A B), which returns the intersection of sets A and B.

## Expert Answer

**a. Note: is-set? function uses the is-unique? method to find if a list is a set or not.**

(define (is-unique? num L)

(if (null? L)

#t

(if (= num (car L))

#f

(is-unique? num (cdr L)))))

(define (is-set? L)

(if (null? L)

#t

(if (is-unique? (car L) (cdr L))

(is-set? (cdr L))

#f)))

**b.Note: make-set function uses the is-unique? method to find make a list into a set**

(define (is-unique? num L)

(if (null? L)

#t

(if (= num (car L))

#f

(is-unique? num (cdr L)))))

(define (make-set L)

(if (null? L)

L

(if (is-unique? (car L) (cdr L))

(cons (car L) (make-set (cdr L)))

(make-set (cdr L)))))

**c. Note: subset? function uses the is-present? method to find if a list is a subset of the other list.**

(define (is-present? num L)

(if (null? L)

#f

(if (= num (car L))

#t

(is-present? num (cdr L)))))

(define (subset? A S)

(if (null? A)

#t

(if (is-present? (car A) S)

(subset? (cdr A) S)

#f)))

**d. Note: union function uses the make-set function which in turn uses the is-unique method to find the union of two sets**

(define (is-unique? num L)

(if (null? L)

#t

(if (= num (car L))

#f

(is-unique? num (cdr L)))))

(define (make-set L)

(if (null? L)

L

(if (is-unique? (car L) (cdr L))

(cons (car L) (make-set (cdr L)))

(make-set (cdr L)))))

(define (union A B)

(make-set (append A B)))

**e. Note: intersection function uses the is-present function to find the intersection of two sets.**

(define (is-present? num L)

(if (null? L)

#f

(if (= num (car L))

#t

(is-present? num (cdr L)))))

(define (intersection A B)

(if (null? A)

A

(if (is-present? (car A) B)

(cons (car A) (intersection (cdr A) B))

(intersection (cdr A) B))))

Below are the screenshots of output of programs a,b,c,d,e respectively.

Screenshots of the explained code for each function are attached below:

Raw code with explanation for each function:

Note : Explanation is provided in the comments

(define (is-unique? num L)

(if (null? L) ;checking if list is null

#t ;if list is null, that means the num is unique,hecne returning true

(if (= num (car L)) ;if the num is present, then it returns false

#f ;if the num is present, then it is not unique, hence, returning false

(is-unique? num (cdr L))))) ; checking for the num in the rest of the list i.e (cdr list)

(define (is-set? L)

(if (null? L) ;checking if list is null

#t ;if list is null, that means it is a set. Hence returning true.

(if (is-unique? (car L) (cdr L)) ; checking if the first element in the list is not present in the cdr of the list,

(is-set? (cdr L)) ;if the above condition is true,that element is unique and hence checkiing the rest of the set

#f))) ; if that condition fails,that means the element is not unique and it is not a set.

(define (make-set L)

(if (null? L) ;checking if list is null

L ;if list is null, returning the list itself

(if (is-unique? (car L) (cdr L)) ; checking if the first element in the list is not present in the cdr of the list,

(cons (car L) (make-set (cdr L))) ; if the first element in the list is not present in the cdr of the list,that element is unique and hence adding it to the list and calling the make-set on the rest of the list

(make-set (cdr L))))) ;if the first element in the list is not present in the cdr of the list,that element is not unique and hence calling the make-set on the rest of the list

(define (is-present? num L)

(if (null? L) ; checking if list is empty

#f ;if list is empty, returning false

(if (= num (car L)) ; checking if num is present

#t ; if num is present , returning true

(is-present? num (cdr L))))) ; if num is not equal to (car list), checking for it in the (cdr list)

(define (subset? A S)

(if (null? A) ; checking if list is empty

#t ;if list is null, that means it is a subset,hence returning true

(if (is-present? (car A) S) ;checking if (car A) is present in set B

(subset? (cdr A) S) ;if (car A) is present in set B, then checking for thr rest of the A i.e (cdr A)

#f))) ;if (car A) is not present in set B, A is not a subset of B. Hence,returnig false

(define (union A B)

(make-set (append A B))) ;calling the make-set function on the append( A B) Note: append merges A,B into a single list

(define (intersection A B)

(if (null? A) ; checking if list is empty

A ;if list is null, returning the null list itself

(if (is-present? (car A) B) ;checking if (car A) is present in set B

(cons (car A) (intersection (cdr A) B)) ;if (car A) is present in set B, that means it is in both A and B,and hence adding it to the output list and calling the intersection on the rest of the list A

(intersection (cdr A) B)))) ;if (car A) is not present in set B, that means it is not in both A and B,and hence calling the intersection on the rest of the list A