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).
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.
Composing Predicates
I'm going to define two predicates specifying a particular rule for an Employee
class.
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.
Another technique involves composing the functions into another function, allowing only one call to Where
.
You can also name the composed function and reuse it, potentially reducing duplicate code and making it available for compositions that are more complex.
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.
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.
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.
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.
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.
I use the visitor in a private extension method of the Predicate class called WithParametersOf.
The method returns an expression with only the function's result since it no longer has its own parameters.
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.