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

## No comments:

## Post a Comment