Predicate Composition in Scala

Function composition is a term used to define a process of a function mixing with other functions. During the composition one function holds the reference to another function. 

Scala language has two native ways to compose functions:

• (f compose g) (x), which is equivalent to f(g(x))
• (f andThen g) (x), which is equivalent to g(f(x))

However, as opposed to function composition, predicate composition has its own specifics and rules. Unlike function composition, where one function has a reference of another, predicates are independent; in addition, a predicate always has a return type of Boolean. The composition of predicates follows the laws of Boolean algebra. 

There are three basic Boolean predicates, AND, OR and NOT. The other Boolean predicates can be a composition of these three basic predicates. 

For various reasons, the Scala language does not have a native way to compose predicates as it does for functions. In this article, we present an encoding pattern for predicate composition as compensation to the language design. We demonstrate that our proposed composition is Boolean algebra complete.

Predicate in Scala

A predicate in Scala is a function that takes the following form:

T => Boolean

Which can be presented as:

Function[T, Boolean]

Thus, we define our predicate trait as:

trait Predicate[T] extends Function[T, Boolean]

In Scala, Function is a type alias of Function1[-A,+B] that takes one parameter of type A and returns a type of B. As we can see, Predicate takes a type of T and always return a type of Boolean. 

The three basic predicates, AND, OR, and NOT, can be defined as follows:

trait Predicate[T] extends Function[T, Boolean]{
  def or(p2:Predicate[T]) = OrPredicate[T](this, p2)
  def and(p2:Predicate[T]) =  AndPredicate[T](this, p2)
  def unary_! = NotPredicate[T](this)
}
case class OrPredicate[T](p1:Predicate[T], p2:Predicate[T]) extends Predicate[T] {
  def apply(a:T) = p1(a) || p2(a)
}
case class AndPredicate[T](p1:Predicate[T], p2:Predicate[T]) extends Predicate[T] {
  def apply(a:T) = p1(a) && p2(a)
}
case class NotPredicate[T](p:Predicate[T])  extends Predicate[T] {
  def apply(a:T) = !p(a)
}

As we can see, the predicate is a higher-order function, the function can be composed by its three basic Boolean operations OR, AND, and NOT (unary!)  to yield a new predicate.

Secondary operations, NAND, NOR, and XOR can be a composition of the three basic operations by the end-user, however, they can also be modeled as primitive operations as follows, which we’d like to include in our implementation:

case class NandPredicate[T](p1: Predicate[T], p2: Predicate[T])  {
  def apply(a: T) = !(p1(a) && p2(a))
}
case class NorPredicate[T](p1: Predicate[T], p2: Predicate[T])  {
  def apply(a: T) = !(p1(a) || p2(a))
}
case class XorPredicate[T](p1: Predicate[T], p2: Predicate[T])  {
  def apply(a: T) = (p1(a) || p2(a)) and !(p1(a) && p2(a))
}

In addition, we define the identity predicates for Or and And, which always yields false and true, respectively:

case class TruePredicate[T](r:T) extends Predicate[T] {
   def apply(a: T) = true
}
case class FalsePredicate[T](r:T) extends Predicate[T] {
   def apply(a: T) = false
}

Composition of the Predicates

Once the basic predicates, secondary predicates, and identity predicates are structured, we can define the type classes of our interest. For instance, for type Int:

implicit class IntEqualTo(x:Int) extends Predicate[Int] {
  def apply(a:Int) = a == x
}
implicit class IntGreaterThan(x:Int) extends Predicate[Int] {
  def apply(a:Int) = a > x
}

Composing these predicates can yield more complicated predicates. For instance, greater-than or equal-to Predicate can be composed as:  

IntGreaterThan and IntEqualTo

The predicates are composed into a new predicate without being evaluated, which makes the composition lazy. This can be important in large and complex rule-building and decision-making scenarios.

Completeness of Predicate Composition

Boolean Algebra, also known as Binary Algebra, deals with operations on logical values and incorporates binary variables. A predicate is a statement or mathematical assertion that contains variables, yields a Boolean value. 

Law of Boolean Algebra comprised of the following:

Monotone Laws

Nonmonotone Laws

We demonstrate that our proposed composition satisfies all the laws of Boolean Algebra. The demonstration and a sample implementation can be found at:

Predicate Composition

Conclusion 

In this article, we proposed an encoding pattern for predicate composition in Scala, as compensation for the lack of native support in the language design. We demonstrated that the proposed pattern satisfies the law of Boolean algebra. This pattern can be efficiently used in large-scale application development involving complex predicates, building dynamic rules, and making lazy evaluations in decision making.