Что такое предикат в программировании

Что такое предикат в программировании

На этом шаге мы рассмотрим использование унарных предикатов .

Особую разновидность вспомогательных функций, используемых алгоритмами, составляют предикаты. Предикатом называется функция, которая возвращает логическое значение. С помощью предикатов часто определяют критерии сортировки или поиска. В зависимости от способа применения предикаты делятся на унарные и бинарные . Учтите, что не любая унарная или бинарная функция, возвращающая логическую величину, является действительным предикатом. STL требует, чтобы при неизменности входных данных предикат всегда давал постоянный результат. Тем самым из категории предикатов исключаются функции, внутреннее состояние которых изменяется в процессе вызова.

Унарные предикаты

Унарный предикат проверяет некоторое свойство одного аргумента. Типичный пример — функция, используемая в качестве критерия поиска первого простого числа:

//--------------------------------------------------------------------------- #include #include #include #include #include //необходимо для getch() #include //для abs <)#pragma hdrstop //--------------------------------------------------------------------------- #pragma argsused using namespace std; std::string ToRus(const std::string &in) < char *buff = new char [in.length()+1]; CharToOem(in.c_str(),buff); std::string out(buff); delete [] buff; return out; > // Предикат проверяет, является ли целое число простым bool isPrime (int number) < // Знак числа игнорируется number = abs(number); // 0 и 1 не являются простыми числами if (number == 0 || number == 1) < return false; > // Поиск множителя, на который число делятся без остатка int divisor; for (divisor = number/2; number%divisor != 0; --divisor) < ; >// Если не найдено ни одного множителя, большего 1. // проверяемое число является простым. return divisor == 1; > int main(int argc, char* argv[]) < listcoll; // Вставка элементов со значениями от 24 до 30 for (int i=24; i // Поиск простого числа list::iterator pos; pos = find_if (coll.begin(), coll.end(), // Интервал isPrime); // Предикат if (pos != coll.end()) < // Найдено простое число cout else < // Простые числа не найдены cout cout return 0; > //--------------------------------------------------------------------------- 

Текст этого примера можно взять здесь.

В приведенном примере алгоритм find_if() ищет в заданном интервале первый элемент, для которого передаваемый унарный предикат возвращает true . В качестве предиката передается функция isPrime() , которая проверяет, является ли число простым. В итоге алгоритм возвращает первое простое число в заданном интервале. Если алгоритм не находит ни одного элемента, удовлетворяющего предикату, возвращается конец интервала (второй аргумент). Это условие проверяется после вызова. Коллекция из нашего примера содержит простое число между 24 и 30, поэтому результат выполнения программы выглядит так:

Рис.1. Результат работы приложения

На следующем шаге мы рассмотрим бинарные предикаты .

Что такое предикат в программировании

Объекты-функции – это объекты, у которых перегружен оператор вызова функций operator(). В библиотеке STL уже определено несколько полезных арифметических и других объектов-функций (описание в файле ):

Рассмотрим пример с отрицанием всех элементов вектора. Можно выполнить этот пример с помощью цикла, а можно сделать намного проще с использованием алгоритма transform и стандартной функции negate.

vectorint> v; vectorint>::iterator it=v.begin(); while(it != v.end()) < *it = -(*it); it++; >// то же самое с использованием объекта-функции negate transform(v.begin(),v.end(), v.begin(), negateint>()); // вывод контейнера на экран copy(v.begin(), v.end(), ostream_iteratorint>(cout, " "));

Алгоритмы (описание в файле < algorithm>) позволяют выполнять некоторые типовые действия надо контейнерами с использованием объектов-функций стандартной библиотеки или своих объектов-функций. Подробно алгоритмы, функции, и другие возможности библиотеки STL приводятся в Приложении 5.

Стандартные алгоритмы можно использовать и для ввода и вывод контейнера на экран. При чтении ввод происходит до ввода первого не числового символа.

Программисты могут определить свои объекты-функции, которые могут быть наследниками от стандартных. В объектах-функциях обязательно должен быть перегружен оператор вызова функции (), в конструкторе могут задаваться необходимые параметры, или он может быть пустым (см.пример 6.5).

Функции могут быть двух типов:

• Унарная функция – это функция, в которой участвует один операнд (например, x=-y — унарный минуc)
• Бинарная функция – это функция, в которой участвуют два операнда (например, x=y+z — сложение, умножение, и т.д.)

Для унарных функций перегруженный оператор вызова функции должен содержать один параметр, в бинарных – два параметра.

Иногда нужно преобразовать бинарную функцию в унарную, например умножение – бинарная функция, нужны два элемента, а мы хотим умножить все элементы контейнера на одно и то же число. Для этого можно использовать функцию bind2nd.

Функция binder2nd – преобразует бинарную функцию в унарную, и принимает второй аргумент как параметр бинарной функции (описание в файле )

// умножение каждого элемента на 2 transform (v.begin(), v.end(), v.begin(), bind2nd(multipliesint>(), 2));

Пример 6.5. Использование объектов-функций

///////////////////////////////////////////////////////////////////////////// // Прикладное программирование // Пример 6.5. Использование объектов-функций // // Кафедра Прикладной и компьютерной оптики, http://aco.ifmo.ru // Университет ИТМО ///////////////////////////////////////////////////////////////////////////// #include #include #include #include #include using namespace std; ///////////////////////////////////////////////////////////////////////////// // создание объекта-функции для заполнения случайными числами // функция Rand - шаблон, наследник от стандартной функции unary_function // параметры шаблона: PAR - тип данных, void - возвращаемое значение оператора () template class PAR> class Rand : public unary_functionvoid> < // диапазон случайных чисел PAR m_min, m_max; public: // конструктор, в котором задается диапазон случайных чисел Rand(PAR min, PAR max) : m_min(min), m_max(max) < >// перегруженный оператор вызова функции, в котором число value заполняется случайным числом void operator() (PAR& value) < value=(PAR)(rand()*(m_max-m_min))/RAND_MAX+m_min; >>; ///////////////////////////////////////////////////////////////////////////// // тестирование объектов-функций STL - negate, ввод-вывод void main() < vectorint> v; // чтение контейнера из потока ввода (до первого не числового символа) copy(istream_iteratorint>(cin), istream_iteratorint>(), back_inserter(v)); // вывод контейнера на экран copy(v.begin(), v.end(), ostream_iteratorint>(cout, " ")); cout// использование объекта-функции negate transform(v.begin(),v.end(), v.begin(), negateint>()); copy(v.begin(), v.end(), ostream_iteratorint>(cout, " ")); cout// заполнение контейнера случайными числами при помощи объекта-функции Rand for_each(v.begin(), v.end(), Randint>(-10, 10)); copy(v.begin(), v.end(), ostream_iteratorint>(cout, " ")); cout// умножение каждого элемента на 2, // использование стандартной бинарной функции multiplies, // преобразованной в унарную при помощи функции bind2nd transform (v.begin(), v.end(), v.begin(), bind2nd(multipliesint>(), 2)); copy (v.begin(), v.end(),ostream_iteratorint>(cout, " ")); cout /////////////////////////////////////////////////////////////////////////////

6.4.2. Предикаты. Пример 6.6 (использование предикатов)

Предикаты позволяют без изменения шаблона изменять критерии сравнения элементов контейнера и другие подобные действия. У предикатов объект-функция возвращает значение bool.

В файле уже определено несколько полезных предикатов:

• equal_to бинарный предикат равенства
• not_equal_to бинарный предикат неравенства
• greater бинарный предикат >
• less бинарный предикат < (используется по умолчанию)
• greater_equal бинарный предикат >=
• less_equal бинарный предикат
• logical_and бинарный предикат И
• logical_or бинарный предикат ИЛИ
• logical_not унарный предикат НЕ

Например, стандартный алгоритм сортировки сортирует по возрастанию, если мы хотим сделать сортировку по убыванию – можно использовать предикат greater:

// сортировка в порядке убывания sort(v.begin(), v.end(), greaterint>());

Можно определять свои предикаты, как наследники от стандартных объектов-функций.

Пример 6.6. Использование предикатов

///////////////////////////////////////////////////////////////////////////// // Прикладное программирование // Пример 6.6. Использование предикатов // // Кафедра Прикладной и компьютерной оптики, http://aco.ifmo.ru // Университет ИТМО ///////////////////////////////////////////////////////////////////////////// #include #include #include #include #include #include using namespace std; ///////////////////////////////////////////////////////////////////////////// // создание объекта-функции для заполнения случайными числами // функция Rand - шаблон, наследник от стандартной функции unary_function // параметры шаблона: PAR - тип данных, void - возвращаемое значение оператора () template class PAR> class Rand : public unary_functionvoid> < // диапазон случайных чисел PAR m_min, m_max; public: // конструктор, в котором задается диапазон случайных чисел Rand(PAR min, PAR max) : m_min(min), m_max(max) < >// перегруженный оператор вызова функции, в котором число value заполняется случайным числом void operator() (PAR& value) < value=(PAR)(rand()*(m_max-m_min))/RAND_MAX+m_min; >>; ///////////////////////////////////////////////////////////////////////////// // создание объекта-функции определения попадания числа в диапазон // функция InRange - шаблон, наследник от стандартной функции unary_function // параметры шаблона: int - тип данных, bool - возвращаемое значение оператора () class InRange : public unary_functionint, bool> < // диапазон чисел int m_left, m_right; public: // конструктор, в котором задается диапазон InRange(int left, int right) : m_left(left), m_right(right) <> // перегруженный оператор вызова функции, в котором определяется // попадание числа value в диапазон от m_left до m_right bool operator() (const int& value) < return (value>m_left && value >; ///////////////////////////////////////////////////////////////////////////// // тестирование предикатов void main() < vectorint> v(10); // заполнение контейнера случайными числами при помощи объекта-функции Rand for_each(v.begin(), v.end(), Randint>(-10, 10)); copy(v.begin(), v.end(), ostream_iteratorint>(cout, " ")); cout// сортировка с использованием предиката greater sort(v.begin(), v.end(), greaterint>()); copy(v.begin(), v.end(), ostream_iteratorint>(cout, " ")); cout// использование InRange для подсчета количества элементов в диапазоне от 0 до 10 cout /////////////////////////////////////////////////////////////////////////////

JavaScript: Предикаты

Подобные функции называют предикатами. Функции-предикаты (или функции-вопросы) отвечают на какой-то вопрос и всегда (без исключений!) возвращают либо true , либо false .

Предикаты во всех языках принято именовать особым образом для простоты анализа. В JavaScript предикаты, как правило, начинаются с префикса is , has или can , но не ограничены этими словами. Примеры:

• isInfant() — «младенец ли?»
• hasChildren() — «есть ли дети?»
• isEmpty() — «пустой ли?»
• hasErrors() — «есть ли ошибки?»

Функция может считаться предикатом только если она возвращает boolean.

Давайте напишем ещё одну функцию-предикат. Она принимает строку и проверяет, является ли она словом ‘Castle’ :

const isCastle = (type) => type === 'Castle'; console.log(isCastle('Sea')); 

false

Задание

Напишите функцию isMister() , которая принимает строку и проверяет, является ли она словом ‘Mister’ .

isMister('Mister'); // true isMister('Miss'); // false 

Упражнение не проходит проверку — что делать? ��

Если вы зашли в тупик, то самое время задать вопрос в «Обсуждениях». Как правильно задать вопрос:

• Обязательно приложите вывод тестов, без него практически невозможно понять что не так, даже если вы покажете свой код. Программисты плохо исполняют код в голове, но по полученной ошибке почти всегда понятно, куда смотреть.

В моей среде код работает, а здесь нет ��

Тесты устроены таким образом, что они проверяют решение разными способами и на разных данных. Часто решение работает с одними входными данными, но не работает с другими. Чтобы разобраться с этим моментом, изучите вкладку «Тесты» и внимательно посмотрите на вывод ошибок, в котором есть подсказки.

Мой код отличается от решения учителя ��

Это нормально ��, в программировании одну задачу можно выполнить множеством способов. Если ваш код прошел проверку, то он соответствует условиям задачи.

В редких случаях бывает, что решение подогнано под тесты, но это видно сразу.

Прочитал урок — ничего не понятно ��

Создавать обучающие материалы, понятные для всех без исключения, довольно сложно. Мы очень стараемся, но всегда есть что улучшать. Если вы встретили материал, который вам непонятен, опишите проблему в «Обсуждениях». Идеально, если вы сформулируете непонятные моменты в виде вопросов. Обычно нам нужно несколько дней для внесения правок.

Кстати, вы тоже можете участвовать в улучшении курсов: внизу есть ссылка на исходный код уроков, который можно править прямо из браузера.

Полезное

Определения

• Предикат — выражение, отвечающее на вопрос «да» или «нет» с помощью типа boolean.

Python: Предикаты

Функция is_infant() — это функция-предикат или функция-вопрос. Предикат отвечает на утвердительный вопрос «да» или «нет», возвращая значение типа bool. Предикаты во всех языках принято именовать особым образом для простоты анализа. В Python предикаты начинаются с префикса is или has :

• is_infant() — «младенец ли?»
• has_children() — «есть ли дети?»
• is_empty() — «пустой ли?»
• has_errors() — «есть ли ошибки?»

Функция считается предикатом, если она возвращает булевы значения True или False .

Напишем еще одну функцию-предикат. Она принимает строку и проверяет, является ли она словом ‘Castle’ :

def is_castle(string): return string == 'Castle' print(is_castle('Sea')) # False 

Задание

Напишите функцию is_mister() , которая принимает строку и проверяет, является ли она словом ‘Mister’ .

is_mister('Mister') # True is_mister('Missis') # False 

Упражнение не проходит проверку — что делать? ��

Если вы зашли в тупик, то самое время задать вопрос в «Обсуждениях». Как правильно задать вопрос:

• Обязательно приложите вывод тестов, без него практически невозможно понять что не так, даже если вы покажете свой код. Программисты плохо исполняют код в голове, но по полученной ошибке почти всегда понятно, куда смотреть.

В моей среде код работает, а здесь нет ��

Тесты устроены таким образом, что они проверяют решение разными способами и на разных данных. Часто решение работает с одними входными данными, но не работает с другими. Чтобы разобраться с этим моментом, изучите вкладку «Тесты» и внимательно посмотрите на вывод ошибок, в котором есть подсказки.

Мой код отличается от решения учителя ��

Это нормально ��, в программировании одну задачу можно выполнить множеством способов. Если ваш код прошел проверку, то он соответствует условиям задачи.

В редких случаях бывает, что решение подогнано под тесты, но это видно сразу.

Прочитал урок — ничего не понятно ��

Создавать обучающие материалы, понятные для всех без исключения, довольно сложно. Мы очень стараемся, но всегда есть что улучшать. Если вы встретили материал, который вам непонятен, опишите проблему в «Обсуждениях». Идеально, если вы сформулируете непонятные моменты в виде вопросов. Обычно нам нужно несколько дней для внесения правок.

Кстати, вы тоже можете участвовать в улучшении курсов: внизу есть ссылка на исходный код уроков, который можно править прямо из браузера.

Полезное

Определения

• Предикат — выражение, отвечающее на вопрос «да» или «нет» с помощью типа bool.