Фильтр (функция высшего порядка)

Функция компьютерного программирования

В функциональном программировании фильтр — это функция высшего порядка , которая обрабатывает структуру данных (обычно список ) в некотором порядке для создания новой структуры данных, содержащей именно те элементы исходной структуры данных, для которых данный предикат возвращает логическое значение true .

Пример

В Haskell пример кода

 фильтровать даже [ 1 .. 10 ]  

вычисляет список 2, 4, …, 10, применяя предикат evenк каждому элементу списка целых чисел 1, 2, …, 10 в этом порядке и создавая новый список тех элементов, для которых предикат возвращает логическое значение true , тем самым создавая список, содержащий только четные элементы этого списка. И наоборот, пример кода

 фильтр ( нет . даже ) [ 1 .. 10 ]    

вычисляет список 1, 3, …, 9, собирая те элементы списка целых чисел 1, 2, …, 10, для которых предикат evenвозвращает логическое значение false (который .является оператором композиции функции ).

Наглядный пример

Ниже вы можете увидеть представление каждого шага процесса фильтрации для списка целых чисел X = [0, 5, 8, 3, 2, 1]в соответствии с функцией:

$${\displaystyle f(x)={\begin{cases}\mathrm {True} &{\text{ if }}x\equiv 0{\pmod {2}}\\\mathrm {False} &{\text{ if }}x\equiv 1{\pmod {2}}.\end{cases}}}$$

Эта функция показывает, что если четно, то возвращаемое значение равно , в противном случае — . Это предикат. ${\displaystyle x}$ ${\displaystyle \mathrm {True} }$ ${\displaystyle \mathrm {False} }$

Просмотр этапов обработки при применении функции фильтра к списку

Сравнение языков

Фильтр — стандартная функция для многих языков программирования , например, Haskell, ^[1] OCaml , ^[2] Standard ML , ^[3] или Erlang . ^[4] Common Lisp предоставляет функции remove-ifи remove-if-not. ^[5] Запросы на реализацию схемы (SRFI) 1 обеспечивают реализацию фильтра для языка Scheme . ^[6] C++ предоставляет алгоритмы remove_if (мутирующие) и remove_copy_if(немутирующие); C++11 дополнительно предоставляет copy_if(немутирующий). ^[7] Smalltalk предоставляет select:метод для коллекций. Фильтр также можно реализовать с использованием списков на языках, которые их поддерживают.

В Haskell это filterможно реализовать так:

 фильтр :: ( a -> Bool ) -> [ a ] ​​-> [ a ] ​​фильтр _ [] = [] фильтр p ( x : xs ) = [ x | p x ] ++ фильтр p xs                         

Здесь []обозначает пустой список, ++операцию объединения списков, и [x | p x]обозначает список, условно содержащий значение, x, если условие p xвыполняется (приводится значение True).

Варианты

Фильтр создает результат без изменения исходного списка. Многие языки программирования также предоставляют варианты, которые вместо этого деструктивно изменяют аргумент списка для повышения производительности. Другие варианты фильтров (например, Haskell dropWhile^[14] и partition^[15] ) также распространены. Общая оптимизация памяти для чисто функциональных языков программирования заключается в том, чтобы входной список и отфильтрованный результат имели самый длинный общий хвост ( tail-sharing ).

Смотрите также

• Карта (функция высшего порядка)
• Понимание списка
• Охранник (вычислительный)

Рекомендации

1. фильтр в стандартной прелюдии Haskell
2. фильтр в модуле стандартной библиотеки OCamllist
3. «Структура списка». Стандартная базовая библиотека машинного обучения . Проверено 25 сентября 2007 г.
4. filter/2 в документации модуля Erlang STDLIB Reference Guide.lists
5. Функция REMOVE, REMOVE-IF, REMOVE-IF-NOT, DELETE, DELETE-IF, DELETE-IF-NOT в HyperSpec Common Lisp
6. фильтр в SRFI 1
7. стандартной библиотеки шаблонов SGI (STL).
8. clojure.core/filter на ClojureDocs
9. Функция COMPLEMENT в Common Lisp HyperSpec.
10. Функция EVENP, ODDP в Common Lisp HyperSpec.
11. ИСО/МЭК 13211-1:1995/Кор 2:2012.
12. «Проект технического исправления 2» .
13. «Встроенные функции — документация Python 3.9.0» . docs.python.org . Проверено 28 октября 2020 г.
14. Удаление фильтра Haskell Пока
15. Раздел фильтра Haskell