Csc 4330/6330, Programming Language Concepts (Spring 2022)

Project 2 (Due: 28 April 2020 - Thursday; No Late Submission)

Handin under assignment p2 (Submit just binaryRelation.hs)

BinaryRelationNotes.pdf
binaryRelation.hs (template file with type signatures)
Test Cases

You will complete various functions in the following implementation of the "Binary Relation" data structure.

type Element = (Int,Int)
type BinaryRelation = Element -> Bool
bound = 99

BinaryRelation is set of pairs of integers, each integer is in the range 0 to bound. The choice of 99 as the value of bound is an arbitrary choice. Some examples of binary relations are shown below:

  r1 = { (1,5), (2,8), (3,9) }
  r2 = { (1,2), (2,3), (3,4), (4,5) }

The above notation is for human consumption. Internally, in our implementation, a BinaryRelation is defined as a function from (Int,Int) to Boolean, which indicates whether a given pair of integers is in the binary relation or not.

The binary relation r1 above can be represented by the function that maps (1,5) to True, (2,8) to True, (3,9) to True, and every other pair to False.

Similarly, binary relation r2 can be represented by the function that maps (1,2) to True, (2,3) to True, (3,4) to True, (4,5) to True, and every other pair to False.

Here are the functions that you will have to implement (solutions to a few are given):

-- returns an empty binary relation, i.e. no pairs
emptyBinaryRelation :: BinaryRelation
???

-- returns the universal binary relation, i.e. all pairs
universalBinaryRelation :: BinaryRelation
???

-- returns True of element is in binary relation; False otherwise
contains :: Element -> BinaryRelation -> Bool
???

-- returns a new binary relation obtained by adding element to binary relation; 
-- if element is already in binary relation then returns same binary relation
add :: Element -> BinaryRelation -> BinaryRelation
???

-- returns new binary relation obtained by adding all elements in input list to
-- given binary relation.
addMultiple :: [Element] -> BinaryRelation -> BinaryRelation
???

-- returns True if binary relation 1 is a subset of binary relation 2;
-- False otherwise.
subRelation :: BinaryRelation -> BinaryRelation -> Bool
subRelation r1 r2 = subRelationHelper1 r1 r2 0

subRelationHelper1 :: BinaryRelation -> BinaryRelation -> Int -> Bool
subRelationHelper1 r1 r2 n 
  | n > bound = True
  | otherwise = subRelationHelper2 r1 r2 n 0 && subRelationHelper1 r1 r2 (n+1)

subRelationHelper2 :: BinaryRelation -> BinaryRelation -> Int -> Int-> Bool
subRelationHelper2 r1 r2 n m 
  | m > bound                                    = True
  | contains (n,m) r1 && not (contains (n,m) r2) = False
  | otherwise                                    = subRelationHelper2 r1 r2 n (m+1)

-- returns True if binary relation 1 and binary relation 2 are equal;
-- False otherwise.
equal :: BinaryRelation -> BinaryRelation -> Bool
???

-- for all a, (a,a) is in binary relation
reflexive :: BinaryRelation -> Bool
???

-- returns the union of the two input binary relations
union :: BinaryRelation -> BinaryRelation -> BinaryRelation
???

-- returns inverse of input binary relation; 
-- inverse(r) = { (b,a) | (a,b) in r }
inverse :: BinaryRelation -> BinaryRelation
???

-- returns True if input binary relation is symmetric; False otherwise
symmetric :: BinaryRelation -> Bool
???

-- returns True if input binary relation is anti-symmetric; False otherwise
antiSymmetric :: BinaryRelation -> Bool
???

-- returns True if input binary relation is transitive; False otherwise
transitive :: BinaryRelation -> Bool
???

-- returns True if input binary relation is an equivalence; False otherwise
equivalence :: BinaryRelation -> Bool
equivalence r = reflexive r && symmetric r && transitive r

-- look up definition in BinaryRelationNotes.pdf
reflexiveClosure :: BinaryRelation -> BinaryRelation
???

-- look up definition in BinaryRelationNotes.pdf
symmetricClosure :: BinaryRelation -> BinaryRelation
???

-- selfJoin will be useful in implementing transitiveClosure;
-- returns selfJoin(r) = { (a,c) | (a,b) is in r and (b,c) is in r }
selfJoin :: BinaryRelation -> BinaryRelation
???

-- look up definition in BinaryRelationNotes.pdf
transitiveClosure :: BinaryRelation -> BinaryRelation
???

-- returns String version of binary relation
toString :: BinaryRelation -> String
toString r = show [(x,y) | x <- [0..bound], y <- [0..bound], r (x,y)]