Building a minimal predicate function by composing Option[predicate] functions in Scala (possibly with scalaz)

Question

I have results in a list that I wish to filter.

The user can supply a specific limit to any of the attributes on a row (e.g., I only want to see the rows where x == 1). If they specify no limit, then of course that predicate is not used. The simplest form of this, of course, is:

list.filter(_.x == 1)

There are many possible simple predicates, and I am building a new predicate function on the fly with code that converts the user search terms (e.g. Option[Int]) into predicate functions or Identity (a function that returns true). The code looks like this (shortened, with explicit types added for clarity):

case class ResultRow(x: Int, y: Int)

object Main extends App {
  // Predicate functions for the specific attributes, along with debug output
  val xMatches = (r: ResultRow, i: Int) => { Console println "match x"; r.x == i }
  val yMatches = (r: ResultRow, i: Int) => { Console println "match y"; r.y == i }
  val Identity = (r : ResultRow) => { Console println "identity"; true }

  def makePredicate(a: Option[Int], b: Option[Int]) : ResultRow => Boolean = {
    // The Identity entry is just in case all the optional params are None 
    // (otherwise, flatten would cause reduce to puke)
    val expr = List(Some(Identity), 
                    a.map(i => xMatches(_: ResultRow, i)),
                    b.map(i => yMatches(_: ResultRow, i))
                   ).flatten

    // Reduce the function list into a single function. 
    // Identity only ever appears on the left...
    expr.reduceLeft((a, b) => (a, b) match {
      case (Identity, f) => f
      case (f, f2) => (r: ResultRow) => f(r) && f2(r)
    })
  }

  val rows = List(ResultRow(1, 2), ResultRow(3, 100))

  Console println rows.filter(makePredicate(Some(1), None))
  Console println rows.filter(makePredicate(None, None))
  Console println rows.filter(makePredicate(None, Some(100)))
  Console println rows.filter(makePredicate(Some(3), Some(100)))
}

This works perfectly. When run, it filters properly, and the debug output proves that the minimal number of functions are called to appropriately filter the list:

match x
match x
List(ResultRow(1,2))
identity
identity
List(ResultRow(1,2), ResultRow(3,100))
match y
match y
List(ResultRow(3,100))
match x
match x
match y
List(ResultRow(3,100))

I am actually very happy with how well this came out.

But, I can't help but think there is a more functional way to do it (e.g. Monoids and Functors and generalized sum)...but I cannot figure out how to make it work.

I tried following a scalaz example that indicated I needed to create an implicit zero and semigroup, but I could not get Zero[ResultRow => Boolean] to type-check.

Answer 1

You can simplify your code a bit (without moving to Scalaz) with the forall method:

def makePredicate(a: Option[Int], b: Option[Int]): ResultRow => Boolean = {
  val expr = List(
    a.map(i => xMatches(_: ResultRow, i)),
    b.map(i => yMatches(_: ResultRow, i))
  ).flatten

  (r: ResultRow) => expr.forall(_(r))
}

Note that this also eliminates the need to include Some(Identity) in the list.

If you have a lot of rows, I'd suggest using zip to match up the xMatches functions with the user input, like this:

val expr = List(a, b) zip List(xMatches, yMatches) flatMap {
  case (maybePred, matcher) => maybePred.map(i => matcher(_: ResultRow, i))
}

It's not really any more concise or readable with two rows, but would be with four or five.

---

To answer your question about Scalaz, the problem is that there are two possible monoids for Boolean, and Scalaz doesn't pick one for you—instead you have to tag your boolean values with something like Haskell's newtype wrapper to indicate which monoid you want to use (in Scalaz 7—in 6 the approach is a little different).

Once you've indicated which monoid you want for Boolean, the monoid for Function1 will kick in, and there's nothing left to do—you don't need to define an Identity zero explicitly. For example:

import scalaz._, Scalaz._

def makePredicate(a: Option[Int], b: Option[Int]): ResultRow => Boolean =
  List(a, b).zip(List(xMatches, yMatches)).flatMap {
    case (maybePred, matcher) =>
      maybePred.map(i => matcher(_: ResultRow, i).conjunction)
  }.suml

Here we've just taken the sum of the ResultRow => Boolean @@ Conjunction functions.