A predicate, or more precisely a predicate functor, is a Boolean-valued function. It is often a unary function, checking one argument against a condition and returning the result. Disregarding functions depending on side effects, there are two nullary functions (without arguments).
public static class Predicate
{
Func<bool> True()
{
return () => true;
}
Func<bool> False()
{
return () => false;
}
}
Listing 1: Nullary predicate functions
It is rare to need these functions in C#, but I sometimes use them when combining functions. I used methods rather than properties since the same function exists in other arities (number of arguments). You can create a single delegate that takes any number of parameters using the params keyword, but its usage is limited since the arguments must be the same type. The best way to obtain True or False predicates with different shapes is through method overloading.
public static Func<T, bool> True<T>()
{
return a => true;
}
public static Func<T, T2, bool> True<T, T2>()
{
return (a, b) => true;
}
Listing 2: Predicates with a fixed return value
Composing Predicates
I'm going to define two predicates specifying a particular rule for an Employee class.
Func<Employee, bool> isActiveEmployee = e => e.DateFired == null;
Func<Employee, bool> isNewEmployee = e => e.DateHired >= DateTime.Today.AddDays(-90);
Listing 3: Predicates accepting an Employee instance
If you're using LINQ to filter a list of employees by both of these functions, there are a few ways to approach it. One should avoid writing another function containing the logic of the other functions since code duplication is difficult to maintain. One way is to chain multiple Where methods.
result = employees.Where(isActiveEmployee).Where(isNewEmployee);
Listing 4: LINQ method chaining
Another technique involves composing the functions into another function, allowing only one call to Where.
result = employees.Where(e => isActiveEmployee(e) && isNewEmployee(e));
Listing 5: Composed predicates
You can also name the composed function and reuse it, potentially reducing duplicate code and making it available for compositions that are more complex.
Func<Employee, bool> isNewAndSurvived = e => isActiveEmployee(e) && isNewEmployee(e);
result = employees.Where(isNewAndSurvived);
Listing 6: Named predicate using composition
Abstracting to Combinators
Unfortunately, the compositional approach to predicates still leads to code duplication, just on a smaller scale. Abstracting and naming the logic is simple and provides other benefits: 1) reduces characters from the lambdas, 2) logic is explicitly named, and 3) it works with implicit typing. Functional composition can be abstracted using functional combinators.
A function combinator does exactly what one might think: it combines functions. A predicate combinator is more specific: it combines predicates (surprised?). Here are the three most common predicate combinators.
public static Func<T, bool> Not<T>(this Func<T, bool> predicate)
{
return a => !predicate(a);
}
public static Func<T, bool> And<T>(this Func<T, bool> left, Func<T, bool> right)
{
return a => left(a) && right(a);
}
public static Func<T, bool> Or<T>(this Func<T, bool> left, Func<T, bool> right)
{
return a => left(a) || right(a);
}
Listing 7: Three common predicate combinators
The And method's lambda expression is nearly identical to the last composition example. To create it, I simply extracted what changes (the inner functions) and made them arguments into the new method. I then added the this keyword to make the method an extension to the first argument so it reads more like English.
You can now define the composed function from the previous section with implicit typing and without a lambda expression.
var isNewAndSurvived = isActiveEmployee.And(isNewEmployee);
Listing 8: Usage of predicate combinator extension methods
Predicate Combinators for Expression Trees
You shouldn't use the above technique for lambdas used in LINQ to Entities or any other variant of LINQ using expression trees. Lambda expressions compile to either delegates or expression trees. Assuming you're using the standard System.Linq, attempting to a delegate to an IQueryable<T> ends up referencing LINQ to Objects. This can cause the program to pull entire tables from the database for in-memory processing.
Combining expression trees is much more involved, but the payoff is much greater. Since functional composition techniques won't work with expression trees, duplication occurs far more often.
Creating the Not combinator is easy enough.
public static Expression<Func<T, bool>> Not<T>(this Expression<Func<T, bool>> predicate)
{
return Expression.Lambda<Func<T, bool>>(Expression.Not(predicate.Body), predicate.Parameters);
}
Listing 9: The Not expression tree combinator
Copy the signature from the function version of Not, then wrap the Func declarations with Expression<>. There's already an Expression.Not method, but it returns a UnaryExpression operating on the predicates' body. To return Expression<Func<T, bool>>, call the Expression.Lambda<Func<T, bool>> method ing the flipped predicate's body and the predicate's parameters.
Combinators operating on two variable predicates are a little more difficult. One might expect it to look like this.
public static Expression<Func<T, bool>> And<T>(this Expression<Func<T, bool>> left, Expression<Func<T, bool>> right)
{
return Expression.Lambda<Func<T, bool>>(Expression.AndAlso(left.Body, right.Body), left.Parameters);
}
Listing 10: Incorrect implementation of binary, expression tree, predicate combinators
Unfortunately, the two predicates don't share parameters, and it will require an expression visitor to change all references to a particular parameter.
The Replace Parameter Visitor
Get started by creating a class that inherits ExpressionVisitor. The class only needs to override the necessary Visit methods. The base Visit method walks the expression, calls each specific Visit method, then returns a new Expression with changes.
The class will need to know two things: the parameter expression and its replacement. It doesn't need to be another parameter expression; this visitor can apply another expression to a parameter the required number of arguments.
This visitor makes changes in the VisitParameter method. I use a generic Visit method to create the expected lambda expression, primarily to streamline the calling code.
public class ReplaceParameterVisitor<TResult> : ExpressionVisitor
{
private readonly ParameterExpression parameter;
private readonly Expression replacement;
public ReplaceParameterVisitor(ParameterExpression parameter, Expression replacement)
{
this.parameter = parameter;
this.replacement = replacement;
}
public Expression<TResult> Visit<T>(Expression<T> node)
{
var parameters = node.Parameters.Where(p => p != parameter);
return Expression.Lambda<TResult>(Visit(node.Body), parameters);
}
protected override Expression VisitParameter(ParameterExpression node)
{
return node == parameter ? replacement : base.VisitParameter(node);
}
}
Listing 11: Visitor implementation
I use the visitor in a private extension method of the Predicate class called WithParametersOf.
private static Expression<Func<TResult>> WithParametersOf<T, TResult>(this Expression<Func<T, TResult>> left, Expression<Func<T, TResult>> right)
{
return new ReplaceParameterVisitor<Func<TResult>>(left.Parameters[0], right.Parameters[0]).Visit(left);
}
Listing 12: A private extension to encapsulate the ReplaceParameterVisitor usage
The method returns an expression with only the function's result since it no longer has its own parameters.
public static Expression<Func<T, bool>> And<T>(this Expression<Func<T, bool>> left, Expression<Func<T, bool>> right)
{
return Expression.Lambda<Func<T, bool>>(Expression.AndAlso(left.Body, right.WithParametersOf(left).Body), left.Parameters);
}
public static Expression<Func<T, bool>> Or<T>(this Expression<Func<T, bool>> left, Expression<Func<T, bool>> right)
{
return Expression.Lambda<Func<T, bool>>(Expression.OrElse(left.Body, right.WithParametersOf(left).Body), left.Parameters);
}
Listing 13: Working implementation of binary, expression tree, predicate combinators using a visitor
The binary expression tree combinators in Listing 13 are now functional.
Conclusion
Both predicates and combinators are powerful tools in your coding arsenal. Predicates are unavoidable in modern C# development, but combinators may seem daunting when first encountered. Even if you do not wish to use them in your active projects, understanding them will make it easy to solve certain hard problems. It's worth learning.
If you're having trouble with these concepts, please refer to the attached code. I've included unit tests proving each piece works and the project is a console application if you prefer to code and run it yourself.
Exercises
Here are a few exercises to improve your C# skills. Check your work with unit tests.
Exercise 1: Predicate<T>
Before the generic Func classes were included in .NET, there was another generic delegate type to represent conditionals: Predicate<T>. Write combinators for it.
Exercise 2: Additional Arguments
I wrote extensions for the three standard predicate combinators, but only for predicates with up to two arguments. Write combinators for ternary (three-argument) predicates.
Exercise 3: Apply an Argument
There are times when a predicate's argument is known. Instead of ing both the predicate and its argument, go ahead and set it. I like to create methods named Apply to implement this technique, known as partial application. The returned predicate should have one less argument. Write the combinators performing partial application.
Exercise 4: Exclusive Disjunction
Not, And, and Or are the most common Boolean operators, but others exist. Implement combinators for Exclusive Disjunction, also known as Xor.
Hint: it should return true only if the left and right predicates have different values.
Vocabulary
This is a quick reference to some of the terms used in the article and some extras for fun. Be aware that some of these terms have different meanings in different contexts.
- Arity: the number of arguments to a function.
- Expression tree: a tree-like data structure representing code.
- Function composition: the act of composing a function with other functions.
- Function combinator: a function-valued function with function arguments.
- Functor: a function that maps from one type of value to another.
- Higher-order function: a function that either returns a function or accepts functions as arguments.
- Predicate: a Boolean-valued function.
- Pure function: a function that neither causes nor is affected by side effects.
- Side effect: a change in a program's state.
- Visitor: a design pattern for separating an algorithm and the structure on which it operators.
Arity Table
| Number of arguments |
Name |
| 0 |
nullary |
| 1 |
unary |
| 2 |
binary |
| 3 |
ternary |
| 4 |
quaternary |
| 5 |
quinary |
| 6 |
senary |
| 7 |
septenary |
| 8 |
octary |
| 9 |
nonary |
| 2+ |
multary |
| n |
n-ary |
Implications
A function combinator is a higher-order function whose arity is greater than zero.
A function combinator does not necessarily combine functions.
A pure function must return the same result on separate calls with identical arguments.
A nullary pure function will always return the same result.
A unary predicate is a Boolean-valued functor.