Properties of relations, done in Scala

I am currently reading "Elements of Distributed Computing". In order to eventually explain different models for distributed computing, they start with introducing the notion of total order and partial order. A relation defines a reflexive partial order if its reflexive, antisymmetric and transitive.

If X is a set of things, then a relation R over X is a subset of X * X. For example, let

scala> val X = Set('a, 'b, 'c)
X: scala.collection.immutable.Set[Symbol] = Set('a, 'b, 'c)

Then, one possible relation is:

scala> val R = Set(('a, 'c), ('a, 'a), ('b, 'c'), ('c, 'a))
R: scala.collection.immutable.Set[(Symbol, Any)] = Set(('a,'c), ('a,'a), ('b,c), ('c,'a))

A relation is reflexive if for each x belonging to X, (x, x) belongs to R. How would you check if a relation is reflexive in Scala? The trouble is, with the "natural" way of defining a relation as a Set of tuples in Scala, there is no way of telling which values are part of X, just like that. However, if the relation is completely defined by all values in R, then we can determine the values in X simply by combining the values in the domain (the first value in the tuple) and the domain (the second value in the tuple).

If X is not provided than we need a way to derive X from R. In order to get there, I am going to write two functions:

scala> def toSet[T](xs: (T, T)): Set[T] = Set(xs._1, xs._2)  
toSet: [T](xs: (T, T))Set[T]

scala> def domainAndRangeOf[T](xs: Set[(T, T)]): Set[T] = xs flatMap(toSet) 
domainAndRangeOf: [T](xs: Set[(T, T)])Set[T]

So, the set on which the binary relation R is defined is:

scala> val X = domainAndRangeOf(R)                                         
X: Set[Symbol] = Set('a, 'c, 'b)

A relation is reflexive if x R x for all x in X.

scala> def isReflexive[T](xs: Set[(T, T)]): Boolean = 
  domainAndRangeOf(xs) forall(x => xs contains (x, x))
isReflexive: [T](xs: Set[(T, T)])Boolean

scala> isReflexive(Set((1, 1), (1, 2), (2,2)))        
res17: Boolean = true

A relation is antisymmetric if for x, y for which x R y there is no y R x.

scala> def flip[T](t: (T,T)) = (t._2, t._1)                                                             
flip: [T](t: (T, T))(T, T)

scala> def isAntiSymmetric[T](xs: Set[(T,T)]): Boolean = 
  xs forall (x => x == flip(x) || !(xs contains flip(x)))
isAntiSymmetric: [T](xs: Set[(T, T)])Boolean

scala> isAntiSymmetric(Set((1, 2), (1, 3), (1, 4)))
res19: Boolean = true

scala> isAntiSymmetric(Set((1, 2), (1, 3), (2, 1)))
res20: Boolean = false

A relation is transitive if for all x, y, z for with x R y and y R z, x R z is also defined.

scala> def isTransitive[T](xs: Set[(T,T)]) = {
     |   xs forall { x =>
     |     xs filter(y => y._1 == x._2) forall (y => xs contains ((x._1, y._2)))
     |   }
     | }
isTransitive: [T](xs: Set[(T, T)])Boolean

scala> isTransitive(Set((1, 2), (2, 3)))
res21: Boolean = false

scala> isTransitive(Set((1, 2), (2, 3), (1, 3)))
res22: Boolean = true

A relation R defines a reflexive partial order if it is both reflexive, transitive and antisymmetric:

scala> def isReflexivePartialOrder[T](xs: Set[(T,T)]): Boolean = 
     | isReflexive(xs) && isTransitive(xs) && isAntiSymmetric(xs)

scala> isReflexivePartialOrder(Set((1, 2), (1, 4), (2, 4), (1, 1), (2, 2), (4, 4)))
res31: Boolean = true