;; ============================ ;; CMPU-145, Spring, 2019 ;; Lab 2 Template ;; 12, February 2019 ;; ============================ #lang racket (include "asmt-helper.scm") (header "Lab 2" "Replace This Text With Your Name") ;; 1A: DISJOINT? ;; ---------------------------------------- ;; Create tester statements to verify that ;; this function works properly. ;; Here, disjoint is already coded. ;; ---------------------------------------- (problem "1A: Disjoint?") ;; DISJOINT? ;; --------------------------------------------- ;; INPUTS: Two lists representing sets ;; OUTPUT: #t if the two sets have no elements in common ;; #f otherwise (define disjoint? (lambda (input-list-1 input-list-2) (cond ;; Base Case: input-list-1 is empty ((null? input-list-1) ;; Empty set is disjoint from every set, including itself ;; Return #t #t) ;; Base Case 2: an element exists in both lists! ;; So, they cannot be disjoint. Return #f ((member (first input-list-1) input-list-2) #f) ;; Recursive Case: continue the search (else (disjoint? (rest input-list-1) input-list-2)) ))) ;; --------------------------------------------- ;; Add your tester test cases here. ;; 1B: BOOLEAN-DISJOINT? ;; ---------------------------------------- ;; Using boolean operations, determine if ;; two sets are disjoing, as above. ;; ---------------------------------------- (problem "1B: boolean-disjoin?") ;; BOOLEAN-DISJOINT? ;; --------------------------------------------- ;; INPUTS: Two input lists representing sets ;; OUTPUT: #t if the two sets have no elements in common ;; #f otherwise (define boolean-disjoint? (lambda (input-list-1 input-list-2) ;; The two sets are disjoint if ;; (input-list-1 is empty OR ;; (the first element of input-list1 is not in input-list2 AND ;; (the rest of the elements in input-list1 are not in input-list2) ;; )) )) ;; --------------------------------------------- ;; Add your tester test cases here. ;; Super-easy, barely an inconvenience. You wrote them already! ;; 2: RANGE of a binary relation ;; ---------------------------------------- (problem "2: Range") ;; In one of our earlier labs, we attempted to create a set ;; intersection without creating duplicates in the logic. ;; One way to implement a range function is to collect all of ;; the b's in all pairs (a,b) and *then* account for duplicates. ;; The b's would be the second element in an ordered pair. So... ;; Before creating a range function, we will create a function ;; to remove duplicates from a set... a helper function. ;; ;; How do we collect all of the second elements in an ordered pair? ;; If only there was a function that could be applied to every ;; element in a list... ;; remove-duplicates -- helper function for RANGE ;; --------------------------------------------- ;; INPUT: input-list, a list of items ;; OUTPUT: Same as input-list, except that duplicate occurrences of ;; items are not included ;; to think about: ;; base case - if the input list is empty, what should we do? ;; recursive case 1: say the first element is a dupe, should we keep it? ;; case 2: say the first element is unique, should we keep it? (define remove-duplicates (lambda (input-list) (cond ))) ;; RANGE -- not a recursive function! ;; ------------------------------------ ;; INPUT: PAIRS, a list of pairs representing a binary relation ;; OUTPUT: A list representing the range of the input relation (define range ) (tester '(range '((1 2) (1 3) (1 4) (2 3) (2 4) (3 5) (3 1) (1 6)))) (problem "3: Inverse, or what Makinson calls Converse") ;; In our earlier lecture, we devised a diy reverse function and a ;; wrapper function for a nicer user interface to it. ;; Let's use that diy reverse function (make sure you test it) ;; to do the work for the inverse function. ;; diy-reverse-v2 ;; ------------------------------- ;; INPUT: Two lists, the second one is, preferrably, the empty list ;; OUTPUT: A single list in reverse order ;; diy-reverse-v2 is an internal function only meant to be called ;; by a wrapper ;; diy-reverse ;; ------------------------------- ;; INPUT: A list in a particular order ;; OUTPUT: The list in reverse order ;; diy-reverse is both a helper function for inverse and a wrapper function ;; for diy-reverse2 (tester '(diy-reverse-v2 '(1 2) '() )) (tester '(diy-reverse-v2 '(1 2 3) '() )) (tester '(diy-reverse '(1 2 3) )) ;; INVERSE ;; ------------------------------- ;; INPUT: PAIRS, a list of pairs representing a binary relation ;; OUTPUT: A list of pairs representing the inverse of that relation ;; Be sure to use our diy reverse function! ;; BTW, What is the other function we want to use? (define inverse ) (tester '(inverse '((1 2) (1 3) (1 4) (2 3) (2 4)))) (tester '(inverse '())) (tester '(inverse '((1 a) (1 b) (1 c) (2 b) (2 e) (1 f) (1 g))))