Csc 4330/6330, Programming Language Concepts (Summer 2020)

Project 2 (Due: 30 July 2020 - Thursday; Late Submission: 2 August (Sunday))

Handin under assignment p2 (Submit just BinaryRelation.scala)

BinaryRelationNotes.pdf
BinaryRelation.scala
Driver.scala

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

  type BinaryRelation = (Int,Int) => Boolean
  type Element = (Int,Int)
  val 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):

object BinaryRelation {

  type BinaryRelation = (Int,Int) => Boolean
  type Element = (Int,Int)
  val bound = 99

  // returns an empty binary relation, i.e. no pairs
  def emptyBinaryRelation: BinaryRelation = ???

  // returns the universal binary relation, i.e. all pairs
  def universalBinaryRelation: BinaryRelation = ???

  // returns true of e is in r, false otherwise
  def contains(r: BinaryRelation, e: Element): Boolean = ???

  // returns true if r1 is a subset of r2, false otherwise
  def subRelation(r1: BinaryRelation, r2: BinaryRelation): Boolean = {
    def helper1(x: Int): Boolean = {
      def helper2(y: Int): Boolean = {
        if (y > bound) true
        else if (contains(r1,(x,y)) && !contains(r2,(x,y))) false
        else helper2(y+1)
      }
      if (x > bound) true
      else if (!helper2(0)) false
      else helper1(x+1)
    }
    helper1(0)
  }
  
  // returns true of r1 equals r2, false otherwise
  def equal(r1: BinaryRelation, r2: BinaryRelation): Boolean = ???

  // returns a new binary relation obtained by adding e to r; if e already
  // is in r then returns r
  def add(r: BinaryRelation, e: Element): BinaryRelation = ???

  // for all a, (a,a) is in r
  def reflexive(r: BinaryRelation): Boolean = ???

  // for all a,b, if (a,b) is in r then (b,a) is also in r
  def symmetric(r: BinaryRelation): Boolean = ???

  // for all a,b,c, if (a,b) is in r and (b,c) is in r then (a,c) is also in r
  def transitive(r: BinaryRelation): Boolean = ???

  // equivalence relation is reflexive, symmetric, and transitive
  def equivalence(r: BinaryRelation): Boolean = ???

  // For all a,b, if a != b and (a,b) in r then (b,a) is not in r
  def antisymmetric(r: BinaryRelation): Boolean = ???

  // returns set union of r1 and r2
  def union(r1: BinaryRelation, r2: BinaryRelation): BinaryRelation = ???

  // returns inverse of r; inverse(r) = { (b,a) | (a,b) in r }
  def inverse(r: BinaryRelation): BinaryRelation = ???

  // look up definition in BinaryRelationNotes.pdf
  def reflexiveClosure(r: BinaryRelation): BinaryRelation = ???

  // look up definition in BinaryRelationNotes.pdf
  def symmetricClosure(r: BinaryRelation): BinaryRelation = ???

  // selfJoin will be useful in implementing transitiveClosure
  // returns a new relation { (a,c) | (a,b) is in r and (b,c) is in r }
  def selfJoin(r: BinaryRelation): BinaryRelation = ???

  // look up definition in BinaryRelationNotes.pdf
  def transitiveClosure(r: BinaryRelation): BinaryRelation = ???

  def toString(r: BinaryRelation): String = {
    val rs = for {
      i <- 0 to bound
      j <- 0 to bound
      if contains(r, (i, j)) 
    } yield ((i,j))
    rs.mkString("{", ",", "}")
  }

  def printBinaryRelation(r: BinaryRelation): Unit = {
    println(toString(r))
  }

}