This post is a follow-up to my Stack Overflow question on Combining predicates in Python, but with the focus on Scala. It is also a little warm-up programming exercise for similar techniques I think I'll will learn from the book DSLs in Action by Debasish Ghosh that I recently received as present.

The initial situation is fairly easy. I have a set of predicates that I want to logically combine to create new predicates. A predicate in this context is a function that takes one argument of an arbitrary type and returns a boolean value. The Scala type of a generic predicate would be Any => Boolean. Here are some very simple examples that take integers as input:

val isDivisibleBy13: Int => Boolean = _ % 13 == 0

val isPalindrome: Int => Boolean = x => {
  val s = x.toString
  s == s.reverse
}

Now that I have some predicates to play with, I want to combine them to create a new predicate. E.g. a predicate that tests whether a given integer is a palindrome and is divisible by 13. That's fairly easy:

val isPalindromeAndDivisibleBy13: Int => Boolean = x => {
  isPalindrome(x) && isDivisibleBy13(x)
}

So far so good, but there are two things about this new predicate that I don't like. First, I had to specify the type of the function, which means if the types of the inner predicates change, all compound predicates need to be updated as well. And second, I had to specify the argument x at all although it is only required to be passed to the inner predicates. So the question is: can we do better? Can the compound predicate be written in a point-free style and without specifying its type? Ideally it would look like this:

val isPalindromeAndDivisibleBy13 = isPalindrome && isDivisibleBy13

Such a definition would be concise, expressive, and robust against changes of the inner predicates, since all unnecessary details are hidden. New predicates could then be composed by just connecting any number of predicates with logical operators (like && and ||).

As it turns out, it is indeed possible to combine predicates in Scala as described above by using the Pimp my Library pattern and a little bit of Scala's syntactic sugar. The key ingredients to make this work is a class that is a thin wrapper for predicates and a method to implicitly convert any predicate to an object of that class. Let's start with the wrapper for predicates that I will call Predicate. Here is its full definition:

class Predicate[-A](val pred: A => Boolean) extends (A => Boolean) {
  def apply(x: A) = pred(x)

  def &&(that: A => Boolean) = new Predicate[A](x => pred(x) && that(x))
  def ||(that: A => Boolean) = new Predicate[A](x => pred(x) || that(x))
  def unary_! = new Predicate[A](x => !pred(x))
}

Let me dissect Predicate:

  1. It wraps a predicate of type A => Boolean.
  2. It extends (A => Boolean) (which is syntactic sugar for Function1[A, Boolean]) so that it is itself a predicate of type A => Boolean. That means that instances of Predicate can be used as arguments for its constructor and its other methods that take predicates.
  3. Instances of Predicate are callable via the apply method which just forwards its argument to the wrapped predicate.
  4. It defines the methods && and || that each take another predicate as argument and return a new instance of Predicate constructed with an anonymous predicate that is the composition of the wrapped predicate and the passed argument. The unary_! method is similar but instead of composing two predicates it returns a modified version of the wrapped predicate.

So Predicate is a transparent wrapper for predicates with methods for composing them. The compound predicate can now be written like this:

val isPalindromeAndDivisibleBy13 = Predicate(isPalindrome) && isDivisibleBy13
//           which is the same as: Predicate(isPalindrome).&&(isDivisibleBy13)

The last ingredient to simplify the composition of predicates, and to make my second definition of isPalindromeAndDivisibleBy13 work, is the implicit conversion of predicates to instances of Predicate which is as simple as:

implicit def toPredicate[A](pred: A => Boolean) = new Predicate(pred)

That's it! With Predicate and this implicit conversion, you can now easily combine your predicates. The complete code with some examples is available in predicates.scala.

Further reading:

comment 1
Pretty neat. But is it really worth the overhead in using an implicit? M
Comment by Dominic Bou-Samra
Re: comment 1
That depends on your actual case. How many predicates are combined, how many predicates do you have, and how critical is the code involving them? First and foremost I would write readable and then optimized code.
Comment by fst
comment 3

scala> def a (a: Int): Boolean = true a: (a: Int)Boolean

scala> def b (a: Int): Boolean = false b: (a: Int)Boolean

scala> val c = (d: Int) => a(d) && b(d)

Comment by Anonymous