;PL HW#2 UNION INTERSECTION AND DIFFERENCE
;b91705034 ¸êºÞ¤T ®}§g»ñ version 0325.01
;***********************************************************
;In this SCHEME program, I use different method from others.
;I didn't sort these sets because the parentheses are too noisy......
;To count the number of parentheses is really hard
;METHOD:
;In this program, there are some sub-functions except from union intersection and difference
; 1.(isthesame a x), where a is an element and x is a set. this function takes two parameters and judge
; if a is in x...return true or false(boolean)
; 2.(singalize x), where parameter x is a set. this function is to remove the duplicated elements
; to "normalize" this set(normalize: 1 1 2 2 4 5->1 2 4 5 )
; 3.function union,intersection and difference.
;***********************************************************
;function isthesame
(define (isthesame a x)
(cond ( (null? x) #f ) ;if set x is null, a will not be in x, return false
( (null? a) #f ) ;if element a is null, a will not be in x, return false
( (= a (car x)) #t ) ;take elements in x, one by one(from head), to compare with a,
( else ( isthesame a (cdr x))) ;if head x=a, return true; else ,take next one to compare
)) ;till the end of x(then by cond 1, return false)
;***********************************************************
;function (singalize x):to remove duplicated items in set x
(define (singalize x)
(cond ( (null? x) () ) ;if x is null, it is singalized...return ()
( (isthesame (car x) (cdr x)) (singalize (cdr x)) ) ;take items from head of x, one by one, to compare with
( else (cons (car x) ( singalize (cdr x) ) )) ;the rest of the set,
)); ;when meet duplicated value: ignore this head value(since there is another one is the sublist)
;if there is no duplicated value in the sublist:
;*********************************************************** ;put this value in the list
;function (pre_union x y):to find the union set of set x and y
(define (pre_union x y)
(cond ( (null? x) y ) ;if any of these two sets are null,
( (null? y) x ) ;the answer is the other one
( (isthesame (car x) y) (pre_union (cdr x) y) ) ;mtheod: get head of x, one by one, to compare with set y
( else (cons (car x) (pre_union (cdr x) y) )) ;if head x is the same as one of the elements in set y,ignore it(since there is another one in set y)
)); ;else:ignore it and recursive call till the end of set x
;*************************************************************
;function (union x y): since pre_union didn't define the parameter x and y must be singalized, this function defined it
(define (union x y) (pre_union (singalize x) (singalize y) ) ) ;normalize parameter x and y
;*************************************************************
;function pre_intersection: to find the intersection part of set x and y
(define (pre_intersection x y)
(cond ( (null? x) ()) ;if one of the both sets are empty, there is no intersetion list
( (null? y) ()) ;return ()
( (isthesame (car x) y) (cons (car x) (pre_intersection (cdr x) y) ) )
;take head element in x, one by one, to compare with set y, if find same item, put in interseion list
( else ( pre_intersection (cdr x) y)) ;else ignore it and check the next one
))
;*************************************************************
;function intersection x y: same as union, singalize parameter
(define (intersection x y) (pre_intersection (singalize x) (singalize y) ) )
;*************************************************************
;function pre_difference: to find set of x-y
(define
(pre_difference x y) ;take set x as minuend, and y as subtrahen
(cond ;if set x is null, the difference will be null
( (null? x) () ) ;if set y is null, the difference will be x
( (null? y) x ) ;take items one by one from the head of x, if head x has the same value as items in y
( (isthesame (car x) y) (pre_difference (cdr x) y) ) ;then ignore this value, and check next one
( else (cons (car x) (pre_difference (cdr x) y)) ) ;else put this item in difference list, and check next one
))
;*************************************************************
;function difference: as union and intersection, to singalize the parameters
(define (difference x y) (pre_difference (singalize x) (singalize y)) )
;*************************************************************
;test values from assignment
(define a '(1 3 45 62 18 91 10 12 3));
(define b '(11 13 41 18 3 12 91 20));
(define c '(1 41 7 62 91 3));
;test functions
(difference (union a b) c);
(difference (union (intersection a b) (intersection a b)) (intersection a b));