What is a predicate function?
I study C++. In the literature, one of the functions is called predicate. What does this mean, or is it just a translation ?
3 answers
Let's consider such a problem. We have, say, a vector of integers, and we want to display only positive numbers.
How do we do this?
void out(const vector<int>& v)
{
for(auto i: v)
if (i > 0) cout << i << " ";
}
And if you print everything, more than 5?
void out(const vector<int>& v)
{
for(auto i: v)
if (i > 5) cout << i << " ";
}
Looks like it? Yes. So I'm drawn to combine them into
void out(const vector<int>& v, int value)
{
for(auto i: v)
if (i > value) cout << i << " ";
}
But what if we want to output only even numbers? Only those for which the sine is positive?
All this can be summarized, for example, as follows:
void out(const vector<int>& v, bool(*)(int) pred)
{
for(auto i: v)
if (pred(i)) cout << i << " ";
}
Where pred
is a function that checks for some condition, predicate. And only the numbers for which the function pred
returns the value true
will be output. And how we write it is our business. For example,
bool pred(int i) { return i > 5; }
That's basically it. The rest - a function, or a lambda, a template or not, from how many arguments, etc., etc. - is not important. Predicative function-checking a certain condition, predicate, for your (their) argument (s).
Well-predicates are very widely used in algorithms of the standard libraries.
A predicate is a function that returns the type
bool
(or other a value that can be automatically converted tobool
). Predicates are widely used in STL. In particular, comparison functions in standard associative containers are predicates. Predicate functions are often passed as parameters to algorithms such asfind_if
and various sorting algorithms.
Here is a small example.
#include <iostream>
#include <iterator>
template<typename T, typename Cmp>
T* array_move(T* fa, T* la, Cmp cmp){
T* p;
while((fa != la) && cmp(*fa))
++fa;
for(p = fa; fa != la; ++fa){
if(cmp(*fa)){
std::swap(*fa, *p);
++p;
}
}
return p;
}
int main(void){
std::ostream_iterator<int> _out(std::cout, " ");
int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int n = sizeof(a)/sizeof(a[0]);
//переставить в начало массива чётные числа
auto e1 = array_move(a, a + n, [] (int x) {
return ((x & 1) == 0);
});
std::copy(a, e1, _out);
std::cout << std::endl;
//переставить в начало массива только те числа которые кратны трём
auto e2 = array_move(a, a + n, [] (int x){
return ((x % 3) == 0);
});
std::copy(a, e2, _out);
std::cout << std::endl;
//переставить в начало массива только те числа у которых включен 3-ий бит
auto e3 = array_move(a, a + n, [] (int x){
return (((x >> 2) & 1) == 1);
});
std::copy(a, e3, _out);
return 0;
}
And what conclusion can be drawn about a predicate, no matter how it is made by a structure, function, or lambda? And so, a predicate is a condition that is embedded from outside, thereby allowing a function to be more functional compared to functions without predicates. Even the slightest glance at the code is enough to see the advantage of using the predicate, because without it I had to write three different functions to complete the task, and if there are 40 tasks? example move to the beginning of the array:
- prime numbers
- Fibonacci numbers
- odd numbers
- negative numbers
- positive numbers
- numbers that are greater than 100 but less than 500
- numbers with 5-bit enabled
...